Terminale maths expertes

PGCD, Bézout et équations diophantiennes — 20 exercices corrigés

Cette série relie l'algorithme d'Euclide, les identités de Bézout, le lemme de Gauss et les équations diophantiennes. Les inconnues sont entières sauf indication contraire. Une identité numérique correcte n'est pas automatiquement un certificat du PGCD : il faut aussi contrôler les divisibilités. Les paramétrages sont donnés avec leur domaine exact, puis restreints lorsque des contraintes de signe ou d'encadrement sont imposées. Les approfondissements sont explicitement signalés.

L'essentiel à retenir

Le PGCD de deux entiers non tous deux nuls est leur plus grand diviseur commun positif. Changer un signe ne le modifie pas : $\mathrm{PGCD}(a,b)=\mathrm{PGCD}(|a|,|b|)$ .
L'algorithme d'Euclide utilise $\mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,a-bq)$ et se termine au dernier reste non nul.
Le théorème de Bézout affirme qu'il existe des entiers u et v tels que $au+bv=\mathrm{PGCD}(a,b)$ . Une remontée de l'algorithme d'Euclide permet de les calculer.
Pour certifier que d est le PGCD, on peut vérifier que d est positif, qu'il divise les deux nombres et qu'il est une combinaison linéaire entière de ces nombres.
Le lemme de Gauss affirme que si a divise bc et si le PGCD de a et b vaut 1, alors a divise c. La condition de coprimalité ne doit pas être omise.
L'équation $ax+by=c$ est soluble en entiers si et seulement si le PGCD de a et b divise c. Pour a et b non nuls, à partir d'une solution ( $x_0$ , $y_0$ ), toutes les solutions sont $x=x_0+(b/d)t$ , $y=y_0-(a/d)t$ .
Un entier a possède un inverse modulo m exactement lorsque son PGCD avec m vaut 1. Les coefficients de Bézout fournissent cet inverse.
Pour deux entiers strictement positifs, leur produit est égal au produit de leur PGCD et de leur PPCM. Pour exploiter cette relation à rebours, il faut encore imposer la coprimalité des facteurs réduits.

Exercice 1 — Euclide puis remontée complète

Calculer le PGCD de 252 et 198 par l'algorithme d'Euclide.
Remonter les égalités pour obtenir une identité de Bézout.
Utiliser le résultat pour déterminer tous leurs diviseurs communs positifs.

Corrigé détaillé

Les divisions successives sont $252=198\times1+54$ , $198=54\times3+36$ , $54=36\times1+18$ , puis $36=18\times2+0$ . Le dernier reste non nul est 18, donc $\mathrm{PGCD}(252,198)=18$ .
On remonte sans sauter de substitution : $18=54-36$ et $36=198-3\times54$ , d'où $18=4\times54-198$ . Puis $54=252-198$ , donc $18=4\times252-5\times198$ . La vérification numérique est $1008-990=18$ .
Tout diviseur commun de 252 et 198 divise chacune de leurs combinaisons linéaires, donc il divise 18. Réciproquement, comme 18 divise 252 et 198, tout diviseur de 18 les divise également. Les diviseurs communs positifs sont exactement 1, 2, 3, 6, 9 et 18. La remontée fournit ainsi plus qu'un nombre : elle prouve que tout diviseur commun est nécessairement un diviseur du dernier reste non nul.

Exercice 2 — Des nombres plus grands et des signes

Calculer le PGCD de 12345 et 6789.
Déterminer des coefficients de Bézout et les vérifier.
En déduire une identité de Bézout pour -12345 et 6789, puis décider si $12345x+6789y=12$ est soluble.

Corrigé détaillé

Les divisions sont $12345=6789+5556$ , $6789=5556+1233$ , $5556=4\times1233+624$ , $1233=624+609$ , $624=609+15$ , $609=40\times15+9$ , $15=9+6$ , $9=6+3$ , $6=2\times3$ . Le PGCD vaut donc 3.
La remontée peut se regrouper ainsi : $3=2\times9-15=2\times609-81\times15=83\times609-81\times624$ . Puis $609=1233-624$ , donc $3=83\times1233-164\times624=739\times1233-164\times5556$ . Enfin $1233=6789-5556$ et $5556=12345-6789$ , d'où $3=-903\times12345+1642\times6789$ . Vérification : les produits sont -11147535 et 11147538, de somme 3.
Pour les nombres -12345 et 6789, on change le premier coefficient : $3=903(-12345)+1642\times6789$ . Enfin, 3 divise 12 ; l'équation est soluble. En multipliant l'identité initiale par 4, on obtient par exemple $x=-3612$ et $y=6568$ .

