PGCD, Bézout, Gauss — Terminale

Pour calculer un PGCD, prouver que deux nombres sont premiers entre eux, résoudre $ax + by = c$ en entiers.

Euclide : $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ où $r$ est le reste de $a$ par $b$. Bézout : $a$ et $b$ sont premiers entre eux ⇔ il existe $u, v$ entiers avec $au + bv = 1$. Gauss : si $a \mid bc$ et $\text{PGCD}(a, b) = 1$, alors $a \mid c$. $ax + by = c$ a des solutions ⇔ $\text{PGCD}(a, b) \mid c$.

1. PGCD par divisions successives (dernier reste non nul).
2. Remonte l'algorithme pour trouver $u, v$ (Bézout).
3. Équation $ax + by = c$ : solution particulière, puis Gauss pour la solution générale.

$\text{PGCD}(84, 30)$ : $84 = 2 \times 30 + 24$, $30 = 24 + 6$, $24 = 4 \times 6$ : PGCD = 6. $3x + 5y = 1$ : $(2 ; -1)$ ; solutions $(2 + 5k ; -1 - 3k)$.

Gauss exige que $a$ et $b$ soient premiers entre eux : $6 \mid 4 \times 3$ mais $6 \nmid 4$.