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$

Flowchart — Algorithme d’Euclide

flowchart TD
    E["Entrée : a, b (entiers, b ≠ 0)"] --> W{"b = 0 ?"}
    W -->|Non| D["Division euclidienne\na = b·q + r"]
    D --> U["a ← b\nb ← r"]
    U --> W
    W -->|Oui| R["Retourner a\n= PGCD(a₀, b₀)"]

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 :

Trouver une solution particulière $(x_0, y_0)$ par Bézout (si $c = d$ ), sinon multiplier.
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)}$