Exercice 3 — Un certificat valable et un mauvais certificat

Vérifier l'égalité $8\times414-5\times662=2$ . Suffit-elle, à elle seule, à prouver que le PGCD est 2 ?
Compléter la preuve correcte.
Un autre élève affirme que $2\times414-662=166$ prouve que le PGCD est 166 : diagnostiquer l'erreur.

Corrigé détaillé

On calcule $8\times414=3312$ et $5\times662=3310$ , donc la différence vaut bien 2. Cette identité montre que tout diviseur commun de 414 et 662 divise 2. Elle établit seulement que le PGCD est 1 ou 2 ; il faut encore vérifier que 2 est effectivement un diviseur commun.
Les nombres 414 et 662 sont pairs, avec $414=2\times207$ et $662=2\times331$ . Ainsi 2 les divise tous les deux. Combinée à l'identité précédente, cette vérification donne $\mathrm{PGCD}(414,662)=2$ .
L'égalité $828-662=166$ est vraie. Elle prouve seulement que le PGCD divise 166, pas que 166 est le PGCD. D'ailleurs $414=2\times166+82$ , donc 166 ne divise même pas 414. Un certificat correct comprend deux directions : le candidat doit diviser les deux nombres, et tout diviseur commun doit diviser le candidat. Une combinaison linéaire assure la seconde direction, jamais automatiquement la première.

Exercice 4 — Démontrer puis utiliser le lemme de Gauss

Démontrer le lemme de Gauss à partir de Bézout : si a divise bc et si le PGCD de a et b vaut 1, alors a divise c.
Résoudre la condition $35\mid12n$ pour n entier.
Montrer par un contre-exemple que l'hypothèse de coprimalité est indispensable.

Corrigé détaillé

Bézout fournit des entiers u et v tels que $au+bv=1$ . En multipliant par c, on obtient $acu+bcv=c$ . Le premier terme est divisible par a, et le second l'est aussi puisque a divise bc. Leur somme c est donc divisible par a. Cette démonstration vaut pour des entiers de signes quelconques, sous réserve que la notion de PGCD soit bien définie.
On a $\mathrm{PGCD}(35,12)=1$ , car les facteurs premiers de 35 sont 5 et 7, qui ne divisent pas 12. Le lemme donne $35\mid n$ . Réciproquement, tout multiple de 35 convient. Les solutions sont donc $n=35k$ , k entier.
Prenons $a=6$ , $b=4$ et $c=3$ . On a $bc=12$ , divisible par 6, mais $c=3$ n'est pas divisible par 6. L'échec vient du PGCD de 6 et 4, qui vaut 2 et non 1. On ne peut donc pas supprimer un facteur d'une relation de divisibilité sans vérifier sa coprimalité avec le diviseur.

Exercice 5 — Paramétrer une équation diophantienne générale

Résoudre dans les entiers $252x+198y=90$ .
Prouver que le paramétrage obtenu contient toutes les solutions.
Déterminer la solution pour laquelle x appartient à l'intervalle [0,10].

Corrigé détaillé

Le PGCD de 252 et 198 vaut 18, et 18 divise 90. L'identité $4\times252-5\times198=18$ , multipliée par 5, donne la solution particulière (20,-25). En divisant l'équation par 18, on obtient $14x+11y=5$ . Toutes les solutions s'écrivent donc $x=20+11t$ , $y=-25-14t$ , avec t entier. Une présentation plus courte résulte de $t=-1$ : $x=9+11k$ , $y=-11-14k$ .
Si (x,y) et (9,-11) sont solutions, alors $14(x-9)=-11(y+11)$ . Les nombres 14 et 11 étant premiers entre eux, Gauss impose $11\mid(x-9)$ . Ainsi $x=9+11k$ , puis la substitution donne $y=-11-14k$ . Réciproquement, ces expressions satisfont l'équation pour tout k entier.
La condition $0\leq9+11k\leq10$ impose $k=0$ : $k=-1$ donne -2 et $k=1$ donne 20. La solution est donc (9,-11). Vérification : $252\times9+198\times(-11)=2268-2178=90$ .

