Équations du type $ax + by = c$

Dans cette leçon, $a$ et $b$ sont des entiers naturels non nuls, $c$ est un entier naturel, et l'on cherche les couples $(x\,;y)$ d'entiers relatifs tels que $a\,x + b\,y = c$. C'est la compétence exigible du programme : « résoudre dans $\mathbb{Z}$ des équations du type $ax + by = c$ où $a$, $b$ et $c$ sont des entiers naturels ».

5.1 Existence de solutions

Théorème. Soit $d = \mathrm{PGCD}(a\,;b)$. L'équation $a\,x + b\,y = c$ a des solutions dans $\mathbb{Z}^2$ si, et seulement si, $d$ divise $c$.

Démonstration.

• Si $(x\,;y)$ est une solution, $d$ divise $a$ et $b$, donc il divise $a\,x + b\,y = c$.
• Réciproquement, si $c = d\,k$, l'identité de Bézout donne $u$ et $v$ tels que $a\,u + b\,v = d$ ; alors $a\,(u\,k) + b\,(v\,k) = d\,k = c$.

Exemple 24. $84\,x + 30\,y = 10$ n'a aucune solution entière : $\mathrm{PGCD}(84\,;30) = 6$ ne divise pas $10$. En effet, le membre de gauche est toujours un multiple de $6$.

5.2 Méthode de résolution

1. Simplifier. On calcule $d = \mathrm{PGCD}(a\,;b)$. Si $d$ ne divise pas $c$, il n'y a pas de solution. Sinon, on divise par $d$ : $a'\,x + b'\,y = c'$, avec $a'$ et $b'$ premiers entre eux.
2. Trouver une solution particulière $(x_0\,;y_0)$, à vue ou par la remontée de l'algorithme d'Euclide (on trouve $a'\,u + b'\,v = 1$, puis on multiplie par $c'$).
3. Soustraire et appliquer Gauss. Si $(x\,;y)$ est une solution, on soustrait $a'\,x_0 + b'\,y_0 = c'$ : $a'\,(x - x_0) = b'\,(y_0 - y).$ $a'$ divise $b'\,(y_0 - y)$ et $a'$ est premier avec $b'$, donc $a'$ divise $y_0 - y$ : $y_0 - y = a'\,k$ avec $k \in \mathbb{Z}$. En remplaçant, $a'\,(x - x_0) = b'\,a'\,k$, donc $x - x_0 = b'\,k$.
4. Vérifier et conclure. Réciproquement, pour tout $k \in \mathbb{Z}$, le couple $(x_0 + b'\,k\,;\,y_0 - a'\,k)$ est solution, car $a'\,b'\,k - b'\,a'\,k = 0$. L'ensemble des solutions est $\big\{(x_0 + b'\,k\,;\;y_0 - a'\,k),\ k \in \mathbb{Z}\big\}.$

Exemple 25. Résoudre dans $\mathbb{Z}^2$ l'équation $84\,x + 30\,y = 18$.

1. $\mathrm{PGCD}(84\,;30) = 6$ divise $18$. On divise par $6$ : $14\,x + 5\,y = 3$.
2. Solution particulière : $14 \times 2 + 5 \times (-5) = 28 - 25 = 3$, donc $(x_0\,;y_0) = (2\,;-5)$.
3. Si $14\,x + 5\,y = 3$, alors $14\,(x - 2) = 5\,(-5 - y)$. $5$ divise $14\,(x - 2)$ et $5$ est premier avec $14$, donc $5$ divise $x - 2$ : $x = 2 + 5k$. Alors $14 \times 5k = 5\,(-5 - y)$, d'où $y = -5 - 14k$.
4. Réciproquement, $14\,(2 + 5k) + 5\,(-5 - 14k) = 28 - 25 = 3$. Les solutions sont les couples $(2 + 5k\,;\,-5 - 14k)$, $k \in \mathbb{Z}$.

Remarque. Une autre solution particulière donne une autre écriture du même ensemble. Avec la remontée, $14 \times (-1) + 5 \times 3 = 1$, donc $(x_0\,;y_0) = (-3\,;9)$ : on obtient $(-3 + 5k\,;9 - 14k)$, qui décrit les mêmes couples (remplacer $k$ par $k + 1$).

5.3 Un problème concret

Exemple 26 (situation simplifiée). Dans une librairie, un cahier coûte $350$ F et un stylo $150$ F. Une élève a dépensé exactement $2\,600$ F. Combien a-t-elle pu acheter de cahiers et de stylos ?

On note $x$ le nombre de cahiers et $y$ le nombre de stylos : $350\,x + 150\,y = 2\,600$. En divisant par $50$ : $7\,x + 3\,y = 52$, avec $\mathrm{PGCD}(7\,;3) = 1$.

• Solution particulière : $7 \times 1 + 3 \times 15 = 52$.
• Comme ci-dessus, les solutions dans $\mathbb{Z}^2$ sont $x = 1 + 3k$ et $y = 15 - 7k$, $k \in \mathbb{Z}$.
• Ici $x$ et $y$ sont des entiers naturels : $1 + 3k \geq 0$ donne $k \geq 0$, et $15 - 7k \geq 0$ donne $k \leq 2$.

$k$	$0$	$1$	$2$
cahiers $x$	$1$	$4$	$7$
stylos $y$	$15$	$8$	$1$

Il y a trois possibilités.

5.4 Équations avec des congruences

Pour résoudre $a\,x \equiv b \;[n]$, deux méthodes :

• le tableau des restes : on essaie les $n$ restes possibles de $x$ ;
• multiplier par un « inverse » : on cherche un entier $a'$ tel que $a\,a' \equiv 1 \;[n]$ (il existe quand $a$ et $n$ sont premiers entre eux, d'après le théorème de Bézout), et on multiplie les deux membres par $a'$.

Exemple 27. Résoudre dans $\mathbb{Z}$ : $3\,x \equiv 2 \;[7]$.

$3 \times 5 = 15 \equiv 1 \;[7]$. Si $3x \equiv 2 \;[7]$, en multipliant par $5$ : $15\,x \equiv 10 \;[7]$, soit $x \equiv 3 \;[7]$. Réciproquement, si $x \equiv 3 \;[7]$, alors $3x \equiv 9 \equiv 2 \;[7]$. Les solutions sont les entiers $x = 3 + 7k$, $k \in \mathbb{Z}$.

Le tableau des restes donne le même résultat :

$x$ modulo $7$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$3x$ modulo $7$	$0$	$3$	$6$	$\mathbf{2}$	$5$	$1$	$4$

Lien avec la leçon. $3x \equiv 2 \;[7]$ signifie $3x = 2 + 7m$ avec $m$ entier, c'est-à-dire $3x + 7y = 2$ en posant $y = -m$ : c'est une équation du type $ax + by = c$.