Cours maths Terminale S

Equations diophantiennes

Dans ce module, étude des équations diophantiennes.
Après un bref rappel des résultats d’arithmétique utiles à la résolution de telles équations, la notion d’équation diophantienne est définie.

 

1/ Résultats utiles

Dans les démonstrations à venir, nous aurons besoin de certains résultats vus et démontrés dans le module sur le PGCD.

Rappel :

Soient a et b deux entiers relatifs non nuls.
a et b sont dits premiers entre eux si pgcd (a,b) = 1

 

Théorème de Bézout :

soient a et b deux entiers relatifs non nuls.
a et b sont premiers entre eux
si et seulement si
il existe u et v entiers relatifs tels que : a x u + b x v = 1

De ce théorème découlent les résultats suivants :

Propriété n° 1

pgcd (a,b) = d ⇔ il existe a’ et b’ entiers relatifs tels que : a = da’ et b = db’ avec pgcd (a',b') = 1

 

Théorème de Gauss :

soient a, b et c trois entiers relatifs non nuls.
Si a divise bc et a et b premiers entre eux alors a divise c.

Il est à noter que le théorème de Gauss peut être déduit de celui de Bézout et que cette démonstration est un des R.O.C les plus fréquents au BAC.

 

2/ Equations diophantiennes : définition

Définition :

Toute équation (E) du type : ax +by = c
où a, b et c sont trois entiers relatifs et où les inconnues x et y sont des relatifs
est appelée équation diophantienne.

Remarque :

dans la suite du cours, nous aurons besoin de parler du PGCD de a et de b, donc seul le cas où a et b sont non nuls sera étudié dans ce module.

 

2/ Equations diophantiennes : le cas c = 0

Si c = 0 alors x et y solutions de (E) ⇔ ax + by = 0 ⇔ ax = b(-y)
Donc si x et y sont solutions de (E) alors a divise b(-y)

Sous cas n° 1 : a et b sont premiers entre eux.

a divise b(-y) et a est premier avec b donc d’après le théorème de Gauss :
a divise (–y) et par conséquent, il existe k entier relatif tel que : -y = ka.
d'où ax = b (-y) ⇔ ax = bka
⇔ = kb car a est nul

Si x et y solutions de (E), il existe alors k entier relatif tel que :

Réciproque :
Soient x et y s’écrivant x = kb et y = -ka.
alors : ax = akb et b(-y) = bka.
donc ax = -by
d'où ax + by = 0
x et y sont solutions de (E)

Conclusion : les couples solutions de (E) sont les couples ( kb, -ka ) avec k entier relatif.

Sous cas n° 2 : a et b ne sont pas premiers entre eux.

Soit d = pgdc (a,b)

Il existe a’ et b’ premiers entre eux tels que : a = da’ et b = db’
Et alors : ax = b (-y) ⇔ da' x = db' (-y)
⇔ a'x = b'(-y) car d non nul
On retombe alors sur le sous cas n°1

Et donc : les couples solutions de (E) sont les couples ( kb’, -ka’ ) avec k entier relatif.

Il est à retenir de l’étude de ce cas c = 0 :
- la technique pour se ramener au sous cas n°1.
- la technique d’utilisation du théorème de Gauss.
- la nécessité de montrer la réciproque pour pouvoir conclure sur l’ensemble des solutions.
- l’existence d’une infinité de solutions

 

2/ Equations diophantiennes : existence de solutions

La suite du cours va être gérée comme l’étude générale d’une équation diophantienne.

A savoir : l’équation a-t-elle des solutions ? Si oui, combien et comment les trouver ?

Étape n° 1 : A quelle condition (E) admet-elle au moins une solution ?

Si (E) admet au moins une solution alors il existe u et v entiers relatifs tels que : au + bv = c

Soit d = pgcd (a,b)
d divise a et b donc d divise tout combinaison linéaire de a et de b.
Par conséquent d divise c.

Une condition nécessaire à l’existence d’au moins une solution est donc :
que le PGCD de a et de b divise c.
Cette condition est-elle suffisante ?

Supposons que d divise c.
Il existe alors k entier relatif tel que c = kd
d = pgcd (a,b) donc il existe a’ et b’ premiers entre eux tels que : a = da’ et b = db’.

Et d’après le sens direct du théorème de Bézout, alors il existe u et v tels que : a'u' + b'v' = 1
d'où : kda'u' + kdb'v' = kd Soit : aku' + bkv' = c

En posant : u = ku' et v = kv' qui sont tous deux des relatifs,
nous obtenons que l’équation admet alors au moins une solution.

La condition est donc suffisante.

Conclusion : condition nécessaire et suffisante d’existence s’une solution :

L’ équation (E) : ax + by = c admet au moins une solution
si et seulement si
le PGCD de a et de b divise c.

Remarques :

1) La première chose à faire est évidemment de calculer le PGCD de a et de b.

2) Si a et b sont premiers entre eux, (E) admet des solutions quel que soit c.

