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

L'algorithme d'Euclide, vieux de plus de 2 000 ans, calcule le plus grand diviseur commun de deux entiers. Il fournit en prime une relation $au + bv = \mathrm{PGCD}(a, b)$, clé des théorèmes de Bézout et de Gauss, qui permettent de résoudre des équations en nombres entiers.

Calculer un PGCD avec l'algorithme d'Euclide
Trouver un couple de Bézout, démontrer que deux entiers sont premiers entre eux
Démontrer et utiliser le théorème de Gauss
Résoudre des équations diophantiennes $ax + by = c$ et des congruences $ax \equiv b\ [n]$

Cours

1. PGCD et algorithme d'Euclide

Soit $a$ et $b$ deux entiers non tous les deux nuls. L'ensemble de leurs diviseurs communs est fini et contient 1 : son plus grand élément est le plus grand commun diviseur de $a$ et $b$, noté $\mathrm{PGCD}(a, b)$ ou $a \wedge b$.

Exemple : les diviseurs positifs de 12 sont 1, 2, 3, 4, 6, 12 ; ceux de 18 sont 1, 2, 3, 6, 9, 18. Donc $\mathrm{PGCD}(12, 18) = 6$.

Si $a = bq + r$ (avec $a$, $b$, $q$, $r$ entiers), alors les diviseurs communs de $a$ et $b$ sont exactement ceux de $b$ et $r$. En particulier $\mathrm{PGCD}(a, b) = \mathrm{PGCD}(b, r)$.

Preuve : un diviseur de $a$ et $b$ divise $r = a - bq$ ; un diviseur de $b$ et $r$ divise $a = bq + r$ (combinaisons linéaires).

On effectue des divisions euclidiennes successives, en remplaçant $(a, b)$ par $(b, r)$ jusqu'à obtenir un reste nul. Le PGCD est le dernier reste non nul.

$161 = 63 \times 2 + 35$ ; $\;63 = 35 \times 1 + 28$ ; $\;35 = 28 \times 1 + 7$ ; $\;28 = 7 \times 4 + 0$. Donc $\mathrm{PGCD}(161, 63) = 7$.

L'algorithme s'arrête car les restes forment une suite d'entiers naturels strictement décroissante.

Deux entiers sont premiers entre eux si leur PGCD vaut 1 (leurs seuls diviseurs communs sont 1 et $-1$). Une fraction $\frac ab$ est irréductible si et seulement si $a$ et $b$ sont premiers entre eux.

2. Identité de Bézout

Soit $a$ et $b$ deux entiers non tous les deux nuls, et $d = \mathrm{PGCD}(a, b)$. Il existe deux entiers $u$ et $v$ tels que $\;au + bv = d$.

Soit $E$ l'ensemble des entiers strictement positifs de la forme $ax + by$, avec $x, y \in \mathbb{Z}$. $E$ n'est pas vide : il contient $a^2 + b^2 = a \times a + b \times b > 0$. Toute partie non vide de $\mathbb{N}$ a un plus petit élément : notons $m$ celui de $E$, et $m = au_0 + bv_0$.

$m$ divise $a$. Division euclidienne : $a = mq + r$ avec $0 \leqslant r < m$. Alors $r = a - mq = a(1 - qu_0) + b(-qv_0)$ est de la forme $ax + by$. Si on avait $r > 0$, $r$ serait un élément de $E$ strictement plus petit que $m$ : impossible. Donc $r = 0$ et $m \mid a$. De même, $m \mid b$.

Conclusion. $m$ est un diviseur commun positif de $a$ et $b$, donc $m \leqslant d$. D'autre part, $d$ divise $a$ et $b$, donc il divise la combinaison $au_0 + bv_0 = m$, ce qui donne $d \leqslant m$. Ainsi $m = d$ et $d = au_0 + bv_0$. $\blacksquare$

Avec $161$ et $63$ : $7 = 35 - 28$, puis $28 = 63 - 35$ donne $7 = 35 - (63 - 35) = 2 \times 35 - 63$, puis $35 = 161 - 2 \times 63$ donne $7 = 2 \times 161 - 5 \times 63$. Donc $u = 2$, $v = -5$ conviennent. Le widget ci-dessus fait ce calcul dans les colonnes $u$ et $v$.

