Résoudre une équation diophantienne du premier degré

Par Zauctore

Voici un document à l'attention des TS spé math sur la résolution en nombres entiers des équations de la forme ax+by=cax + by = caa, bb, cc sont eux aussi des entiers.

On suppose connus pour cela les principaux résultats d'arithmétique que sont les théorèmes de Gauss et de Bachet-Bézout.

Note :
La méthode employée ici est plus classique que celle d'Euler dont j'ai donné les rudiments dans cet autre article.

Résumé

Soient aa, bb, cc trois entiers. Résoudre l’équation diophantienne

ax+by=cax + by = c

consiste à déteminer toutes les paires de nombres entiers xx et yy qui en sont solution.

Dans la suite, on étudie d’abord un exemple particulier
avant de considérer le problème en toute généralité.

On suppose connus la division euclidienne, les notions de pgcd et de nombres premiers entre eux, les théorèmes de Bachet et de Gauss.

§ 1. Résolution d’une équation particulière.

Considérons l’équation
(1)(1) 7x+12y=5.7x + 12y = 5.

Il est clair que x=1x = -1 et y=1y = 1 est une solution de cette équation puisque

(2)(2) 7×(1)+12×1=57 \times (-1) + 12 \times 1 = 5.

Pour éliminer le terme constant 55, soustrayons (1)(1) et (2)(2) :

7(x+1)+12(y1)=07(x + 1) + 12(y - 1) = 0.

On en déduit que :

(3)(3) 7(x+1)=12(1y)7(x + 1) = 12(1 - y)

où tous les nombres en jeu sont entiers.

Les nombres 77 et 1212 étant premiers entre eux, on voit 11 ainsi que 77 divise (1y)(1 − y) et que 1212 divise (x+1)(x + 1).

Remarque : C’est le théorème de Gauss : si aa divise bcbc, et si aa est premier avec bb, alors aa divise nécessairement cc.

Il doit donc exister deux entiers kk et kk' tels que
x+1=12kx + 1 = 12k et 1y=7k1 - y = 7k'.

Alors, l’égalité (3)(3) devient 7×12k=12×7k7 \times 12k = 12 \times 7k'.

Ceci montre que k=kk = k'.
Donc pour un certain entier kk, on a : x+1=12kx + 1 = 12k et 1y=7k1 − y = 7k.

C’est-à-dire que si xx et yy sont solution de l’équation (1)(1), alors :

x=1+12kx = -1 + 12k et y=17ky = 1 - 7k pour un certain kZ.k \in \mathbb{Z}.

Réciproquement, on voit que :

7×(1+12k)+12×(17k)=7+84k+1284k=57\times (-1 + 12k) + 12 \times (1 - 7k) = -7 + 84k + 12 - 84k = 5.

Les solutions sont donc exactement les couples
(4)(4) (x=1+12kx = -1 + 12k ; y=17ky = 1 - 7k), kZk \in \mathbb{Z}.

Exercice 1.

Résoudre l’équation 13x8y=2113x - 8y = 21 en remarquant qu’une solution particulière est donnée par x=1x = 1, y=1y = -1.

§ 2. Généralisation.

L’exemple précédent laisse penser que la connaissance
d’une solution particulière détermine toutes les autres en fonction des coefficients de l’équation.

Ceci est parfaitement général, moyennant une condition sur les
coefficients.

Propriété 1 :

Soient aa et bb deux nombres premiers entre eux.

Soit (x0;y0)(x_0 ; y_0) une solution particulière de l’équation ax+by=cax + by = c.

Alors elle possède une infinité de solutions qui sont toutes données par (x=x0+bkx = x_0 + bk ; y=y0ak)y = y_0 - ak), kZk \in \mathbb{Z}.

Démonstration.

La démarche suit exactement l’exemple de la résolution de l’équation (1)(1).

On suppose que ax0+by0=cax_0 + by_0 = c.

Si xx, yy est une autre solution de l’équation, alors on a :

ax+by=cax + by = c

et par différence