3) Si c = 0, tout nombre divisant 0, (E) admet des solutions, comme vu précédemment.

 

2/ Equations diophantiennes : solution particulière

En supposant que l’équation admette au moins une solution,
essayons maintenant d’en trouver au moins une.

Étape n° 2 : Recherche d’une solution particulière.

Deux cas de figure sont possibles :
* Soit la solution particulière est donnée par le texte
et il ne reste qu’à vérifier qu’elle est bien solution de (E).

* Soit il faut la trouver par soi-même.
- Soit il y a alors une solution particulière évidente.
- Soit il faut trouver cette solution par le calcul et ce « en remontant » l’algorithme d’Euclide.
Prenons un exemple concret : (E) : 616x + 585y = 12

616 = 585 x 1 + 31 Le dernier reste non nul est 1 donc pgcd (616,585) = 1

585 = 31 x 18 +27
31 = 27 x 1 + 4 1 divise 12 donc ce qui est certain
c’est que l’équation a des solutions.

27 = 4 x 6 + 3
4 = 3 x 1 + 1 Voici maintenant la technique à adopter
pour remonter la suite de divisions.

Et vue la probabilité de se tromper dans ce genre de manipulation,
il est conseillé de vérifier le résultat trouvé :

En effet, la calculatrice confirme que : 616 x 1812 + 585 x (-1908) =12

Une solution particulière de (E) est donc le couple ( 1812 ; -1908 )

 

2/ Equations diophantiennes : solution générale

Étape n° 3 : Recherche de l’ensemble des solutions.

Supposons que nous ayons trouvé le couple ( u ; v ) comme solution particulière de (E).
Le couple ( u, v ), vérifie donc : au + bv = c
on a alors : x et y solutions de (E)
⇔ ax + by = au + bv
⇔ a(x - u) + b(y - v) = 0
⇔aX + bY = 0 avec X = x - u et Y = y - v

Et l’on retombe donc sur le cas c = 0 étudié plus haut, genre d’équation que l’on sait résoudre.
Et d’après l’étude qui en a été faite, on peut affirmer que si l’équation (E) possède au moins une solution dans , alors elle en possède une infinité dans .

Voyons cependant sur notre exemple comment rédiger la fin de la résolution.

(E) 616x + 585y = 12 a pour solution particulière le couple ( 1812 ; -1908 ).
Donc 616x + 585y = 12 ⇔ 616x + 585y = 616 x 1812 + 585 x (-1908)
⇔ 616(x - 1812) = 585x (-y - 1908)

Donc si x et y solutions de (E) alors 616 divise 585x (-y - 1908)
Or 616 est premier avec 585
donc d’après le théorème de Gauss : 616 divise (-y -1908)

Il existe donc un entier relatif k tel que : -y -1908 = 616k

D’où : 616(x - 1812) = 585 x 616k
Et donc : x - 1812 = 585k

si x et y sont solutions de (E), il existe donc un entier relatif k tel que :

Réciproque :

Soient x et y s’écrivant 1812 + 585k et y = -1908 - 616k avec k entier relatif.

616x + 585 x y = 616 x (1812 + 585k) + 585 (- 1908 - 616k)
= 616 x 1812 + 585 x (-1908) + 616 x 585k - 585 x 616k = 12

Conclusion : les couples solutions de (E) sont les couples avec k entier relatif.

 

2/ Equations diophantiennes : nombre de solutions

Étape n° 4 : Recherche de solutions spécifiques.

Même si (E) a une infinité de solutions dans ℤ , le contexte de l’exercice peut obliger à en éliminer certaines.

Il se peut donc parfois qu’il faille faire une étape de plus qui consiste à sélectionner les solutions respectant des contraintes imposées.

Ce sera le cas en particulier si la résolution d’une équation diophantienne doit apporter une réponse à un problème concret.

Si par exemple dans l’équation : (E) : 616x + 585y = 12
x et y sont des entiers naturels représentant des nombres de tours de piste.

Alors x > 0 et k doit donc vérifier : 1812 + 585k > 0
Soit : Or :

k étant entier, il doit donc vérifier : k > −3
De même avec la contrainte y ≥ 0 , on obtient : −1908 − 616k > 0
Soit : Or
Il faut donc également : k > −4
Aucun k ne pouvant respecter ces deux contraintes, le problème n’a pas de solution.

 

3/ Bilan pratique

Nous allons maintenant à partir d’un exemple, essayer de faire le tour des stratégies à adopter
en fonction des situations et des questions qui peuvent être posées dans un exercice.

Pour ce faire prenons l’exemple de (E) : 1462x - 408y =136
* Quelles que soient les questions à venir, commencer par regarder si l’équation peut être simplifiée de façon évidente.

Ici, c’est la cas, on peut simplifier l’équation par 2.
(x ; y ) solution de (E) ⇔ (x ; y ) solution de (E’) : 731x - 204y = 68