Exercice 6 — Une équation impossible puis une équation soluble

Déterminer le PGCD de 2024 et 748.
Décider si $2024x+748y=30$ possède une solution entière.
Résoudre complètement $2024x+748y=132$ .

Corrigé détaillé

L'algorithme donne $2024=2\times748+528$ , $748=528+220$ , $528=2\times220+88$ , $220=2\times88+44$ , puis $88=2\times44$ . Le PGCD vaut 44. Une remontée fournit $44=-7\times2024+19\times748$ , car -14168+14212=44.
Tout membre de gauche est divisible par 44. Or 30 ne l'est pas : l'équation n'a aucune solution entière. Ce constat suffit ; essayer des valeurs de x et y ne serait pas une preuve générale.
Comme $132=3\times44$ , multiplier l'identité de Bézout par 3 donne une solution (-21,57). Les coefficients réduits sont $2024/44=46$ et $748/44=17$ . Toutes les solutions sont donc $x=-21+17t$ , $y=57-46t$ , où t est entier. Pour vérifier, les termes en t s'annulent puisque $2024\times17=748\times46=34408$ , et la partie constante vaut 132. La coprimalité de 46 et 17 garantit, par Gauss, qu'aucune autre solution ne manque.

Exercice 7 — Des achats soumis à la positivité

Des objets de deux types coûtent respectivement 7 € et 11 €. On dépense exactement 100 €.

Trouver toutes les solutions entières de $7x+11y=100$ .
Conserver celles où les quantités x et y sont positives ou nulles.
Déterminer les achats possibles si l'on exige au moins trois objets de chaque type.

Corrigé détaillé

Modulo 7, l'équation donne $4y\equiv2\pmod7$ . L'inverse de 4 modulo 7 est 2, donc $y\equiv4\pmod7$ . Posons $y=4+7t$ . Alors $7x=100-11(4+7t)=56-77t$ , d'où $x=8-11t$ . Toutes les solutions entières sont $(x,y)=(8-11t,4+7t)$ , avec t entier.
La condition $x\geq0$ donne $t\leq8/11$ , donc $t\leq0$ . La condition $y\geq0$ donne $t\geq-4/7$ , donc $t\geq0$ . Il reste seulement $t=0$ : on achète huit objets à 7 € et quatre objets à 11 €. Le coût vaut $56+44=100$ €.
Les conditions $x\geq3$ et $y\geq3$ donnent $8-11t\geq3$ , donc $t\leq0$ , et $4+7t\geq3$ , donc $t\geq0$ . Le même achat est donc encore l'unique possibilité. Le traitement séparé des solutions entières et des contraintes est important : le paramétrage contient une infinité de couples, mais une seule paire décrit ici un achat physiquement possible.

Exercice 8 — Une contrainte d'intervalle et de parité

Résoudre $9x-14y=5$ dans les entiers.
Déterminer les solutions avec $0\leq x\leq100$ et $0\leq y\leq60$ .
Parmi elles, conserver celles pour lesquelles x est impair.

Corrigé détaillé

Le couple (13,8) convient, car $9\times13-14\times8=117-112=5$ . Comme le PGCD de 9 et 14 vaut 1, toutes les solutions sont $x=13+14t$ , $y=8+9t$ , avec t entier. Le signe positif dans la seconde expression vient du signe négatif du terme -14y : les variations $9\times14t$ et $-14\times9t$ s'annulent.
Pour x, l'encadrement donne $-13\leq14t\leq87$ , donc 0≤ $t\leq6$ pour t entier. Pour y, il donne $-8\leq9t\leq52$ , donc 0≤ $t\leq5$ . L'intersection est $t=0$ ,1,2,3,4,5. Les couples sont (13,8), (27,17), (41,26), (55,35), (69,44) et (83,53).
L'expression $x=13+14t$ est toujours impaire, car 13 est impair et 14t est pair. Les six solutions satisfont donc la condition supplémentaire. Une contrainte de parité ne réduit pas nécessairement l'ensemble : il faut l'évaluer sur le paramétrage plutôt que supposer qu'elle élimine la moitié des solutions.

