Identité de Bézout et théorème de Gauss

4.1 Identité de Bézout

Théorème (identité de Bézout). Soit $a$ et $b$ deux entiers non tous les deux nuls, et $d = \mathrm{PGCD}(a\,;b)$. Il existe deux entiers relatifs $u$ et $v$ tels que $a\,u + b\,v = d.$

Démonstration (pour $a$ et $b$ naturels, $b \neq 0$). Dans l'algorithme d'Euclide, chaque reste s'écrit sous la forme $a\,u + b\,v$ avec $u$, $v$ entiers. C'est vrai pour $a = a \times 1 + b \times 0$ et pour $b = a \times 0 + b \times 1$ ; et si deux restes consécutifs $r_1$ et $r_2$ sont de cette forme, le suivant, $r_3 = r_1 - r_2\,q$, l'est aussi. C'est donc vrai pour le dernier reste non nul, qui est $d$.

Méthode : la remontée de l'algorithme d'Euclide. On écrit chaque reste à partir de la ligne qui le donne, puis on remplace, en remontant, jusqu'à n'avoir plus que $a$ et $b$.

Exemple 20. Trouver $u$ et $v$ tels que $84\,u + 30\,v = \mathrm{PGCD}(84\,;30)$.

L'algorithme d'Euclide donne : $84 = 30 \times 2 + 24$ ; $30 = 24 \times 1 + 6$ ; $24 = 6 \times 4 + 0$. Donc $\mathrm{PGCD}(84\,;30) = 6$. On remonte : $6 = 30 - 24 \times 1 = 30 - (84 - 30 \times 2) = 84 \times (-1) + 30 \times 3.$ On a donc $u = -1$ et $v = 3$. Vérification : $-84 + 90 = 6$.

Remarque. Le couple $(u\,;v)$ n'est pas unique : par exemple $84 \times 4 + 30 \times (-11) = 336 - 330 = 6$.

4.2 Théorème de Bézout

Théorème de Bézout. Deux entiers $a$ et $b$ sont premiers entre eux si, et seulement si, il existe deux entiers relatifs $u$ et $v$ tels que $a\,u + b\,v = 1.$

Démonstration.

• Si $\mathrm{PGCD}(a\,;b) = 1$, c'est l'identité de Bézout.
• Réciproquement, si $a\,u + b\,v = 1$, tout diviseur commun de $a$ et $b$ divise $a\,u + b\,v = 1$ : c'est $1$ ou $-1$. Donc $\mathrm{PGCD}(a\,;b) = 1$.

Méthode. Pour montrer que deux expressions sont premières entre elles, on cherche une combinaison qui vaut $1$ (ou $-1$).

Exemple 21.

• Pour tout entier $n$ : $(n + 1) \times 1 + n \times (-1) = 1$, donc deux entiers consécutifs sont premiers entre eux.
• Pour tout entier $n$ : $3\,(2n + 1) - 2\,(3n + 2) = -1$, donc $(2n + 1) \times (-3) + (3n + 2) \times 2 = 1$ : $2n + 1$ et $3n + 2$ sont premiers entre eux.

4.3 Théorème de Gauss

Théorème de Gauss. Soit $a$, $b$ et $c$ trois entiers. Si $a$ divise $b\,c$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Démonstration. Comme $\mathrm{PGCD}(a\,;b) = 1$, il existe $u$ et $v$ tels que $a\,u + b\,v = 1$. En multipliant par $c$ : $c = a\,c\,u + b\,c\,v$. Or $a$ divise $a\,c\,u$, et $a$ divise $b\,c$ donc $b\,c\,v$. Donc $a$ divise leur somme, $c$.

Exemple 22. Si $7$ divise $4n$, alors $7$ divise $n$, car $7$ et $4$ sont premiers entre eux.

Attention : l'hypothèse « premiers entre eux » est indispensable. $6$ divise $4 \times 3 = 12$, mais $6$ ne divise ni $4$ ni $3$.

4.4 Conséquence

Propriété. Si $a$ et $b$ divisent $c$, et si $a$ et $b$ sont premiers entre eux, alors $a\,b$ divise $c$.

Démonstration. $c = a\,k$ avec $k$ entier. $b$ divise $a\,k$ et $b$ est premier avec $a$ : d'après le théorème de Gauss, $b$ divise $k$, donc $k = b\,k'$ et $c = a\,b\,k'$.

Exemple 23.

• Un entier est divisible par $6$ si, et seulement si, il est divisible par $2$ et par $3$ ($2$ et $3$ sont premiers entre eux).
• Un entier est divisible par $12$ si, et seulement si, il est divisible par $3$ et par $4$. Mais être divisible par $2$ et par $6$ ne suffit pas : $6$ l'est, et n'est pas divisible par $12$. Ici $2$ et $6$ ne sont pas premiers entre eux.