PGCD et théorème de Bézout

Théorème de Bézout

Soient $a, b \in \mathbb{Z}$ non tous nuls. Il existe $u, v \in \mathbb{Z}$ tels que :

$au + bv = \text{PGCD}(a, b)$

Corollaire : $a \land b = 1 \iff \exists u,v \in \mathbb{Z}$ tels que $au + bv = 1$

---

Algorithme d’Euclide étendu

On remonte les divisions de l’algorithme d’Euclide pour trouver $u$ et $v$.

Exemple : PGCD(35, 12) et coefficients de Bézout.

$35 = 2 \times 12 + 11$ $12 = 1 \times 11 + 1$ $11 = 11 \times 1 + 0$

PGCD = 1. On remonte :

$1 = 12 - 1 \times 11 = 12 - (35 - 2 \times 12) = 3 \times 12 - 1 \times 35$

Donc : $35 \times (-1) + 12 \times 3 = 1$. Coefficients : $u = -1$, $v = 3$.

---

Équations diophantiennes $ax + by = c$

Soit $d = \text{PGCD}(a,b)$.

• Si $d \nmid c$ : pas de solution entière
• Si $d \mid c$ : infinité de solutions

Méthode :

1. Trouver une solution particulière $(x_0, y_0)$ par Bézout (si $c = d$), sinon multiplier.
2. Solution générale :

$x = x_0 + \frac{b}{d}t \quad y = y_0 - \frac{a}{d}t \quad t \in \mathbb{Z}$

Exemple : $35x + 12y = 1$. D’après ci-dessus : $x_0 = -1$, $y_0 = 3$.

Solution générale : $x = -1 + 12t$, $y = 3 - 35t$.

---

Théorème de Gauss (rappel)

Si $a \mid bc$ et $\text{PGCD}(a,b) = 1$, alors $a \mid c$.

Applications :

• Si $p$ premier et $p \mid ab$ → $p \mid a$ ou $p \mid b$
• Unicité de la décomposition en facteurs premiers

---

PPCM et relation avec le PGCD

$\text{PPCM}(a,b) = \frac{|ab|}{\text{PGCD}(a,b)}$