Exercice 9 — Calculer un inverse avec Bézout

Calculer l'inverse de 37 modulo 101 par l'algorithme d'Euclide.
Résoudre $37x\equiv12\pmod{101}$ .
Donner l'unique solution de cette congruence appartenant à [-50,50].

Corrigé détaillé

On effectue $101=2\times37+27$ , $37=27+10$ , $27=2\times10+7$ , $10=7+3$ , $7=2\times3+1$ . La remontée donne $1=7-2(10-7)=3\times7-2\times10=3\times27-8\times10=11\times27-8\times37=11\times101-30\times37$ . Ainsi $-30\times37\equiv1\pmod{101}$ et l'inverse positif est -30+101=71. Vérification : $37\times71=2627=26\times101+1$ .
En multipliant par 71, on obtient $x\equiv12\times71=852\equiv44\pmod{101}$ , puisque 852=8×101+44. Les solutions sont $x=44+101k$ .
La valeur 44 est dans [-50,50]. Les voisines 44-101=-57 et 44+101=145 sont hors intervalle. Elle est donc unique. La vérification dans la congruence initiale donne $37\times44=1628=16\times101+12$ , ce qui confirme exactement le second membre 12.

Exercice 10 — Approfondissement — Un PGCD dépendant d'un paramètre

Pour n entier positif ou nul, on pose

d_n=\mathrm{PGCD}(2n+1,n+5)

Montrer que $d_n=\mathrm{PGCD}(2n+1,9)$ .
Classer les valeurs de $d_n$ selon le reste de n modulo 9.
Déterminer les n de 0 à 100 pour lesquels $d_n$ =9.

Corrigé détaillé

On soustrait deux fois le second argument au premier : $(2n+1)-2(n+5)=-9$ . Ainsi $d_n=\mathrm{PGCD}(n+5,9)$ . Pour obtenir la forme demandée, on remarque que tout diviseur commun de 2n+1 et 9 est impair et divise $2(n+5)=(2n+1)+9$ ; Gauss lui permet donc de diviser n+5. Réciproquement, tout diviseur commun de $n+5$ et de $9$ divise $2(n+5)-9=2n+1$ . Les deux couples ont donc les mêmes diviseurs communs, ce qui prouve l’égalité des PGCD.
Pour $n=0$ ,1,2,3,4,5,6,7,8 modulo 9, les valeurs de 2n+1 modulo 9 sont 1,3,5,7,0,2,4,6,8. Les PGCD avec 9 sont donc 1,3,1,1,9,1,1,3,1. Autrement dit, $d_n$ =9 si $n\equiv4$ modulo 9 ; $d_n$ =3 si $n\equiv1$ ou 7 ; $d_n$ =1 dans les six autres classes.
On écrit $n=4+9k$ . Les bornes 0≤ $n\leq100$ donnent $k=0$ à 10. Les indices sont 4,13,22,31,40,49,58,67,76,85 et 94. Il y en a onze ; le suivant, 103, dépasse 100.

Exercice 11 — Un PGCD polynomial qui reste constant

Démontrer que $\mathrm{PGCD}(n,n+1)=1$ pour tout entier n.
En déduire $\mathrm{PGCD}(n^2+n+1,n+1)$ .
Donner une identité de Bézout explicite entre les deux expressions de la question 2.

Corrigé détaillé

Tout diviseur commun de n et n+1 divise leur différence 1. Leur seul diviseur commun positif est donc 1. L'identité $(n+1)-n=1$ est déjà une identité de Bézout.
On écrit $n^2+n+1=n(n+1)+1$ . Tout diviseur commun de $n^2$ +n+1 et n+1 divise le reste 1, donc leur PGCD vaut 1 pour tout entier n. Cela reste vrai pour $n=-1$ : les deux nombres valent alors 1 et 0, et leur PGCD est 1.
L'identité cherchée est simplement $1\times(n^2+n+1)-n\times(n+1)=1$ . Les coefficients sont 1 et -n, qui sont bien des entiers lorsque n est entier. Cette identité fournit une preuve directe et uniforme, sans calculer séparément les valeurs du PGCD. Elle montre aussi que $n^2$ +n+1 est inversible modulo n+1 lorsque ce module est au moins 2, et qu'il est alors congru à 1. Il ne faut pas confondre cette coprimalité systématique avec la primalité de $n^2$ +n+1, qui peut être composé.

