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

Prérequis

Résumé

Le théorème de Bézout est très important en théorie des nombres et est utilisé dans de nombreux résultats plus avancés. Après l'avoir énoncé et démontré, nous verrons immédiatement son intérêt en l'utilisant pour prouver le théorème de Gauss.

Ce chapitre a été écrit par N. Radu et mis en ligne le 8 décembre 2014.

1. Introduction

Le théorème de Bézout permet de répondre à la question :

Question
Étant donnés $a$ et $b$ deux nombres naturels (non-nuls), quels nombres entiers peuvent s'écrire sous la forme $$a x+b y$$ avec $x,y \in \mathbb{Z}$ ?

Par exemple, quels nombres peuvent s'écrire comme $15 x + 20 y$ ? Sur cet exemple, on remarque directement qu'il ne sera pas possible de former un nombre qui n'est pas un multiple de $5$. Et il s'agit là d'un fait général ! À partir des nombres $a$ et $b$, tous les nombres de la forme $ax + by$ seront forcément multiples de $(a,b)$ (le PGCD de $a$ et $b$), puisque ce dernier divise $a$ et $b$. Ici, $(15,20) = 5$ donc ils seront tous multiples de $5$.

Le théorème de Bézout permet d'établir qu'il s'agit en fait d'un si et seulement si : tout nombre multiple de $(a,b)$ peut s'écrire sous la forme $a x+b y$.

2. 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.$$

3. Théorème de Gauss

Le théorème de Gauss (parfois appelé lemme de Gauss) est le suivant :

Théorème de Gauss
Soient $a$, $b$ et $c$ trois entiers naturels non nuls. Si $c$ est premier avec $a$ et $c$ divise $ab$, alors $c$ divise $b$.

Par exemple, ce théorème nous indique que si $10$ divise un produit $ab$ alors que $a$ n'est divisible ni par $2$ ni par $5$, alors $b$ est forcément multiple de $10$.

Remarque importante
Ce théorème peut paraître tout à fait évident à démontrer, notamment en utilisant la décomposition en facteurs premiers des nombres $a$, $b$ et $c$. Cela dit, nous n'avions pas prouvé l'existence et l'unicité de cette décomposition et il se fait que le théorème de Gauss intervient dans la démonstration de l'unicité ! Nous vous avions présenté ce résultat en premier lieu pour des raisons pédagogiques, mais il devrait d'un point de vue logique se situer après le théorème de Gauss. Il n'est dès lors pas raisonnable d'utiliser la décomposition des nombres pour démontrer notre théorème !

Démonstration
Une jolie façon de faire est d'utiliser le théorème de Bézout que nous venons de démontrer (notez que nous n'avions pour ce faire pas utilisé le théorème de décomposition en facteurs premiers).
Nous savons par hypothèse que $c$ divise $ab$. Il existe donc un nombre entier $k$ tel que $ck = ab$. De plus, $c$ est premier avec $a$, c'est-à-dire $(a,c) = 1$. Nous pouvons dès lors appliquer le théorème de Bézout qui nous fournit $x$ et $y$ entiers tels que
$$ax+cy = 1.$$ On multiplie les deux membres par $b$, ce qui nous permet d'écrire
$$\begin{align}
& abx + cby = b\\
\Leftrightarrow \quad & ckx + cby = b\\
\Leftrightarrow \quad & c(kx+by) = b
\end{align}$$ Et on voit donc directement que $c$ divise bien $b$.

Lemme d'Euclide

Le lemme d'Euclide est un cas particulier de celui de Gauss :

Lemme d'Euclide
Soient $a$ et $b$ des nombres naturels non nuls et $p$ un nombre premier. Si $p$ divise $ab$, alors $p$ divise $a$ ou $b$.

Démonstration
Supposons que $p$ ne divise pas $a$. Alors, $(a,p) = 1$ et le théorème de Gauss nous indique immédiatement que $p$ divise $b$.

Remarque (suite)
C'est en fait ce cas particulier du théorème de Gauss qui permet de prouver l'unicité de la décomposition en facteurs premiers. En effet, si le nombre $n$ possède deux décompositions
$$p_1^{e_1}\cdot \ldots \cdot p_k^{e_k} = q_1^{f_1} \cdot \ldots \cdot q_l^{f_l}$$ alors $p_1$ divise $q_1^{f_1} \cdot \ldots \cdot q_l^{f_l}$ et le lemme d'Euclide appliqué plusieurs fois nous indique qu'il existe un des $q_i$ qui est divisible par $p_1$, et donc égal à celui-ci. On peut alors diviser le premier membre par $p_1$ et le deuxième par $q_i$ tout en gardant l'égalité. En continuant de la sorte, on trouve finalement que les facteurs (et les exposants) doivent forcément être identiques dans les deux décompositions.