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 = c$ où $a$, $b$, $c$ 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 $a$, $b$, $c$ trois entiers. Résoudre l’équation diophantienne

consiste à déteminer toutes les paires de nombres entiers $x$ et $y$ 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)$ $7x + 12y = 5.$

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

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

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

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

On en déduit que :

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

où tous les nombres en jeu sont entiers.

Les nombres $7$ et $12$ étant premiers entre eux, on voit $1$ ainsi que $7$ divise $(1 − y)$ et que $12$ divise $(x + 1)$.

Remarque : C’est le théorème de Gauss : si $a$ divise $bc$, et si $a$ est premier avec $b$, alors $a$ divise nécessairement $c$.

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

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

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

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

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

Réciproquement, on voit que :

$7\times (-1 + 12k) + 12 \times (1 - 7k) = -7 + 84k + 12 - 84k = 5$.

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

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

Démonstration.

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

On suppose que $ax_0 + by_0 = c$.

Si $x$, $y$ est une autre solution de l’équation, alors on a :

$ax + by = c$

et par différence

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

c’est-à-dire

$a(x - x_0) = b(y_0 - y)$.

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

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

$x - x_0 = bk$ et $y_0 - y = ak'$.

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

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

$x = x_0 + bk$ et $y = y_0 - ak$.

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

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

Démonstration.

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

Réciproquement, supposons qu’il existe $u$ tel que $c = 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 $x_1$, $y_1$ tels que $ax_1 + by_1 = d$.

En multipliant par $u$, on obtient $ax_1u + by_1u = du$ c’est-à-dire l’existence de $x$ et $y$ tels que $ax + by = c$.

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

§ 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 = 2$, il est facile de voir (dans les tables!) que les nombres $42$ et $-40$ conviennent, c’est-à-dire que $x = 6$ et $y = -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 $a$ et $b$ : on peut toujours trouver explicitement deux entiers $x$, $y$ tels que $ax + by = pgcd (a ; b)$.

Exemple.

L’algorithme d’Euclide donne :

$217 = 34 \times 6 + 13$
$34 = 13 \times 2 + 8$
$13 = 8 \times 1 + 5$
$8 = 5 \times 1 + 3$
$5 = 3 \times 1 + 2$
$3 = 2 \times 1 + \boxed{1}$
$2 = 1 \times 2$.

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

$1 = 3 - 2 \times 1$
$= 3 - (5 - 3 \times 1)$
$= 3 \times 2 - 5$
$= (8 - 5 \times 1) \times 2 - 5$
$= 8 \times 2 - 5 \times 3$
$= 8 \times 2 - (13 - 8 \times 1) \times 3$
$= 8 \times 5 - 13 \times 3$
$= (34 - 13 \times 2) \times 5 - 13 \times 3$
$= 34 \times 5 - 13 \times 13$
$= 34 \times 5 - (217 - 34 \times 6) \times 13$

d’où la relation cherchée

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

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

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

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

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

Exemple.

L’algorithme d’Euclide donne :

$944 = 544 \times 1 + 400$
$544 = 400 \times 1 + 144$
$400 = 144 \times 2 + 112$
$144 = 112 \times 1 + 32$
$112 = 32 \times 3 + \boxed{16}$
$32 = 16 \times 2$

Le pgcd est $16$ ; il divise le terme constant $160$.

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

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

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

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

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

§ 4. Méthode.

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

1. déterminer le pgcd $d$ des coefficients $a$ et $b$ et s’assurer qu’il divise le terme constant $c$,
2. diviser les coefficients de l’équation par $d$, pour former l’équation équivalente $a'x + b'y = c'$, avec $a'$, $b'$ premiers entre eux,
3. en déterminer une solution particulière $x_0$, $y_0$, puis toutes les solutions avec $x = x_0 + b'k$, $y = y_0 - a'k$, pour tout $k \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.

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