Exercice 12 — Paver un rectangle par les plus grands carrés

Un rectangle mesure 414 cm sur 662 cm. On veut le paver sans découpe par une grille de carrés identiques dont les côtés sont parallèles à ceux du rectangle dont le côté est un nombre entier de centimètres.

Déterminer le plus grand côté possible.
Calculer le nombre de carrés.
Si le côté peut être rationnel, existe-t-il des pavages utilisant davantage de carrés ? Donner un exemple.

Corrigé détaillé

Pour un pavage en grille, le côté entier s doit diviser 414 et 662. Son plus grand choix est donc leur PGCD, égal à 2. On peut le retrouver par $662=414+248$ , $414=248+166$ , $248=166+82$ , $166=2\times82+2$ , $82=41\times2$ . Le plus grand côté est 2 cm.
On place $414/2=207$ carrés sur un côté et $662/2=331$ sur l'autre. Le nombre total vaut $207\times331=68517$ . La vérification par les aires donne $414\times662=274068$ cm² et $274068/4=68517$ .
Oui. Un côté de 1/2 cm permet 828 carrés sur la longueur 414 et 1324 sur la longueur 662. Le total est $828\times1324=1096272$ , soit seize fois 68517 puisque le côté a été divisé par 4. Autoriser les rationnels ne crée pas un plus grand côté que 2 pour un pavage en grille, mais permet des côtés arbitrairement petits et donc un nombre de carrés sans borne supérieure. Ici, l'exemple demandé suffit à montrer l'existence de pavages plus fins.

Exercice 13 — Retrouver deux nombres à partir du PGCD et du PPCM

Deux entiers positifs a≤b ont pour PGCD 12 et pour PPCM 420.

Réduire le problème à deux facteurs premiers entre eux.
Déterminer tous les couples (a,b).
Expliquer pourquoi connaître seulement le produit ab ne suffirait pas.

Corrigé détaillé

On pose a=12u et b=12v, avec u≤v et $\mathrm{PGCD}(u,v)=1$ . Le PPCM vaut alors 12uv. La condition 12uv=420 donne uv=35.
Les couples de diviseurs positifs ordonnés de 35 sont (1,35) et (5,7). Ils sont tous deux premiers entre eux. Les couples recherchés sont donc (12,420) et (60,84). Vérifications : pour le second, le PGCD de 60 et 84 est 12 et leur PPCM vaut $(60\times84)/12=420$ ; pour le premier, 12 divise 420, donc les valeurs annoncées sont immédiates.
La relation produit donne $ab=12\times420=5040$ , mais d'autres couples de produit 5040 ont un PGCD différent. Par exemple, (1,5040) a pour PGCD 1. Même après avoir imposé des multiples de 12, la coprimalité de u et v doit être contrôlée. Dans ce cas précis, 35 étant sans facteur carré, ses deux répartitions ordonnées satisfont cette contrainte ; ce n'est pas une propriété générale de tous les produits réduits.

Exercice 14 — Une condition de multiples et une exclusion

Trouver le plus petit entier positif $n$ tel que $n/18$ et $n/30$ soient entiers, mais que $n/42$ ne le soit pas.
Décrire tous les entiers positifs satisfaisant les trois conditions.
Combien y en a-t-il entre $1$ et $1000$ ?

Corrigé détaillé

18=2\times3^2

30=2\times3\times5

: leur PPCM vaut

90

. Les deux premières conditions imposent

n=90k

avec

k\geq1

entier. Comme

42=2\times3\times7

42\mid90k

équivaut à

7\mid15k

, puis à

7\mid k

par Gauss. Pour

k=1

n=90

convient et est minimal. 2. L’ensemble est

\{90k:k\geq1,\ 7\nmid k\}

. 3.

90k\leq1000

donne

1\leq k\leq11

. Seul

k=7

est exclu ; il reste

10

nombres. Le plus grand est

990

Exercice 15 — Approfondissement — Une identité de PGCD pour les puissances