a(xx0)+b(yy0)=0a(x - x_0) + b(y - y_0) = 0,

c’est-à-dire

a(xx0)=b(y0y)a(x - x_0) = b(y_0 - y).

C’est ici que le fait que aa et bb sont premiers entre eux intervient de façon cruciale : avec le théorème de Gauss, on en déduit que aa est un diviseur de (y0y)(y_0 - y) et que bb est un diviseur de (xx0)(x - x_0).

On peut donc écrire, pour deux entiers kk et kk' convenables

xx0=bkx - x_0 = bk et y0y=aky_0 - y = ak'.

Donc l’égalité a(xx0)=b(y0y)a(x - x_0) = b(y_0 - y) devient
abk=bakabk = bak'
ce qui montre que k=kk = k'.

On en déduit finalement que, pour un certain kk entier

x=x0+bkx = x_0 + bk et y=y0aky = y_0 - ak.

Il reste à vérifier réciproquement que de telles combinaisons fournissent des solutions de l’équation initiale :

a(x0+bk)+b(y0ak)=ax0+by0c+abkbak=ca(x_0 + bk) + b(y_0 - ak) = \underbrace{ax_0 + by_0}_c + abk- bak = c, ce qui achève la démonstration.
On peut se demander à quelle condition il est possible de trouver une solution particulière.

Propriété 2.

Soit d=pgcd(a;b)d = pgcd (a ; b). L’équation ax+by=cax + by = c possède des
solutions si et seulement si dd divise le terme constant cc.
En particulier, l’équation ax+by=1ax + by = 1 admet des solutions si et seulement si aa et bb sont premiers entre eux.

Démonstration.

Supposons que (x0;y0)(x_0 ; y_0) soit une solution de l’équation ; alors dd divise bien entendu ax0+by0ax_0+by_0 et dans ce cas, d divise c=ax0+by0c = ax_0+by_0.

Réciproquement, supposons qu’il existe uu tel que c=duc = du. On sait d’après le théorème de Bachet ( il concerne les nombres entiers ; Bezout a étendu ce résultat aux polynômes) qu’on peut trouver deux entiers x1x_1, y1y_1 tels que ax1+by1=dax_1 + by_1 = d.

En multipliant par uu, on obtient ax1u+by1u=duax_1u + by_1u = du c’est-à-dire l’existence de xx et yy tels que ax+by=cax + by = c.

D’après cette propriété, il est inutile d’espérer trouver des entiers xx et yy qui soient solution de l’équation 21x+12y=5021x + 12y = 50 puisque pgcd (21;12)=3(21 ; 12) = 3 et 5050 n’est pas divisible par 33.

§ 3. Obtention d’une solution particulière.

L’expérimentation peut permettre de trouver rapidement une solution particulière d’une équation diophantienne du premier degré.

Par exemple, pour l’équation 7x+5y=27x + 5y = 2, il est facile de voir (dans les tables!) que les nombres 4242 et 40-40 conviennent, c’est-à-dire que x=6x = 6 et y=8y = -8 conviennent.

De façon plus générale, c’est la « remontée » des égalités de l’algorithme d’Euclide qui fournit une relation de Bachet entre les entiers aa et bb : on peut toujours trouver explicitement deux entiers xx, yy tels que ax+by=pgcd(a;b)ax + by = pgcd (a ; b).

Exemple.

Pour résoudre l’équation diophantienne,
(5)217x+34y=2(5) 217x + 34y = 2

on cherche le pgcd des nombres 217217 et 3434.

L’algorithme d’Euclide donne :

217=34×6+13217 = 34 \times 6 + 13
34=13×2+834 = 13 \times 2 + 8
13=8×1+513 = 8 \times 1 + 5
8=5×1+38 = 5 \times 1 + 3
5=3×1+25 = 3 \times 1 + 2
3=2×1+13 = 2 \times 1 + \boxed{1}
2=1×22 = 1 \times 2.

On part du pgcd 11 et on « remonte » en
remplaçant les restes successifs :

