PGCD, théorèmes de Bézout et de Gauss

Ce que tu sais déjà. Tu connais la divisibilité, la division euclidienne et les congruences (Divisibilité, division euclidienne et congruences), et tu as rencontré le PGCD au collège (3e — Multiples, diviseurs et PGCD). On en fait ici un outil de démonstration : il permet de résoudre des équations en nombres entiers et de chiffrer des messages.

1. PGCD et algorithme d’Euclide

Définition. Soit $a$ et $b$ deux entiers non tous deux nuls. L’ensemble de leurs diviseurs communs est fini et contient $1$ : son plus grand élément est le PGCD de $a$ et $b$, noté $\text{PGCD}(a\,;\,b)$. Il est toujours $\geqslant 1$ et $\text{PGCD}(a\,;\,b) = \text{PGCD}(|a|\,;\,|b|)$.

Propriété (clé de l’algorithme). Si $a = bq + r$, alors les diviseurs communs à $a$ et $b$ sont exactement les diviseurs communs à $b$ et $r$. Donc $\text{PGCD}(a\,;\,b) = \text{PGCD}(b\,;\,r)$.

Justification. Un diviseur commun de $a$ et $b$ divise la combinaison $a - bq = r$ ; un diviseur commun de $b$ et $r$ divise $bq + r = a$.

Algorithme d’Euclide. On remplace $(a\,;\,b)$ par $(b\,;\,r)$ jusqu’à obtenir un reste nul : le PGCD est le dernier reste non nul.

Exemple. $\text{PGCD}(546\,;\,210)$ : $546 = 210 \times 2 + 126$ ; $210 = 126 \times 1 + 84$ ; $126 = 84 \times 1 + 42$ ; $84 = 42 \times 2 + 0$. Le PGCD est $42$.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return abs(a)

print(pgcd(546, 210))   # 42

Propriétés. Pour $k \geqslant 1$, $\text{PGCD}(ka\,;\,kb) = k\,\text{PGCD}(a\,;\,b)$. Tout diviseur commun de $a$ et $b$ divise leur PGCD (on le verra au § 3).

→ S’entraîner : Exercice 1

2. Entiers premiers entre eux

Définition. $a$ et $b$ sont premiers entre eux si $\text{PGCD}(a\,;\,b) = 1$ : leurs seuls diviseurs communs sont $1$ et $-1$.

Exemples. $35$ et $12$ sont premiers entre eux (aucun diviseur commun autre que $\pm 1$). Deux entiers consécutifs $n$ et $n + 1$ sont toujours premiers entre eux : un diviseur commun divise leur différence $1$.

Propriété (fraction irréductible). Si $d = \text{PGCD}(a\,;\,b)$, on écrit $a = da'$ et $b = db'$ : alors $a'$ et $b'$ sont premiers entre eux et $\dfrac{a'}{b'}$ est la forme irréductible de $\dfrac ab$.

Exemple. $\dfrac{546}{210} = \dfrac{42 \times 13}{42 \times 5} = \dfrac{13}{5}$.

→ S’entraîner : Exercice 2

3. Théorème de Bézout

Théorème (identité de Bézout). Soit $a$ et $b$ deux entiers non tous deux nuls et $d = \text{PGCD}(a\,;\,b)$. Il existe des entiers relatifs $u$ et $v$ tels que $$au + bv = d.$$

Conséquence. Tout diviseur commun de $a$ et $b$ divise $\text{PGCD}(a\,;\,b)$.

Théorème de Bézout. $a$ et $b$ sont premiers entre eux si et seulement si il existe des entiers $u$ et $v$ tels que $au + bv = 1$.

Justification. Le sens direct est l’identité de Bézout. Réciproquement, si $au + bv = 1$, tout diviseur commun de $a$ et $b$ divise $1$, donc vaut $\pm 1$.

def euclide_etendu(a, b):
    """Renvoie (d, u, v) avec d = PGCD(a, b) = a*u + b*v."""
    if b == 0:
        return a, 1, 0
    d, u, v = euclide_etendu(b, a % b)
    return d, v, u - (a // b) * v

print(euclide_etendu(37, 11))   # (1, 3, -10)

Application : inverse modulo $n$. $a$ admet un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux. Si $au + nv = 1$, alors $au \equiv 1\ [n]$ : $u$ est un inverse de $a$ modulo $n$.

Exemple. $37 \times 3 - 11 \times 10 = 1$ donne $37 \times 3 \equiv 1\ [11]$ et $11 \times (-10) \equiv 1\ [37]$ : l’inverse de $11$ modulo $37$ est $-10 \equiv 27$.

→ S’entraîner : Exercice 3 · Exercice 4

4. Théorème de Gauss

Théorème de Gauss. Soit $a$, $b$, $c$ trois entiers non nuls. Si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Attention. L’hypothèse « premier avec $b$ » est indispensable : $6 \mid 4 \times 9$ mais $6 \nmid 4$ et $6 \nmid 9$.

Corollaire. Si $a$ et $b$ sont premiers entre eux et divisent tous deux $n$, alors $ab$ divise $n$.

Justification. $n = ak$ ; $b \mid ak$ et $b$ premier avec $a$, donc $b \mid k$ (Gauss) : $k = bk'$ et $n = abk'$.

Exemple. Un entier divisible par $4$ et par $9$ est divisible par $36$ (car $4$ et $9$ sont premiers entre eux) ; mais un entier divisible par $4$ et par $6$ n’est pas forcément divisible par $24$ ($12$).

→ S’entraîner : Exercice 5

5. Équations diophantiennes ax + by = c

Propriété. L’équation $ax + by = c$ (d’inconnues entières $x$, $y$) a des solutions si et seulement si $\text{PGCD}(a\,;\,b)$ divise $c$.

Remarque. Si $d = \text{PGCD}(a\,;\,b)$ divise $c$, on divise d’abord toute l’équation par $d$ pour se ramener à des coefficients premiers entre eux.

→ S’entraîner : Exercice 6 · Exercice 7 · Exercice 8

À retenir.

• $\text{PGCD}(a\,;\,b) = \text{PGCD}(b\,;\,r)$ ; algorithme d’Euclide : dernier reste non nul.
• Il existe $u$, $v$ avec $au + bv = \text{PGCD}(a\,;\,b)$ ; tout diviseur commun divise le PGCD.
• Bézout : $a$ et $b$ premiers entre eux $\iff$ il existe $u$, $v$ avec $au + bv = 1$.
• Gauss : $a \mid bc$ et $\text{PGCD}(a\,;\,b) = 1$ $\Rightarrow$ $a \mid c$ ; si $a$, $b$ premiers entre eux divisent $n$, alors $ab \mid n$.
• $ax + by = c$ a des solutions $\iff$ $\text{PGCD}(a\,;\,b) \mid c$ ; solution particulière + Gauss.