Théorie > Théorie des nombres > Théorème de Bézout

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