Décomposition en une somme de multiples de 5 et de 7

GTG
GTG
Modifié (8 Apr) dans Collège/Lycée
Bonjour,
dans le volume d'Algèbre de Gautier & alii, on trouve au chapitre II-1, l'énoncé d'exercice suivant.
"Prouver que tout entier $x$ supérieur ou égal à 24 peut s'écrire sous la forme $x=5a+7b$, où $a$ et $b$ sont des entiers relatifs."
Est-ce qu'il n'y a pas une erreur dans l'énoncé ? Est-ce qu'il ne faut pas lire que $a$ et $b$ sont des entiers naturels ? Sinon la démonstration est triviale et on ne comprend pas la référence à 24, non ? (On a $5\times(-4)+7\times3=1$.)
(J'espère que ce post est bien à sa place dans la catégorie Collège/Lycée. C'est un manuel de niveau Terminale mais publié il y a 25 ans dans la perspective d'initier à l'enseignement supérieur.)
Je me remets à niveau en vue de faire une thèse en sociologie et/ou de passer l'agrégation de SES. Pour l'instant, le niveau en question est entre la Terminale S et la L1. J'utilise le manuel ForMath de Gautier et alii. Mon pseudo est une référence au mathématicien Georges-Théodule Guilbaud.

Réponses

  • JLapin
    Modifié (8 Apr)
    Effectivement, plus généralement, si $x$ et $y$ sont deux entiers naturels premiers entre eux, tout entier supérieur ou égal à $(x-1)(y-1)$ peut s'écrire sous la forme $xu+yv$ avec $u$ et $v$ deux entiers naturels.
  • gebrane
    Modifié (8 Apr)
    Je crois que le vrai énoncé est 
    Prouver que tout entier naturel x supérieur ou égal à 24 peut s'écrire sous la forme x=5a+7b, où a et b  sont des entiers naturels.
    Avec cette version on comprend bien que x doit être supérieure à  24 sinon comment écrire x=23 en telle somme avec a,b des entiers naturels ?
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • On a trivialement $$x=5(3x-7k)+7(5k-2x)$$
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • Chaurien
    Modifié (9 Apr)
    Quel est au juste ce livre ? Voyant l'auteur Christian Gautier (1943-2008), mon ami trop tôt disparu, j'ai pensé d'abord à la célèbre collection Aleph (Hachette), mais elle a bien plus de vingt ans, alors c'est peut-être : Christian Gautier, Philippe Colombo, Philippe Koechli, Algèbre et probabilités - Niveau lycée - Premières et Terminales S et ES - Formation continue, Ellipses 1998 ?
  • Chaurien
    Modifié (9 Apr)
    • Pour la question posée, il est clair que c'est une erreur d'énoncé. Il est bien connu que deux nombres  $a \in \mathbb Z$ et $b \in \mathbb Z$ sont premiers entre eux si et seulement si  $a \mathbb Z +b \mathbb Z = \mathbb Z$.
    • Sinon, c'est le problème des pièces de monnaie de Sylvester-Frobenius : pour les entiers $a \ge 2$, $b \ge 2$, premiers entre eux, quelles sommes peuvent-elles être payées avec des pièces de $a$ francs et de $b$ francs ? L'ensemble de ces sommes est $S=\{ax+by| x \in \mathbb N, y \in \mathbb N\}$. Les collègues ont rappelé plus haut que tous les entiers $ \ge (a-1)(b-1)$ sont éléments de $S$, et que $(a-1)(b-1)-1=ab-a-b$ ne l'est pas. 
    On peut ajouter une très jolie propriété :  dans l'ensemble  $ [\![0,ab-a-b]\!]$, de cardinal $(a-1)(b-1)$, forcément pair, il y a exactement la moitié des éléments qui sont des éléments de $S$, autrement dit : $|S\cap  [\![0,ab-a-b]\!]|= \frac 12 (a-1)(b-1)$.
    Dans l'exemple évoqué ici, $a=5,b=7$, on a :  $(a-1)(b-1)=24$ et $S\cap  [\![0,23]\!]=\{0, 5,7,10,12,14,15,17,19,20,21,22 \}$.
    Bonne journée.
    Fr. Ch. 
  • Au niveau le plus élémentaire, il suffit de décomposer $24, 25,26,27,28$ et ensuite de procéder par récurrence.
  • john_john
    Modifié (9 Apr)
    Et, pour synthétiser les interventions précédentes, il faut savoir que $24$ est le plus petit entier naturel à partir duquel tous les entiers soient de la forme $5a+7b$, où $a$ et $b$ sont des naturels.
  • Aujourd'hui, chercher la solution à un problème, ça revient souvent à chercher via un moteur de recherche, et non plus réfléchir par soi-même.
    Et du coup, l'information utile, c'est le mot clé qui permet de retrouver toute la littérature existant autour de ce sujet. 
    Ici, Chaurien a donné l'information très utile : c'est le problème des pièces de monnaie de Sylvester-Frobenius.
    Avec ces mots clés, on arrive rapidement à cette synthèse 
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Pour culture générale la notion clé ici est celle de demi-groupe numérique (ou semigroupe...).
  • JLapin
    Modifié (9 Apr)
    Aujourd'hui, chercher la solution à un problème, ça revient souvent à chercher via un moteur de recherche, et non plus réfléchir par soi-même.
    Ta réflexion sonne étrangement. Comme si tu étais amer d'avoir pu faire appel à Google pour trouver des infos en lien avec le message de Chaurien.
  • lourrran
    Modifié (9 Apr)
    Je réagissais en fait au message de John_John. Je pense que sa synthèse est très incomplète, et c'est pour ça que j'ai complété avec le lien Wikipédia. 
    Et Raoul.S a fait la même chose en réagissant à mon message, en donnant une vision plus mathématique de ce petit problème du quotidien.
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • Est-ce qu'on se trompe sur le forum ? Celui-ci ne doit pas dépasser le niveau collège lycée
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • Chaurien
    Modifié (9 Apr)
    Chercher la solution d'un problème, ça a toujours été chercher dans sa tête et si besoin est, en complément, chercher dans les sources dont on peut disposer, naguère sur papier, aujourd'hui aussi sur Internet. La recherche est plus facile quand il y a un nom propre, et c'est pourquoi j'ai été heureux d'en fournir afin que tout un chacun puisse se renseigner à propos de ce problème, qui est encore l'objet de recherches si au lieu de deux pièces de monnaie on en considère plusieurs. Voir par exemple : C7-The money -changing problem dans : Richard K. Guy, Unsolved problems in Number Theory, Third edition, Springer 2004, p. 170.
  • PetitLutinMalicieux
    Modifié (9 Apr)
    Bonjour
    $23=(+6)\times 5 + (- 1) \times 7$.
  • gerard0
    Modifié (9 Apr)
    -1 n'est pas un entier naturel.
    Cordialement.
  • Et avec trois nombres, par exemple 5, 7 et 8 ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • GTG
    GTG
    Modifié (9 Apr)
    Bonjour et merci pour vos réponses !
    La plupart d'entre elles vont plus loin que ma demande et même plus loin que mes compétences et savoirs actuels en maths. Mais certaines m'éclairent parce que j'avais essayé en rectifiant l'erreur présumée (et maintenant avérée) et n'étais parvenu qu'à un résultat disons... laborieux, en montrant qu'on pouvait obtenir toutes les terminaisons ($\overline{m0},\overline{m1},\dots,\overline{m9}$) deux par deux (grâce au facteur 5), à partir de certains entiers.
    Merci en particulier à @Chaurien. Je confirme qu'il s'agit bien du volume Algèbre et probabilités, aux éditions Ellipses. Je le trouve (en fait les trouve, puisqu'il y a trois volumes) relativement adapté à mon niveau et à ce moment de mes projets. Il n'y a ni solutions ni corrigés, ce qui ne facilite pas mon travail isolé mais j'en profite pour travailler mon écriture mathématique. Et heureusement il y a ce forum pour mes doutes et mes échecs.
    Merci aussi à @JLT : l'exercice se trouve sous le titre "Récurrence".
    Je me remets à niveau en vue de faire une thèse en sociologie et/ou de passer l'agrégation de SES. Pour l'instant, le niveau en question est entre la Terminale S et la L1. J'utilise le manuel ForMath de Gautier et alii. Mon pseudo est une référence au mathématicien Georges-Théodule Guilbaud.
  • john_john
    Modifié (9 Apr)
    Avec $5,7,8$, le seuil s'abaisse nettement :
    $23=15+8$
    $22=14+8$
    $21$, $20$, $16$ multiples de $7$,$5$  et $8$ respectivement
    $19=14+5$
    $18=10+8$
    $17=10+7$
    $15=5\times3$
    $14=7\times2$
    $13=5+8$
    $12=7+5$

    En revanche, $11$ ne se décompose pas.
  • gebrane
    Modifié (10 Apr)
    Bonjour, pourquoi JLT avait besoin de décomposer 24, 25, 26, 27, 28 pour mener une récurrence ?
    Je m'essaye.
    On initialise d'abord à 24 en vérifiant que 24 admet une décomposition $24=7\times2+5\times2$. Ensuite, on suppose qu'un $x\geq 25$ se décompose en $x=7a+5b$, alors $x+1$ se décompose en $7(a-2)+5(b+3)$. Pour conclure, il suffit de traiter les cas $a=0$ ou $a=1$ à part.
    Si $a=0$, alors $x=5b$ et puisque $x\geq 25$, nécessairement $b\geq 5$ et donc $b=5+\alpha$. On en déduit $x+1= 5b+1=25+5\alpha+1=26+5\alpha=7\times3+5(\alpha +1)$.
    Si $a=1$, alors $x=7+5b$ et puisque $x\geq 25$, nécessairement $b\geq 3$ et donc $b=3+\beta$. On en déduit $x+1= 8+ 5b=23+5\alpha$ et là, on bloque. Il faut donc initialiser comme JLT à partir de 27, de telle façon que si $x\geq 27$, nécessairement $b\geq 4$ et donc $b=4+\beta$. On en déduit $x+1= 28+5\alpha=7\times4+5\alpha$.
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • GTG
    GTG
    Modifié (10 Apr)
    @gebrane La solution suggérée par @JLT me paraît moins périlleuse, à défaut d'être plus courte.
    On a $24 = 5.2 + 7.2$, $25= 5.5 + 7.0$, $26= 5.1 +7.3$, $27 = 5.4 +
     7.1$ et $28 = 5.0 + 7.4$. Donc la proposition est vraie pour les cinq
     premiers entiers supérieurs ou égaux à 24.
     Supposons maintenant la proposition vraie pour cinq entiers consécutifs $n,n+1,n+2,n+3 \text{ et } n+4$, tous supérieurs à 24. On a donc :
     - $n=5\times p_0 + 7\times q_0$ ;
     - $n+1=5\times p_1 + 7\times q_1$ ;
     - $n+2=5\times p_2 + 7\times q_2$ ;
     - $n+3=5\times p_3 + 7\times q_3$ ;
     - $n+4= 5\times p_4 + 7\times q_4$,
    avec $p_0,p_1,p_2,p_3,p_4,q_0,q_1,q_2,q_3 \text{ et } q_4$ dans $\mathbb{N}$. Alors,
     - $n+5=5\times (p_0+1) + 7\times q_0$ ;
     - $n+6=5\times (p_1+1) + 7\times q_1$ ;
     - $n+7=5\times (p_2+1) + 7\times q_2$ ;
     - $n+8=5\times (p_3+1) + 7\times q_3$ ;
     - $n+9 = 5\times (p_4+1) + 7\times q_4$.
     La récurrence est donc acquise. Et par conséquent la proposition.
    Je me remets à niveau en vue de faire une thèse en sociologie et/ou de passer l'agrégation de SES. Pour l'instant, le niveau en question est entre la Terminale S et la L1. J'utilise le manuel ForMath de Gautier et alii. Mon pseudo est une référence au mathématicien Georges-Théodule Guilbaud.
  • gebrane
    Modifié (10 Apr)
    Bonjour, GTG
    Tu as fait mieux
    Pour ta preuve, il suffit de le vérifier uniquement pour \( n+5 \) puisque c'est déjà vérifié pour \( n+1, \ldots, n+4 \) par hypothèse de récurrence. 
    Voici un autre raisonnement mais peux-tu l'améliorer ? J'ai utilisé l'égalité triviale :
    \[\forall x\in\mathbb{N},\forall k\in \mathbb{N},\ x= 5(3x-7k)+7(5k-2x)\]
    Donc il suffit de pouvoir démontrer qu'il existe \( k\in\mathbb{N} \) tel que \( 3x-7k\geq 0 \) et \( 5k-2x\geq 0 \), c'est-à-dire
    \[\frac{2x}{5} \leq k \leq \frac{3x}{7}\]
    J'ai choisi \( k = E(\frac{3x}{7}) \) et je démontre que si \( x \geq 35 \), on a bien \( \frac{2x}{5} \leq k \leq \frac{3x}{7} \). Peux-tu faire un meilleur choix de \( k \) ?
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • Tu peux optimiser en cherchant $k$ entier tel que $3x-7k>-1$ et $5k-2x>-1$.
    Tu retrouveras alors que la condition $x\geq 24$ suffit.
  • zygomathique
    Modifié (10 Apr)
    Salut
    puisque $3 \times 5 - 2 \times 7 = 1$ alors s'il existe un entier n tel que $n = 5a + 7b$ on en déduit que $n + 1 = 5(a + 3) + 7(b - 2) \   (1)$ tant que $ b > 2$
    puisque $3 \times 7 - 4 \times 5 = 1$ alors s'il existe un entier n tel que $n = 5a + 7b$ on en déduit que $n + 1 = 5(a - 4) + 7(b + 3) \    (2)$ tant que $ a > 4$
    en combinant (1) + (2) on en déduit que $ n + 2 = 5(a - 1) + 7(b + 2)$
    on en déduit qu'en combinant "convenablement" les opérations (1) et (2) alors on obtient touts les entiers à partir d'un certain rang
    et ce rang est supérieur à 2 * 7 et à 4 * 5 donc à 20 ...
    de plus 5 * 5 + 0 * 7 = 25 et on peut ensuite appliquer (2) puis (1)  puis ...
    on peut fortement penser que ce seuil est inférieur à 25 ...

    Ce ne sont pas les signes, les symboles qui constituent la science ; le seul principe qui y domine, c’est l’esprit de sagacité auquel les objets soumis servent d’auxiliaire.                BHASCARA

  • Y a-t-il d'autres preuves qui ne dépassent pas le cadre de ce sous-forum ?
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • bien entendu je donne une preuve plus complète et rigoureuse à mes math expertes et je n'ai présenté que le "schéma" ou l'idée générale ...

    Ce ne sont pas les signes, les symboles qui constituent la science ; le seul principe qui y domine, c’est l’esprit de sagacité auquel les objets soumis servent d’auxiliaire.                BHASCARA

  • Guego
    Modifié (10 Apr)
    Dans le Arnaudiès-Delezoide-Fraysse, Exercices d'algèbre tome 1 :

  • Bonjour et merci encore à tous.
    Merci en particulier à @gebrane. Je ne comprends pas bien cette histoire de récurrence. Il faut donc nécessairement initialiser sur les 5 entiers consécutifs à partir de 24, nécessairement aussi faire l'hypothèse sur 5 entiers consécutifs supérieurs à 24 mais il suffit de montrer la récurrence pour un seul entier ?
    Je regarderai vos autres propositions plus tard.
    Je me remets à niveau en vue de faire une thèse en sociologie et/ou de passer l'agrégation de SES. Pour l'instant, le niveau en question est entre la Terminale S et la L1. J'utilise le manuel ForMath de Gautier et alii. Mon pseudo est une référence au mathématicien Georges-Théodule Guilbaud.
  • GTG, tu lis ce document sur les récurrences doubles
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • On appelle P(n) l'assertion : il existe une décomposition pour n, n+1,..., n+4. Elle est vraie pour n=24.
    Si elle est vraie pour n alors on montre qu'elle est vraie pour n+1. Pour cela il suffit de décomposer n+5 en partant d'une décomposition de n, ce qui est facile.
  • gebrane
    Modifié (10 Apr)
    Merci @Guego pour ton  lien qui donne une méthode qui coïncide avec la mienne sauf que je n'ai pas cherché le k optimal qui doit être d'après ton lien $k=(a-1)(b-1)=6\times 4=24$ et ce n'est  pas si évident, donc je me tourne vers @Jlapin, après un bonjour, comment as-tu cherché ce $k$ optimal ?
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • JLapin
    Modifié (10 Apr)
    Tu peux reprendre mon message et utiliser le fait que si $Y-X>1$, alors l'intervalle $]X,Y[$ contient au moins un entier relatif.
  • gebrane
    Modifié (10 Apr)
    Bonjour @Jlapin, dans ton dernier message tu as dit 
    Tu peux optimiser en cherchant $k$ entier tel que $3x-7k>-1$ et $5k-2x>-1$.
    Je ne vois pas une valeur ajouté à mon message  précèdent :
    il suffit de pouvoir démontrer qu'il existe \( k\in\mathbb{N} \) tel que \( 3x-7k\geq 0 \) et \( 5k-2x\geq 0 \)
    sauf si tu vois une différence entre $3x-7k>-1$ et $5k-2x>-1$ vs \( 3x-7k\geq 0 \) et \( 5k-2x\geq 0 \)
    Est ce que tu as chercher le $k$ optimal comme dans le lien de Guego ou autrement ?
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • JLapin
    Modifié (10 Apr)
    Oui, il y a une différence : pose les inéquations strictes qui contrôlent $k$ que je te donne et tu verras apparaître le 24.
    L'idée est qu'il est "plus simple" pour un réel d'être strictement plus grand que $-1$ que supérieur ou égal à $0$ donc mes inéquations avec des inégalités strictes donnent un peu plus de marge pour trouver un entier $k$ satisfaisant que tes inéquations avec des inégalités larges;
  • gebrane
    Modifié (10 Apr)
    Où vois-tu des réels, le $x$ et $k$ sont des entiers et donc $3x-7k\geq 0\iff  3x-7k> -1$
    La question du fil est Prouver que tout entier naturel x supérieur ou égal à 24 peut s'écrire sous la forme x=5a+7b, où a et b  sont des entiers naturels., non?

    Ajout, bon je ne comprends pas et je ne vais pas insister
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • JLapin
    Modifié (10 Apr)
    Oui, et c'est grâce à cette équivalence que je parviens à trouver le seuil 24. Je ne doute pas que tu y arrives toi aussi.
  • JLapin
    Modifié (10 Apr)
    Il suffit de résoudre le système d'inéquation suivant d'inconnue réelle $k$.
    3x−7k>−1 et 5k−2x>−1

    puis de vérifier que parmi toutes les solutions réelles se trouve au moins une solution dans $\Z$.

  • JLapin
    Modifié (10 Apr)
    Ajout, bon je ne comprends pas et je ne vais pas insister

    Dommage, tu es vraiment à trois lignes d'une épiphanie tout à fait remarquable ! Ne me laisse pas tomber camarade !

  • Je viens de comprendre camarade ce que tu voulais me dire , il fallait me dire que tu considères le  k  comme étant un réel
    Le 😄 Farceur est fasciné par  notre  cher Nico-le prof le sérieux


  • JLapin
    Modifié (10 Apr)
    , il fallait me dire que tu considères le  k  comme étant un réel
    J'avoue que j'ai eu beaucoup de mal à comprendre ce que tu avais du mal à comprendre, désolé :)
  • Merci @gebrane et @JLT pour ces éclaircissements sur la récurrence (ou les récurrences d'ailleurs).
    Je me remets à niveau en vue de faire une thèse en sociologie et/ou de passer l'agrégation de SES. Pour l'instant, le niveau en question est entre la Terminale S et la L1. J'utilise le manuel ForMath de Gautier et alii. Mon pseudo est une référence au mathématicien Georges-Théodule Guilbaud.
Connectez-vous ou Inscrivez-vous pour répondre.