1° Si la question est : « L’équation admet-elle des solutions ? »

► Il faut alors trouver le pgcd de 731 et (-204), autrement dit le pgcd de 731 et 204.
► Il y a au moins 3 façons de trouver ce pgcd.

Si cette question n’a pas de suite, comme par exemple dans un QCM, les 3 méthodes de recherche du pgcd se valent.
Sinon, il est conseillé d’utiliser l’algorithme d’Euclide.

►Une fois le pgcd trouvé, soit il divise 68 et (E) a des solutions soit il ne divise pas 68 et (E) n’a pas de solution.

Rappel de (E’) : 731x - 204y = 68

Utilisons l’algorithme d’Euclide :


Le pgcd de 731 et 204 est donc 17.
68 = 4 x 17
17 divise 68, l’équation a donc des solutions.

2° Si la question à suivre est : « Donner une solution particulière de (E) » ou encore « Résoudre (E) ».

La première question que l’on se pose souvent est :
« A-t-on intérêt à simplifier l’équation par le pgcd ? »

Auquel cas elle deviendrait (E’’) : 43x -12y = 4

Cette opération comporte des avantages et un inconvénient.

Son premier avantage est que 43 et 12 sont premiers entre eux,
ce qui pourra éviter des erreurs dans la résolution à suivre

Son deuxième avantage est que l’équation étant plus simple,
il est alors plus facile de trouver une solution particulière évidente.

Son troisième avantage est que si le pgcd a été trouvé autrement qu’avec l’algorithme d’Euclide,
l’algorithme d’Euclide qu’il faut maintenant faire en cas d’absence de solution évidente,
est plus court à remonter.

Enfin le seul inconvénient, c’est que s’il n’y a pas de solution évidente et que l’on a déjà
fait une première fois l’algorithme d’Euclide, cela oblige à le refaire.

Rappel de (E’’) : 43x - 12y = 4
Il n’ y a pas de solution évidente, revenons donc à (E’) : 731x - 204y = 68
et remontons notre algorithme :

D'où 731 x (-5) - 204 x (-18) = 17

Il reste alors à multiplier l’équation par 68/17, c’est à dire 4 : 731 x(-20) - 204 x (-72) = 68
Attention : avant conclure regardez si cette égalité est vraie
Le couple ( -20 ; -72 ) est donc une solution particulière de ( E ).

Rappel de (E) : 1492x - 408y = 136

1° et 2° bis
Si la première question posée est : « Monter que le couple ( -20 ; -72 ) est solution de (E). »
On vérifie simplement que : 1462x (-20) + 408x (-72) = 136
Nous en sommes alors au même point qu’avec les questions précédentes, à ceci près que nous n’avons calculé aucun pgcd.

3° Quel qu’ait été notre cheminement jusqu’à une solution particulière, arrive alors la question finale : « Résoudre ( E ) ».

Dans tous les cas :
il faut remplacer le membre de droite par la combinaison
que représente la solution particulière puis manipuler l’équation,
en ne laissant aucun signe sur les coefficients,
afin de faciliter la résolution.

 

 

Exemple : 1462x - 408y = 1462x (-20) - 408x (-72) ⇔ 1462 (x + 20) = 408x (y +72)

Situation n° 1 : les coefficients sont premiers entre eux,

soit parce que nous avions simplifié l’équation en divisant par le pgcd,
soit en raison des données initiales de l’exercice.

Situation n° 2 : les coefficients ne sont pas premiers entre eux.

Il faut alors simplifier l’équation par leur pgcd
sinon on ne peut pas appliquer le théorème de Gauss.

Appliquer le théorème de Gauss à des nombres non premiers entre eux est l’erreur n° 1 chez les élèves.

Dans le cas d’une solution donnée par le texte, il faut donc tout de même trouver le pgcd.

Revenons au cas où nous avions nous-même trouvé une solution particulière.
Reprenons par exemple (E’) : 731x - 204y = 68
⇔ 731x - 204y = 731x (-20) - 204x (-72)
⇔ 731(x + 20) = 204(y + 72)


On simplifie par 17 :
⇔ 43(x + 20) = 12(y + 72)
• 17 étant le pgcd de 731 et 204, on est certain que 43 et 12 sont premiers entre eux.
• 43 divise 12(y+72) et 43 premier avec 12 donc d’après le théorème de Gauss,
• 43 divise y+72.

D’où, il existe k entier relatif tel que : y+72 = 43k.
Inutile alors, comme font certains livres, de réutiliser Gauss avec 12.

Rappel : (E) ⇔43 (x + 20) = 12(y + 72)
y + 72 = 43k donc 43 (x+20) = 12x 43k et par conséquent : x + 20 = 12k.

Les couples solutions sont donc du type ( -20+12k ; -72 + 43k ).

Ne pas oublier de vérifier la réciproque et conclure.

Enfin, un dernier conseil, prendre une valeur simple pour k, et tester si le couple correspondant est bien solution de (E).