1=32×11 = 3 - 2 \times 1
=3(53×1)= 3 - (5 - 3 \times 1)
=3×25= 3 \times 2 - 5
=(85×1)×25= (8 - 5 \times 1) \times 2 - 5
=8×25×3= 8 \times 2 - 5 \times 3
=8×2(138×1)×3= 8 \times 2 - (13 - 8 \times 1) \times 3
=8×513×3= 8 \times 5 - 13 \times 3
=(3413×2)×513×3= (34 - 13 \times 2) \times 5 - 13 \times 3
=34×513×13= 34 \times 5 - 13 \times 13
=34×5(21734×6)×13= 34 \times 5 - (217 - 34 \times 6) \times 13

d’où la relation cherchée

34×83217×13=1\boxed{34 \times 83 - 217 \times 13 = 1}

Ainsi, x=13x = -13 et y=83y = 83 forment une solution de l’équation 217x+34y=1217x + 34y = 1.

Une solution particulière de l’équation (5)(5) est x=26x = -26, y=166y = 166 :

217×(26)+34×166=2217 \times (-26) + 34 \times 166 = 2.

Puisque les coefficients de xx et yy sont premiers entre eux, on en déduit que toutes les solutions de cette équation sont données par (x=26+34k;y=166217k)(x = -26 + 34k ; y = 166 - 217k), kZk \in \mathbb{Z}.

Exemple.

Pour l’équation
(6)544x944y=160(6) 544x - 944y = 160

On cherche d’abord le pgcd des nombres 944944 et 544544.

L’algorithme d’Euclide donne :

944=544×1+400944 = 544 \times 1 + 400
544=400×1+144544 = 400 \times 1 + 144
400=144×2+112400 = 144 \times 2 + 112
144=112×1+32144 = 112 \times 1 + 32
112=32×3+16112 = 32 \times 3 + \boxed{16}
32=16×232 = 16 \times 2

Le pgcd est 1616 ; il divise le terme constant 160160.

On simplifie les coefficients de l’équation (6)(6), qui devient de façon équivalente

(7)34x59y=10(7) 34x - 59y = 10, les coefficients 3434 et 5959 étant maintenant premiers entre eux.

Après quelques calculs (toujours en remontant l’algorithme d’Euclide), on obtient une relation de Bachet :
15×5934×26=115 \times 59 - 34 \times 26 = 1.

L’équation (7)(7) admet donc la solution particulière x=260x = -260, y=150y = -150.

On en déduit toutes les solutions de (7)(7), et donc de (6)(6) :
(x=260+59k;y=150+34k)(x = -260 + 59k ; y = -150 + 34k), kZk \in \mathbb{Z}.

§ 4. Méthode.

De façon générale, pour résoudre une équation diophantienne
ax+by=cax + by = c, la démarche consiste à :

1. déterminer le pgcd dd des coefficients aa et bb et s’assurer qu’il divise le terme constant cc,
2. diviser les coefficients de l’équation par dd, pour former l’équation équivalente ax+by=ca'x + b'y = c', avec aa', bb' premiers entre eux,
3. en déterminer une solution particulière x0x_0, y0y_0, puis toutes les solutions avec x=x0+bkx = x_0 + b'k, y=y0aky = y_0 - a'k, pour tout kZk \in \mathbb{Z},

Remarque :
C’est la troisième étape qui est la plus délicate, demandant la remontée de l’algorithme d’Euclide ou l’obtention « à vue » d’une solution particulière.

Exercice 2.

Trouver une solution particulière puis résoudre chacune des équations diophantiennes suivantes.

(8)(8) 65x+104y=2665x + 104y = 26

(9)(9) 56x21y=10556x - 21y = 105

(10)(10) 14x+20y=714x + 20y = 7.

Toutes nos vidéos sur résoudre une équation diophantienne du premier degré


Posez vos questions

D'autres interrogations sur ce cours ? Démarrez une discussion et obtenez des réponses à des exercices pratiques.

Accéder au forum