Le coin des amatheurs version 2
Les équations diophantiennes sont des équations dont les coefficients et les solutions recherchées sont des entiers. Les plus simples sont les équations de la forme ax + by = c (a, b et c entiers) dont les couples solutions (x ; y) doivent être composés de nombres entiers. Par exemple, l'équation 7x - 3y = 6 a pour solutions les couples (3k + 3 ; 7k + 5) où k est un entier. Des exemples de ces couples sont : (3 ; 5) si k = 0, (9 ; 19) si k = 2 ou (-6 ; -16) si k = -3.
Il est important de noter que, d'après un théorème du à Bézout, l'équation ax + by = c ne peut admettre des solutions entières que si le PGCD de a et b est un diviseur de c.
Par exemple : 7x - 5y = 9 admet des solutions car PGCD (7 ; -5) = 1
3x - 2y = 0 admet des solutions car PGCD (3 ; -2) = 1
8x + 4y = 1 n'admet aucune solution car PGCD (8 ; 4) = 4, qui ne divise pas 1
8x + 4y = 12 admet des solutions car PGCD (8 ; 4) = 4, qui divise 12
Dans le dernier cas (le PGCD est différent de 1 mais divise c), on divise l'équation par le PGCD (dans le dernier exemple, on obtient 2x + y = 3) car la méthode décrite ci-dessous ne fonctionne que si PGCD (a ; b) = 1.
Résolution de l'équation :
Dans cette méthode générale, on suppose que PGCD (a ; b) = 1, c'est-à-dire que a et b sont premiers entre eux.
1) Il est nécessaire de démontrer d'abord un autre théorème : le théorème de Gauss. Il dit que si a divise bc et que a est premier avec b, alors a divise c (par exemple, 2 divise 4 x 5 et 2 est premier avec 5 donc 2 divise 4).
En effet, a est premier avec b donc il existe deux entiers u et v tels que au + bv = 1 (c'est une conséquence du théorème de Bézout que je ne démontrerai pas ici). On a donc aussi acu + bcv = c. Or a divise bc donc bc = ka avec k
entier. En remplaçant dans la relation précédente, on a acu + kav = c ou a(cu + kv) = c. Comme cu + kv est un entier, a divise c.
2) Résolvons à présent ax + by = c. La première chose à faire, c'est de trouver une solution particulière qu'on appellera (x0 ; y0). Une fois cette solution trouvée (voir ci-dessous), on peut trouver l'ensemble des solutions :
ax + by = c et ax0 + by0 = c donc a(x - x0) + b(y - y0) = 0 donc a(x - x0) = -b(y - y0).
Or (x - x0) est entier donc a divise -b(y - y0). Par hypothèse, a et b sont premiers entre eux donc a et -b sont premiers entre eux. D'après le théorème de Gauss, on en déduit que a divise (y - y0). Autrement dit, (y - y0) = ka avec k entier ou y = ka + y0. En remplaçant dans a(x - x0) = -b(y - y0), on a : a(x - x0) = -bka d'où x - x0 = -bk puis x = x0 - bk.
Dans ce raisonnement, on a montré que les couples doivent être de la forme (x0 - bk ; ka + y0) mais pas que tous ces couples conviennent. Nous le faisons donc à présent :
a(x0 - bk) + b(ka + y0) = ax0 + by0 = c.
Les solutions de l'équation ax + by = c avec x et y entiers sont l'ensemble des couples (x0 - bk ; ka + y0) avec k entier.
Etudions une équation spéciale : c = 0, soit l'équation ax + by = 0. On a une solution particulière évidente : (0 ; 0). Donc x0 = 0 et y0 = 0. Les solutions sont donc l'ensemble des couples (-bk ; ka) avec k entier.
Trouver une solution particulière :
Pour ceci, on peut utiliser l'algorithme d'Euclide qui calcule le PGCD de a et b. Il suffit d'écrire l'algorithme, comme on le fait habituellement, jusqu'à obtenir le PGCD. S'il vaut 1, on peut alors renverser les égalités en remontant les calculs pour exprimer 1 en fonction de a et b (voir les exemples). S'il est différent de 1 (et ne divise pas c) : il n'y a pas de solution !
Exemple 1 : résoudre 27y + 45z = 3
Calculons le PGCD de 27 et 45 :
45 = 27 + 18
27 = 18 + 9
18 = 2x9 + 0
Le PGCD de 27 et 45 est alors 9. Mais 9 ne divise pas 3, donc il n'y a aucune solution à cette équation !
Exemple 2 : résoudre 155y + 217z = 31
217 = 155 + 62
155 = 2x62 + 31
62 = 2x31 + 0
Le PGCD de 217 et 155 vaut 31, qui est égal à c : il y a des solutions. Utilisons les calculs déjà faits pour exprimer 31 en fonction de 217 et 155 :
31 = 155 - 2x62 = 155 - 2x(217 - 155) = 155 - 2x217 + 2x155 = 3x155 - 2x217.
On divise alors l'équation et la relation précédente par le PGCD 31 : 5y + 7z = 1, et on sait que 1 = 3x5 - 2x7.
L'équation devient alors 5y + 7z = 3x5 - 2x7, soit en regroupent les termes : 5(y-3) = 7(-z-2).
Alors 5 est un diviseur de 7(-z-2). 5 et 7 sont premiers entre eux donc, d'après le théorème de Gauss, 5 est un diviseur de -z-2. Il existe un entier k tel que -z-2 = 5k, soit z = -5k-2.
Remplaçons alors dans 5(y-3) = 7(-z-2) : on a 5(y-3) = 7(5k) d'où y-3 = 7k et y = 7k+3.
Les solutions de l'équation 155y + 217z = 31 sont tous les couples (7k+3,-5k-2) avec k entier.
Exemple 3 : résoudre 147y + 231z = 294, où y et z doivent être des entiers positifs
231 = 147 + 84
147 = 84 + 63
84 = 63 + 21
63 = 3x21 + 0
Le PGCD de 231 et 147 vaut 21, qui divise 294 : il y a des solutions. Utilisons les calculs déjà faits pour exprimer 294 en fonction de 231 et 147 :
21 = 84 - 63 = 84 - (147 - 84) = 84 - 147 + 84 = 2x84 - 147 = 2x(231 - 147) - 147 = 2x231 - 3x147.
Il reste à multiplier par 14 : 294 = 28x231 - 42x147.
On divise alors l'équation et la relation précédente par le PGCD 21 : 7y + 11z = 14, et on sait que 14 = 28x11 - 42x7.
L'équation devient alors 7y + 11z = 28x11 - 42x7, soit en regroupent les termes : 7(y+42) = 11(-z+28).
Alors 7 est un diviseur de 11(-z+28). 7 et 11 sont premiers entre eux donc, d'après le théorème de Gauss, 7 est un diviseur de -z+28. Il existe un entier k tel que -z+28 = 7k, soit z = -7k+28.
Remplaçons alors dans 7(y+42) = 11(-z+28) : on a 7(y+42) = 11(7k) d'où y+42 = 11k et y = 11k-42.
Les solutions de l'équation 147y + 231z = 294 sont les couples (11k-42,-7k+28) avec k entier. Mais ici, on a en plus la condition que y et z doivent être positifs. Ainsi 11k-42 ≥ 0, soit 11k ≥ 42 d'où k ≥ 42/11. Ainsi, k ≥ 3,82 et comme k est entier, k ≥ 4. On doit aussi avoir -7k+28 ≥ 0 soit -7k ≥ -28 d'où k ≤ 28/7. Ainsi k ≤ 4 et on doit avoir k = 4. L'unique solution est (11x4-42,-7x4+28) soit (2,0).