Identité de Bézout : au + bv = PGCD(a, b)

Le théorème

Théorème de Bézout : pour tous entiers $a, b$ non tous les deux nuls, il existe des entiers $u, v$ tels que :

$a u + b v = \text{PGCD}(a, b)$

Corollaire : nombres premiers entre eux

$a$ et $b$ sont premiers entre eux ssi il existe $u, v$ entiers avec :

$a u + b v = 1$

C’est équivalent à $\text{PGCD}(a, b) = 1$.

Trouver $u$ et $v$ : Euclide remonté

1. Faire l’algorithme d’Euclide (successions de divisions).
2. Remonter les étapes en exprimant chaque reste comme combinaison de $a$ et $b$.

Exemple : Bézout pour $a = 30$, $b = 18$

Descente d’Euclide :

• $30 = 1 \times 18 + 12$
• $18 = 1 \times 12 + 6$
• $12 = 2 \times 6 + 0$ ⇒ PGCD = 6.

Remontée :

• $6 = 18 - 12$
• $6 = 18 - (30 - 18) = 2 \times 18 - 30$

Donc $u = -1$, $v = 2$ : $30 \times (-1) + 18 \times 2 = 6$. ✓

Application 1 : équation diophantienne

Résoudre $ax + by = c$ dans $\mathbb{Z}$ :

• Existe une solution ssi $\text{PGCD}(a, b) \mid c$.
• Si oui : trouver une solution particulière par Bézout, puis toutes les autres par récurrence.

Application 2 : inverse modulaire

Trouver $u$ tel que $a u \equiv 1 \pmod n$ ?

Existe ssi $\text{PGCD}(a, n) = 1$. Par Bézout : $a u + n v = 1$, donc $a u \equiv 1 \pmod n$.

Le PGCD est le plus petit

Le PGCD est le plus petit entier strictement positif de la forme $au + bv$ avec $u, v \in \mathbb{Z}$.

Erreurs classiques

1. Confondre Bézout et Gauss (Gauss = si $a | bc$ et PGCD$(a,b)=1$ alors $a | c$).
2. Oublier que $u, v$ peuvent être négatifs.
3. Chercher $u, v$ dans $\mathbb{N}$ (souvent impossible).

?À toi de jouer

Existe-t-il u, v entiers tels que 15u + 25v = 4 ?

A.Non (PGCD = 5, ne divise pas 4)B.Oui, u = 1, v = 0C.Oui, u = 4, v = −2D.Toujours possible

Valider