Deux entiers $a$ et $b$ sont premiers entre eux si et seulement s'il existe deux entiers $u$ et $v$ tels que $au + bv = 1$.

Sens direct : c'est la propriété précédente avec $d = 1$. Réciproque : un diviseur commun de $a$ et $b$ divise $au + bv = 1$, donc vaut $\pm1$.

Pour tout entier $n$, $3(14n + 3) - 2(21n + 4) = 1$ : les entiers $14n + 3$ et $21n + 4$ sont premiers entre eux.

Tout diviseur commun de $a$ et $b$ divise $\mathrm{PGCD}(a, b)$ (il divise $au + bv$).

3. Théorème de Gauss

Soit $a$, $b$, $c$ trois entiers. Si $a$ divise $bc$ et si $a$ est premier avec $b$, alors $a$ divise $c$.

Comme $a$ et $b$ sont premiers entre eux, le théorème de Bézout donne des entiers $u$ et $v$ tels que $au + bv = 1$. En multipliant par $c$ : $$c = acu + bcv.$$ Or $a$ divise $acu$ (évident) et $a$ divise $bcv$ (car $a \mid bc$). Donc $a$ divise leur somme, c'est-à-dire $c$. $\blacksquare$

L'hypothèse « premier avec » est indispensable : $6 \mid 4 \times 3$, mais $6 \nmid 4$ et $6 \nmid 3$.

Si $a \mid n$, $b \mid n$ et $\mathrm{PGCD}(a, b) = 1$, alors $ab \mid n$. (Exemple : divisible par 2 et par 3 ⇒ divisible par 6.)
Si un nombre premier $p$ divise un produit $ab$, alors $p \mid a$ ou $p \mid b$.

Si $a \mid n$, $b \mid n$ et $\mathrm{PGCD}(a, b) = 1$, alors $ab \mid n$.

$n = ak$ avec $k$ entier. Alors $b \mid ak$ et $b$ est premier avec $a$ : par le théorème de Gauss, $b \mid k$, soit $k = bk'$. Donc $n = abk'$. $\blacksquare$

4. Équations diophantiennes ax + by = c

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

Solution particulière : $7 \times 3 + 4 \times (-5) = 1$ (Bézout), donc en multipliant par 3, $(x_0\,;\,y_0) = (9\,;\,-15)$ convient. Plus simplement, on voit que $(1\,;\,-1)$ convient.
Soustraction : si $7x + 4y = 3$, alors $7x + 4y = 7 \times 1 + 4 \times (-1)$, soit $7(x - 1) = 4(-1 - y)$.
Gauss : 4 divise $7(x - 1)$ et 4 est premier avec 7, donc $4 \mid x - 1$ : $x = 1 + 4k$. En reportant : $7 \times 4k = 4(-1 - y)$, donc $y = -1 - 7k$.
Réciproque : $7(1 + 4k) + 4(-1 - 7k) = 3$ pour tout $k$.

Les solutions sont les couples $(1 + 4k\,;\,-1 - 7k)$, $k \in \mathbb{Z}$.

5. Inverse modulo n

Un entier $a$ a un inverse modulo $n$ (un entier $u$ tel que $au \equiv 1\ [n]$) si et seulement si $a$ et $n$ sont premiers entre eux. On l'obtient avec un couple de Bézout : $au + nv = 1 \Rightarrow au \equiv 1\ [n]$.

Alors l'équation $ax \equiv b\ [n]$ équivaut à $x \equiv ub\ [n]$.

Inverse de 7 modulo 26 : $26 = 7 \times 3 + 5$, $7 = 5 + 2$, $5 = 2 \times 2 + 1$, d'où $1 = 5 - 2 \times 2 = 5 - 2(7 - 5) = 3 \times 5 - 2 \times 7 = 3(26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7$. Donc $7 \times (-11) \equiv 1\ [26]$ : l'inverse est $-11 \equiv 15$. Vérification : $7 \times 15 = 105 = 4 \times 26 + 1$.

def euclide_etendu(a, b):
    # renvoie (d, u, v) avec d = PGCD(a, b) = a*u + b*v
    r0, r1, u0, u1, v0, v1 = a, b, 1, 0, 0, 1
    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 - q * r1
        u0, u1 = u1, u0 - q * u1
        v0, v1 = v1, v0 - q * v1
    return r0, u0, v0

