Théorème de Bachet-Bézout

En mathématiques, le théorème de Bachet-Bézout ou identité de Bézout est un résultat d'arithmétique élémentaire, qui prouve l'existence de solutions à l'équation diophantienne linéaire :

$a \cdot x + b \cdot y = \mathrm{pgcd}(a,b)$

d'inconnues x et y entiers relatifs et où a, b sont des coefficients entiers relatifs et où pgcd(a,b) est le plus grand commun diviseur de a et b.

Le théorème de Bézout affirme que l'équation $a \cdot x + b \cdot y = 1$ admet des solutions si et seulement si les entiers relatifs a et b sont premiers entre eux.

La première démonstration actuellement connue de ce théorème est due à Claude-Gaspard Bachet de Méziriac ; elle figure dans la seconde édition de son ouvrage Problèmes plaisans et délectables qui se font par les nombres, parue en 1624. Cependant, le mathématicien Étienne Bézout a généralisé ce résultat, notamment aux polynômes. Bourbaki, dans les Éléments d’histoire des mathématiques, énonce le résultat sur un anneau principal quelconque et lui donne le nom de « théorème de Bézout ».

Identité de Bézout dans l'ensemble des entiers relatifs

Théorème de Bachet de Méziriac

Claude-Gaspard Bachet de Méziriac (1581 - 1638)

Théorème —  Étant donnés deux entiers relatifs $a$ et $b$ non tous deux nuls, si $d$ est le PGCD de $a$ et de $b$ alors il existe deux entiers relatifs $x$ et $y$ tels que $x\cdot a + y\cdot b = d$.

Deux entiers relatifs $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers relatifs $x$ et $y$ tels que $x\cdot a + y\cdot b = 1$.

Démonstration

L'algorithme d'Euclide étendu, en fournissant un couple d'entiers solution de l'équation ax + by = pgcd(a,b), prouve déjà l'existence de solution à l'équation. Mais la démonstration qui suit, plus proche de celle qui sera utilisée dans les anneaux principaux, possède aussi un intérêt.

On peut supposer par exemple $a$ non nul. Si $A = \{xa+yb; (x;y) \in \Z^2\}$, on montre que le plus petit élément strictement positif de $A$ est le plus grand commun diviseur de $a$ et $b$.

En effet $A \cap \N^*$ est non vide (il contient la valeur absolue de $a$) donc contient un plus petit élément $d_0 = x_0a + y_0b$. La division euclidienne de $a$ par $d_0$ a pour reste $r$ qui est un entier naturel élément de $A$ car s'écrivant $r = a - qd_0 = a - qx_0a - qy_0b = (1-qx_0) \cdot a + (-qy_0) \cdot b$. C'est un entier plus petit que $d_0$, il ne peut donc pas appartenir à $A \cap \N^*$, donc $r$ est nul. Cela signifie que $d_0$ divise $a$. De même, $d_0$ divise $b$. Donc $d_0$ est un diviseur commun à $a$ et $b$.

Enfin, soit $d$ un autre diviseur commun à $a$ et $b$. Comme $d$ divise $a$ et $b$, $d$ divise $x_0a + y_0b$ donc $d$ divise $d_0$. $d_0$ est bien le plus grand diviseur commun de $a$ et $b$ et il existe deux entiers $x_0$ et $y_0$ tels que $\mathrm{pgcd}(a,b) = ax_0 + by_0$.

Résultat réciproque

Ce théorème ne possède en général pas de réciproque : l'existence de deux entiers tels que $d = ax + by$ n'assure pas que $d$ soit le PGCD de $a$ et $b$. Il suffit pour s'en convaincre de remarquer, par exemple, qu'il existe deux entiers $x$ et $y$ tels que $2x + 3y = 5$ (il suffit de prendre $x = 1$ et $y = 1$) alors que 5 n'est pas le PGCD de 2 et 3. S'il existe deux entiers $x$ et $y$ tels que $d = ax + by$, on peut seulement dire que $d$ est un multiple du PGCD. En effet, $a$ et $b$ étant des multiples de leur PGCD, $ax + by$ est un multiple du PGCD donc si $d = ax + by$ alors $d$ est un multiple du PGCD de $a$ et $b$.

Dans le cas de l'équation $ax+by = 1$, il existe cependant une réciproque : l'existence de deux entiers $x$ et $y$ tels que $ax + by = 1$ assure que 1 est un multiple du PGCD de a et b. Cela ne se peut que si le PGCD de $a$ et $b$ est 1 donc seulement si $a$ et $b$ sont premiers entre eux.

