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

GTG

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.)

JLapin

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

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 ?

gebrane

On a trivialement $$x=5(3x-7k)+7(5k-2x)$$

Chaurien

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

• 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. 

JLT

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

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.

lourrran

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 

raoul.S

Pour culture générale la notion clé ici est celle de demi-groupe numérique (ou semigroupe...).

JLapin

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

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.

gebrane

Est-ce qu'on se trompe sur le forum ? Celui-ci ne doit pas dépasser le niveau collège lycée

raoul.S

Voici un article niveau lycée au cas où : https://images.math.cnrs.fr/Semigroupes-numeriques-et-conjecture-de-Wilf-3865.html

Chaurien

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

Bonjour
$23=(+6)\times 5 + (- 1) \times 7$.

gerard0

-1 n'est pas un entier naturel.
Cordialement.

nicolas.patrois

Et avec trois nombres, par exemple 5, 7 et 8 ?

GTG

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".

john_john

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

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$.

GTG

@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.

gebrane

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 \) ?

JLapin

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

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 ...

gebrane

Y a-t-il d'autres preuves qui ne dépassent pas le cadre de ce sous-forum ?

zygomathique

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 ...

Guego

Dans le Arnaudiès-Delezoide-Fraysse, Exercices d'algèbre tome 1 :

GTG

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.

gebrane

GTG, tu lis ce document sur les récurrences doubles

JLT

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

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 ?

JLapin

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

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 ?

JLapin

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

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

JLapin

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

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

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 !

gebrane

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

JLapin

, 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é

GTG

Merci @gebrane et @JLT pour ces éclaircissements sur la récurrence (ou les récurrences d'ailleurs).