Montrer, pour r≥ $s\geq1$ , que le PGCD de $2^r-1$ et $2^s-1$ est celui de $2^{r-s}-1$ et $2^s-1$ .
En déduire la formule $\mathrm{PGCD}(2^r-1,2^s-1)=2^{\mathrm{PGCD}(r,s)}-1$ .
Calculer le PGCD de $2^{84}-1$ et $2^{30}-1$ .

Corrigé détaillé

L'identité $2^r-1=2^{r-s}(2^s-1)+(2^{r-s}-1)$ montre que remplacer le premier nombre par le reste indiqué ne change pas les diviseurs communs. Si r=s, ce reste est nul et le PGCD est simplement $2^s-1$ .
Lorsque r>s, on peut répéter cette réduction et échanger les exposants pour garder le plus grand en premier. Les exposants suivent exactement l'algorithme d'Euclide par soustractions. Cet algorithme se termine au couple (g,0), où g est le PGCD de r et s. Le PGCD initial est donc celui de $2^g-1$ et $2^0-1$ =0, soit $2^g-1$ . La preuve n'affirme pas que les expressions sont des restes euclidiens à chaque étape ; elle utilise l'invariance des diviseurs communs sous une combinaison.
Pour les exposants, $84=2\times30+24$ , $30=24+6$ , $24=4\times6$ , donc leur PGCD est 6. Le résultat demandé est $2^6-1=63$ . Aucune écriture décimale des deux énormes nombres n'est nécessaire.

Exercice 16 — Approfondissement — Termes consécutifs d'une suite

On définit

F_0

=0,

F_1

=1 et

F_{n+2}=F_{n+1}+F_n

Démontrer que deux termes consécutifs sont premiers entre eux.
Calculer $F_10$ , $F_11$ , $F_12$ et $F_13$ .
Trouver une identité de Bézout entre $F_13$ et $F_12$ .

Corrigé détaillé

L'invariance du PGCD donne $\mathrm{PGCD}(F_{n+2},F_{n+1})=\mathrm{PGCD}(F_n,F_{n+1})$ . En redescendant jusqu'à $F_1$ =1 et $F_0$ =0, on obtient le PGCD 1. On peut aussi présenter cela comme une récurrence sur n.
Les termes successifs à partir de $F_2$ sont 1,2,3,5,8,13,21,34,55,89,144,233. Ainsi $F_10$ =55, $F_11$ =89, $F_12$ =144 et $F_13$ =233.
Euclide donne $233=144+89$ , $144=89+55$ , $89=55+34$ , $55=34+21$ , $34=21+13$ , $21=13+8$ , $13=8+5$ , $8=5+3$ , $5=3+2$ , $3=2+1$ . Une remontée fournit $1=-55\times233+89\times144$ . La vérification numérique est $89\times144=12816$ et $55\times233=12815$ , de différence 1. Cette identité confirme la coprimalité du couple particulier ; la question 1, elle, démontre simultanément la propriété pour tous les couples consécutifs.

Exercice 17 — Des coefficients de Bézout sous contrainte

Déterminer toutes les identités $391u+299v=23$ à coefficients entiers.
Trouver celle pour laquelle u appartient à [0,12].
Parmi toutes les solutions, déterminer celle qui minimise la valeur absolue de u.

Corrigé détaillé

On a $391=299+92$ , $299=3\times92+23$ et $92=4\times23$ . Ainsi le PGCD vaut 23, avec $23=299-3(391-299)=-3\times391+4\times299$ . En divisant par 23, l'équation devient $17u+13v=1$ . Toutes les solutions sont $u=-3+13t$ , $v=4-17t$ , où t est entier.
La condition $0\leq-3+13t\leq12$ donne $3\leq13t\leq15$ , donc $t=1$ . On obtient $u=10$ et $v=-13$ . Vérification : $3910-3887=23$ .
Les valeurs possibles de u forment la progression …,-29,-16,-3,10,23,… Le terme de plus petite valeur absolue est -3, correspondant à $t=0$ ; son coefficient associé est $v=4$ . Pour justifier l'unicité, si $t\geq1$ , alors $u\geq10$ ; si $t\leq-1$ , alors $u\leq-16$ . Aucun de ces cas ne peut donner une valeur absolue inférieure ou égale à 3. Les coefficients de Bézout ne sont donc pas uniques, mais une contrainte bien choisie peut en sélectionner un couple.

Exercice 18 — Équation homogène et solutions positives