Le théorème de Bachet-Bézout assure l'existence d'un couple d'entiers tels que $ax + by = \mathrm{pgcd}(a,b)$. L'algorithme d'Euclide étendu fournit un des couples solutions, mais il en existe, en général, une infinité d'autres.

Par exemple, le plus grand diviseur commun de 12 et 42 est 6, et on peut écrire

$(-3) \cdot 12 + 1 \cdot 42 = 6$

mais aussi

$4 \cdot 12 + (-1) \cdot 42 = 6$.

Si le PGCD $d$ est non nul, à partir d'un couple solution $(x_0, y_0)$, il est facile de prouver que l'on a aussi :

$a \cdot \left(x_0 - k \cdot {b \over d}\right) + b \cdot \left(y_0 + k \cdot {a \over d}\right) = d$

où $k$ peut varier dans $\Z$.

Applications

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

Le théorème de Bachet -Bézout intervient dans de nombreux domaine de la théorie des nombres.

• Il permet de démontrer le théorème de Gauss.
• Il intervient dans la recherche d'inverse modulo b et est donc utile dans le décodage de message en cryptographie.
• Il intervient dans la résolution de l'équation diophantienne ax+by = c.

Généralisation

Théorème —  Étant donnés des entiers relatifs $a_1$, ..., $a_n$ non tous nuls, si $d$ est le PGCD de $a_1$, ..., $a_n$, alors il existe des entiers relatifs $x_1$, ..., $x_n$ tels que $x_1\cdot a_1 + \cdots x_n\cdot a_n = d$.

Les entiers relatifs $a_1$, ..., $a_n$ sont premiers entre eux (dans leur ensemble) si et seulement s'il existe des entiers relatifs $x_1$, ..., $x_n$ tels que $x_1\cdot a_1 + \cdots + x_n\cdot a_n = 1$.

En d'autres termes, quand les $a_i$ ne sont pas tous nuls, le PGCD de $a_1$, ..., $a_n$ est le plus petit entier strictement positif qui peut s'écrire comme combinaison linéaire à coefficients entiers de $a_1$, ..., $a_n$.

Identité de Bézout dans l'ensemble des polynômes

Article détaillé : Arithmétique des polynômes.

L'identité de Bézout se généralise à l'ensemble des polynômes à une indéterminée sur un corps commutatif K

Théorème —  Étant donnés $P_1,\dots,P_n$ des polynômes non tous nuls de $\mathbb{K}[X]$, si $\Delta$ est un PGCD de $P_1,\dots,P_n$, alors il existe $A_1,\dots,A_n$,polynômes de $\mathbb{K}[X]$, tels que $\Delta = \sum_{i=1}^n A_iP_i$.

Les polynômes $P_1,\dots,P_n$ de $\mathbb{K}[X]$ sont premiers entre eux (dans leur ensemble) si et seulement s'il existe $A_1,\dots,A_n$, polynômes de $\mathbb{K}[X]$ ,tels que $1 = \sum_{i=1}^n A_iP_i$.

Extension aux anneaux principaux quelconques

L'identité de Bézout peut s'écrire non seulement dans l'anneau des nombres entiers relatifs, mais aussi dans tout autre anneau principal. Notons que dans ce cas « plus grand diviseur » s'entend seulement au sens de la relation d'ordre fournie par la divisibilité dans l'anneau, l'unicité du PGCD n'est conservée qu'à un facteur inversible près de l'anneau. C'est-à-dire, si $A$ est un anneau principal, et $a$ et $b$ sont des éléments de $A$ non tous nuls, et $d$ est un plus grand diviseur commun de $a$ et $b$ , alors il existe des éléments $x$ et $y$ dans $A$ tels que :

$ax + by = d$

Dans un anneau principal, un PGCD de $a$ et $b$ est un générateur de $aA+bA$, l'identité de Bézout est une conséquence de cette définition.

Extension à d'autres anneaux

Article détaillé : Anneau de Bézout.

L'identité de Bachet-Bézout a donné lieu à une classe d'anneaux : un anneau A est dit de Bézout si tout idéal de type fini de A est principal (mais l'anneau peut éventuellement contenir des idéaux qui ne sont pas de type fini). Autrement dit, $A$ est de Bézout si deux éléments quelconques a, b de A possèdent toujours un PGCD, et si celui-ci peut toujours s'écrire sous la forme xa+yb (pour certains éléments x, y de A).

Article connexe

Théorème des restes chinois