print(euclide_etendu(161, 63))
d, u, v = euclide_etendu(7, 26)
print("inverse de 7 modulo 26 :", u % 26)

L'algorithme figure dans le livre VII des Éléments d'Euclide (vers 300 av. J.-C.). Claude-Gaspard Bachet de Méziriac publie en 1612 la méthode pour trouver $u$ et $v$ ; Étienne Bézout l'étend aux polynômes en 1766. Gauss énonce son théorème dans les Disquisitiones arithmeticae (1801).

Mini-jeux

Exercices

Calculer $\mathrm{PGCD}(1\,071, 462)$ avec l'algorithme d'Euclide.

$1\,071 = 462 \times 2 + 147$ ; $462 = 147 \times 3 + 21$ ; $147 = 21 \times 7 + 0$. Le PGCD vaut 21.

Trouver des entiers $u$ et $v$ tels que $17u + 5v = 1$.

$17 = 5 \times 3 + 2$, $5 = 2 \times 2 + 1$. Donc $1 = 5 - 2 \times 2 = 5 - 2(17 - 3 \times 5) = 7 \times 5 - 2 \times 17$ : $u = -2$, $v = 7$.

Montrer que pour tout entier naturel $n$, $n$ et $2n + 1$ sont premiers entre eux, ainsi que $2n + 1$ et $3n + 1$.

$(2n + 1) - 2 \times n = 1$ ; $\;3(2n + 1) - 2(3n + 1) = 1$. On conclut par le théorème de Bézout.

Résoudre dans $\mathbb{Z}^2$ l'équation $11x + 7y = 1$.

$11 \times 2 + 7 \times (-3) = 1$. Si $11x + 7y = 1$, alors $11(x - 2) = 7(-3 - y)$ ; 7 divise $11(x - 2)$ et est premier avec 11, donc $x = 2 + 7k$, puis $y = -3 - 11k$. Réciproquement ces couples conviennent. Solutions : $(2 + 7k\,;\,-3 - 11k)$, $k \in \mathbb{Z}$.

On dispose d'autant de masses de 7 g et de 11 g qu'on veut. Peut-on équilibrer exactement 100 g en les posant toutes sur le même plateau ? Si oui, comment ?

On cherche $x, y \geqslant 0$ avec $7x + 11y = 100$. On a $7 \times (-3) + 11 \times 2 = 1$, d'où la solution particulière $(-300\,;\,200)$ et les solutions $(-300 + 11k\,;\,200 - 7k)$. On veut $x \geqslant 0 \iff k \geqslant 28$ (car $k \geqslant 27{,}3$) et $y \geqslant 0 \iff k \leqslant 28$ : $k = 28$, soit $x = 8$ et $y = 4$. Vérification : $56 + 44 = 100$.

Résoudre $7x \equiv 5\ [26]$.

Plus petite solution positive :

L'inverse de 7 modulo 26 est 15 (voir le cours). $x \equiv 15 \times 5 = 75 \equiv 23\ [26]$. Vérification : $7 \times 23 = 161 = 6 \times 26 + 5$.

Montrer que pour tout entier $n$, $\mathrm{PGCD}(n^2 + 1, n + 1)$ vaut 1 ou 2. Pour quels $n$ vaut-il 2 ?

$n^2 + 1 = (n + 1)(n - 1) + 2$, donc (lemme d'Euclide) $\mathrm{PGCD}(n^2 + 1, n + 1) = \mathrm{PGCD}(n + 1, 2)$, qui vaut 2 si $n$ est impair et 1 si $n$ est pair.

Un général compte ses soldats : en rangs de 3, il en reste 2 ; en rangs de 5, il en reste 3 ; en rangs de 7, il en reste 2. Il a moins de 100 soldats. Combien sont-ils ?

$x \equiv 2\ [3]$ et $x \equiv 2\ [7]$ : 3 et 7 divisent $x - 2$ et sont premiers entre eux, donc $21 \mid x - 2$ : $x \in \{2, 23, 44, 65, 86\}$. Parmi eux, seul $23 \equiv 3\ [5]$. Ils sont 23. (Problème posé par Sunzi, en Chine, au III^e siècle.)