Résoudre $18x=30y$ dans les entiers.
Donner toutes les solutions strictement positives telles que x+ $y\leq100$ .
Trouver celle qui minimise x+y, puis expliquer pourquoi le couple (30,18) n'est pas minimal.

Corrigé détaillé

En divisant par le PGCD 6, on obtient $3x=5y$ . Comme 3 et 5 sont premiers entre eux, Gauss donne $5\mid x$ et $3\mid y$ . On écrit x=5t ; la substitution impose y=3t. Toutes les solutions sont donc $(x,y)=(5t,3t)$ pour t entier.
La stricte positivité équivaut à $t\geq1$ . La condition sur la somme donne $8t\leq100$ , donc $t\leq12$ . Les solutions sont exactement les douze couples $(5t,3t)$ pour $t=1$ ,2,…,12 ; le dernier est (60,36), dont la somme vaut 96. Pour $t=13$ , la somme vaut 104 et dépasse la borne.
La somme 8t croît avec t sur les entiers positifs. Son minimum est 8, atteint uniquement pour $t=1$ , soit le couple (5,3). Le couple (30,18) correspond à $t=6$ : il satisfait bien l'égalité, puisque les deux produits valent 540, mais il est six fois plus grand que le couple minimal. Réduire d'abord les coefficients par leur PGCD permet de voir immédiatement la solution primitive.

Exercice 19 — Deux synchronisations et une équation de temps

Une première machine émet un signal aux instants 5+12k minutes, une seconde aux instants 11+18l minutes, avec k,l entiers positifs ou nuls.

Traduire une rencontre en équation diophantienne et résoudre celle-ci.
Trouver le premier instant commun positif.
Décrire tous les instants communs et leur espacement.

Corrigé détaillé

Une rencontre vérifie $5+12k=11+18l$ , soit $12k-18l=6$ , puis $2k-3l=1$ . Le couple (k,l)=(2,1) convient. Les solutions entières sont $k=2+3t$ et $l=1+2t$ , avec t entier. En effet, les variations donnent $2\times3t-3\times2t=0$ , et Gauss garantit l'exhaustivité.
Les contraintes $k\geq0$ et $l\geq0$ imposent respectivement $t\geq0$ pour t entier dans les deux cas. Le plus petit paramètre autorisé est donc $t=0$ . L'instant commun vaut $5+12\times2=29$ minutes, également $11+18\times1=29$ . Il n'existe pas de rencontre antérieure compatible avec les indices non négatifs.
En remplaçant k par 2+3t, on obtient les instants $29+36t$ minutes pour $t\geq0$ entier. L'espacement vaut 36 minutes, le PPCM de 12 et 18. Les instants suivants sont 65,101,137,… La différence de phase, 11-5=6, est divisible par le PGCD 6, ce qui explique que la synchronisation soit possible malgré des départs différents.

Exercice 20 — Approfondissement — Une somme fixée et un PGCD imposé

On cherche les entiers positifs a≤b tels que a+

b=180

et que leur PGCD soit 12.

Ramener le problème à deux entiers premiers entre eux de somme 15.
Déterminer tous les couples.
Calculer le PPCM de chaque couple et identifier le plus grand.

Corrigé détaillé

On écrit a=12u et b=12v. La somme donne u+ $v=15$ , avec 1≤u≤v et $\mathrm{PGCD}(u,v)=1$ . Comme $v=15$ -u, le PGCD de u et v est celui de u et 15. Il suffit donc de prendre 1≤ $u\leq7$ et u premier avec 15.
Dans cette plage, les valeurs admissibles sont 1,2,4,7 ; les valeurs 3 et 6 sont divisibles par 3, et 5 par 5. Les couples (u,v) sont (1,14), (2,13), (4,11) et (7,8). Les couples initiaux sont donc (12,168), (24,156), (48,132) et (84,96). Tous ont bien une somme de 180.
Puisque u et v sont premiers entre eux, le PPCM de a et b vaut 12uv. On obtient successivement 168,312,528 et 672. Le plus grand est 672, pour (84,96). On ne pouvait pas simplement choisir (90,90), pourtant équilibré, car son PGCD vaut 90. La contrainte arithmétique doit être traitée avant l'optimisation du produit.

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 min Soutien en Maths expertes