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

Théorème de Bézout

Le théorème de Bézout s'énonce comme suit :

Théorème de Bézout
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)$.

Démonstration et construction
É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 :
$$\begin{align}
78 &= 2 \cdot 33 + 12\\
33 &= 2 \cdot 12 + 9\\
12 &= 1 \cdot 9 + \boxed{3}\\
9 &= 3 \cdot 3 + 0
\end{align}$$ On remonte ensuite les égalités, ce qui nous donne d'abord
$$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$).

Commentaires

  1. Comme précisé dans la démonstration, écrire un multiple de $3$ comme combinaison de $78$ et $33$ est à présent immédiat. Par exemple,
    $$9 = 3 \cdot 3= 9 \cdot 78-21 \cdot 33.$$
  2. Il ne s'agit pas de l'unique façon d'écrire $3$ comme combinaison de $78$ et $33$. Il y a d'ailleurs une infinité de possibilités ! En effet, on peut toujours rajouter $33 \cdot 78$ au premier terme et soustraire $78 \cdot 33$ du deuxième, ce qui donne par exemple
    $$3 = 36 \cdot 78 - 85 \cdot 33.$$
  3. Un cas particulier du théorème de Bézout, fréquemment utilisé, est celui où $a$ et $b$ sont premiers entre eux (c'est-à-dire lorsque $(a,b)=1$). Dans ce cas, il existe alors $x$ et $y$ des nombres entiers tels que
    $$a x+b y = 1.$$