Soient $a,b \in \mathbb{N}_0$, et $c \in \mathbb{Z}$. Il existe des entiers $x, y \in \mathbb{Z}$ tels que
$$ ax+by=c$$ si et seulement si $c$ est un multiple de $(a,b)$.
Étant donné un nombre entier $c$ multiple de $(a,b)$, nous devons trouver une façon d'exprimer $c$ comme $a x+b y$.
Remarquons tout d'abord qu'il suffit de prouver que $(a,b)$ s'écrit comme
$$a x_0 + b y_0.$$ En effet, en prouvant cela, vu que tout multiple $c$ de $(a,b)$ s'écrit $c = k \cdot (a,b)$ on aura directement
$$c = k \cdot (a,b) = k \cdot (a x_0 + b y_0) = a (k x_0) + b (k y_0)$$ qui est de la forme voulue.
Reste donc à trouver une façon d'écrire $(a,b)$ sous cette forme. Pour ce faire, rien de plus simple, il suffit d'utiliser l'algorithme d'Euclide à l'envers ! En effet, rappelons qu'étant donnés $a$ et $b$ deux nombres naturels, l'algorithme d'Euclide s'écrit
$$\begin{align}
a &= q_0 \cdot b + r_0\\
b &= q_1 \cdot r_0 + r_1\\
r_0 &= q_2 \cdot r_1 + r_2\\
& \vdots \\
r_{n-3} &= q_{n-1} \cdot r_{n-2} + r_{n-1}\\
r_{n-2} &= q_{n} \cdot r_{n-1} + \boxed{r_n}\\
r_{n-1} &= q_{n+1} \cdot r_n + 0\\
\end{align}$$ Et nous avons montré qu'il nous fournit $r_n = (a,b)$. L'astuce est alors de remonter cette suite d'égalité :
- À partir de l'avant-dernière équation, on peut écrire $(a,b) = r_n = r_{n-2} - q_n \cdot r_{n-1}$, c'est-à-dire $(a,b)$ en fonction de $r_{n-2}$ et $r_{n-1}$.
- À partir de l'équation précédente (l'avant-avant-dernière), de la même façon on peut écrire $r_{n-1}$ en fonction de $r_{n-2}$ et $r_{n-3}$. En remplacant $r_{n-1}$ par cette combinaison dans l'équation trouvée au premier point, on exprime ainsi $(a,b)$ en termes de $r_{n-2}$ et $r_{n-3}$.
- On continue ainsi jusqu'à la première équation, qui nous permet d'exprimer $r_0$ en fonction de $a$ et $b$, et par suite $(a,b)$ en fonction de $a$ et $b$, comme voulu.
Cela peut paraître bien compliqué, mais notre exemple $a=78$, $b=33$ va éclairer les choses. Comme $(78,33) = 3$, nous devons trouver $x_0, y_0 \in \mathbb{Z}$ tels que
$$3 = 78 \cdot x_0 + 33 \cdot y_0.$$ On commence par appliquer l'algorithme d'Euclide :
$$3 = 12-9$$ L'égalité précédente nous permet de remplacer $9$ par $33 - 2 \cdot 12$ :
$$3 = 12-9 = 12-(33-2 \cdot 12) = 3 \cdot 12-33$$ L'égalité encore avant (la première) nous permet enfin de remplacer $12$ par $78-2 \cdot 33$ :
$$\boxed{3}=3 \cdot 12-33 = 3 \cdot (78-2 \cdot 33)-33= \boxed{3 \cdot 78-7 \cdot 33}$$ Nous sommes parvenus à écrire $3$ sous la bonne forme (avec $x_0 = 3$ et $y_0 = -7$).