Comment trouver un couple de Bézout, c'est-à-dire $u, v$ tels que $au + bv = \text{PGCD}(a, b)$ ?

On effectue l'algorithme d'Euclide, puis on « remonte » les divisions en exprimant chaque reste en fonction des précédents. Pour $35$ et $12$ : $35 = 2 \times 12 + 11$, $12 = 1 \times 11 + 1$. On remonte : $1 = 12 - 11 = 12 - (35 - 2 \times 12) = 3 \times 12 - 35$. Donc $35 \times (-1) + 12 \times 3 = 1$. Il existe une infinité de couples solutions ; on vérifie toujours le résultat par un calcul direct.

Comment résoudre une équation diophantienne $ax + by = c$ ?

1) Calculer $d = \text{PGCD}(a, b)$ : s'il ne divise pas $c$, il n'y a aucune solution. 2) Sinon, simplifier par $d$ pour se ramener à $a'x + b'y = c'$ avec $a', b'$ premiers entre eux, et trouver une solution particulière $(x_0, y_0)$ (Bézout, ou tâtonnement). 3) Soustraire : $a'(x - x_0) = -b'(y - y_0)$, puis appliquer le théorème de Gauss : $b' \mid (x - x_0)$, d'où $x = x_0 + b'k$ et $y = y_0 - a'k$, $k \in \mathbb{Z}$. 4) Vérifier que ces couples sont bien solutions.

Quelle est la différence entre le théorème de Bézout et le théorème de Gauss ?

Bézout affirme que $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u, v$ avec $au + bv = 1$ ; c'est un outil pour prouver que deux nombres sont premiers entre eux ou pour construire des inverses modulo $n$. Gauss affirme que si $a \mid bc$ et $a$ premier avec $b$, alors $a \mid c$ ; c'est l'outil pour « simplifier » une divisibilité, indispensable pour résoudre les équations diophantiennes. Gauss se démontre à partir de Bézout.

PGCD et théorème de Bézout

Définitions

Définition 1 — PGCD. Soit $a, b \in \mathbb{Z}$ non tous deux nuls. Leurs diviseurs communs positifs forment un ensemble fini non vide (il contient 1) : le plus grand d’entre eux est le PGCD de $a$ et $b$ , noté $\text{PGCD}(a, b)$ ou $a \wedge b$ . Exemples : $\text{PGCD}(24, 36) = 12$ ; $\text{PGCD}(a, 0) = |a|$ pour $a \neq 0$ ; $\text{PGCD}(a, 1) = 1$ ; $\text{PGCD}(a, b) = \text{PGCD}(|a|, |b|)$ .

Définition 2 — entiers premiers entre eux. $a$ et $b$ sont premiers entre eux si $\text{PGCD}(a, b) = 1$ , c’est-à-dire si leurs seuls diviseurs communs sont $1$ et $-1$ . Exemples : 8 et 9 sont premiers entre eux (sans être des nombres premiers) ; $n$ et $n + 1$ sont toujours premiers entre eux ; 9 et 15 ne le sont pas.

Théorèmes et propriétés

Théorème 1 (propriétés du PGCD).

Si $b \mid a$ (avec $b > 0$ ), alors $\text{PGCD}(a, b) = b$ .
Pour $k \in \mathbb{N}^*$ : $\text{PGCD}(ka, kb) = k\,\text{PGCD}(a, b)$ .
Les diviseurs communs de $a$ et $b$ sont exactement les diviseurs de $\text{PGCD}(a, b)$ (conséquence de la démonstration du Théorème 3).

Exemple : les diviseurs communs de 24 et 36 sont $1, 2, 3, 4, 6, 12$ : les diviseurs de 12.

Théorème 2 (lemme d’Euclide). (démonstration exigible) Soit $a \in \mathbb{Z}$ , $b \in \mathbb{N}^*$ et $a = bq + r$ la division euclidienne. Alors $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ .

Démonstration : si $d$ divise $a$ et $b$ , alors $d$ divise $r = a - bq$ (combinaison linéaire) ; réciproquement, si $d$ divise $b$ et $r$ , alors $d$ divise $a = bq + r$ . Les couples $(a, b)$ et $(b, r)$ ont donc les mêmes diviseurs communs, et le même plus grand diviseur commun.

C’est ce lemme qui justifie l’algorithme d’Euclide (Méthode 1) : les restes successifs décroissent strictement, donc l’algorithme s’arrête, et le PGCD est le dernier reste non nul.

Théorème 3 (identité de Bézout). (démonstration exigible) Soit $a, b \in \mathbb{Z}$ non tous deux nuls et $d = \text{PGCD}(a, b)$ . Il existe des entiers $u, v$ tels que

$au + bv = d$

Démonstration : soit $E$ l’ensemble des entiers strictement positifs de la forme $au + bv$ . $E$ n’est pas vide (il contient $|a|$ ou $|b|$ ) ; soit $m = au_0 + bv_0$ son plus petit élément. (i) $m \mid a$ : la division $a = mq + r$ ( $0 \leq r < m$ ) donne $r = a(1 - qu_0) + b(-qv_0)$ , de la forme $au + bv$ ; si $r > 0$ , alors $r \in E$ et $r < m$ , contradiction ; donc $r = 0$ . De même $m \mid b$ . (ii) $m$ est le plus grand diviseur commun : $m \leq d$ car $m$ est un diviseur commun, et $d \mid au_0 + bv_0 = m$ donc $d \leq m$ . Ainsi $d = m$ .

Cette démonstration montre aussi que tout diviseur commun de $a$ et $b$ divise $d$ (point 3 du Théorème 1).

Théorème 4 (théorème de Bézout). $a$ et $b$ sont premiers entre eux si et seulement s’il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$ .

Démonstration : le sens direct est l’identité de Bézout (Théorème 3) avec $d = 1$ . Réciproquement, si $au + bv = 1$ , tout diviseur commun de $a$ et $b$ divise 1, donc $\text{PGCD}(a, b) = 1$ .

Corollaire. Si $d = \text{PGCD}(a, b)$ , alors $\dfrac ad$ et $\dfrac bd$ sont premiers entre eux (diviser $au + bv = d$ par $d$ ).

Attention. Pour $d \geq 2$ , l’existence de $u, v$ avec $au + bv = d$ ne prouve pas que $d$ est le PGCD : $4 \times 2 + 6 \times 0 = 8$ mais $\text{PGCD}(4, 6) = 2$ . Elle prouve seulement que le PGCD divise $d$ .

Théorème 5 (théorème de Gauss). (démonstration exigible) Soit $a, b, c$ des entiers. Si $a \mid bc$ et si $a$ et $b$ sont premiers entre eux, alors $a \mid c$ .

Démonstration : par Bézout (Théorème 4), il existe $u, v$ avec $au + bv = 1$ . En multipliant par $c$ : $acu + bcv = c$ . Or $a \mid acu$ et $a \mid bc$ donc $a \mid bcv$ ; par combinaison linéaire, $a \mid c$ .

Corollaires.

Si $p$ est premier et $p \mid bc$ , alors $p \mid b$ ou $p \mid c$ (car si $p \nmid b$ , alors $\text{PGCD}(p, b) = 1$ ).
Si $a \mid c$ , $b \mid c$ et $\text{PGCD}(a, b) = 1$ , alors $ab \mid c$ . (Démonstration : $c = ak$ et $b \mid ak$ avec $b$ premier avec $a$ , donc $b \mid k$ : $k = bk'$ et $c = abk'$ .)

Exemples : $7 \mid 3n \Rightarrow 7 \mid n$ car $\text{PGCD}(7, 3) = 1$ ; un entier divisible par 3 et par 4 est divisible par 12. En revanche $6 \mid 2 \times 3$ sans que 6 divise 2 ou 3 : l’hypothèse « premiers entre eux » est indispensable.

Théorème 6 (équation diophantienne $ax + by = c$ ). L’équation $ax + by = c$ (avec $a, b$ entiers non nuls) admet des solutions entières si et seulement si $\text{PGCD}(a, b)$ divise $c$ . Elle en admet alors une infinité.

Démonstration : soit $d = \text{PGCD}(a, b)$ . Si $(x, y)$ est solution, $d$ divise $ax + by = c$ . Réciproquement, si $c = dc'$ , l’identité de Bézout $au + bv = d$ (Théorème 3) donne $a(uc') + b(vc') = c$ .

Méthodes

Méthode 1 — calculer un PGCD par l’algorithme d’Euclide.

Effectuer la division euclidienne de $a$ par $b$ : $a = bq + r$ .
Remplacer $(a, b)$ par $(b, r)$ et recommencer tant que le reste n’est pas nul (Théorème 2).
Le PGCD est le dernier reste non nul.

Exemple : $\text{PGCD}(252, 105)$ : $252 = 2 \times 105 + 42$ , $105 = 2 \times 42 + 21$ , $42 = 2 \times 21 + 0$ , donc $\text{PGCD}(252, 105) = 21$ . De même $\text{PGCD}(1071, 462) = 21$ .

def pgcd(a, b):
    """Algorithme d'Euclide : PGCD de deux entiers naturels."""
    while b != 0:
        a, b = b, a % b      # (a, b) <- (b, reste)
    return a

print(pgcd(252, 105))   # 21

Méthode 2 — trouver un couple de Bézout (algorithme d’Euclide étendu).

Effectuer l’algorithme d’Euclide (Méthode 1).
Remonter les égalités en partant de la dernière de reste non nul, en exprimant chaque reste comme combinaison de $a$ et $b$ .
Vérifier le couple obtenu par un calcul direct. Le couple n’est pas unique : si $(u, v)$ convient pour $au + bv = 1$ , alors $(u + kb, v - ka)$ convient aussi.

Exemple : $a = 35$ , $b = 12$ : $35 = 2 \times 12 + 11$ , $12 = 1 \times 11 + 1$ . Remontée : $1 = 12 - 11 = 12 - (35 - 2 \times 12) = 3 \times 12 - 1 \times 35$ , donc $35 \times (-1) + 12 \times 3 = 1$ . Autre exemple : $21 = 105 - 2 \times 42 = 105 - 2(252 - 2 \times 105) = 5 \times 105 - 2 \times 252$ , donc $252 \times (-2) + 105 \times 5 = 21$ .

def bezout(a, b):
    """Renvoie (d, u, v) avec d = PGCD(a, b) et a*u + b*v = d."""
    u0, v0, u1, v1 = 1, 0, 0, 1          # a = 1*a + 0*b ; b = 0*a + 1*b
    while b != 0:
        q, r = a // b, a % b
        a, b = b, r
        u0, u1 = u1, u0 - q * u1         # on met a jour les coefficients
        v0, v1 = v1, v0 - q * v1
    return a, u0, v0

print(bezout(35, 12))    # (1, -1, 3)
print(bezout(252, 105))  # (21, -2, 5)

Méthode 3 — montrer que deux entiers sont premiers entre eux.

Exhiber une relation de Bézout $au + bv = 1$ (Théorème 4), souvent en combinant les deux expressions ; ou montrer qu’un diviseur commun divise 1 (combinaison linéaire) ; ou appliquer le lemme d’Euclide (Théorème 2) si la division est simple.
Application aux fractions : $\dfrac ab$ est irréductible si et seulement si $a$ et $b$ sont premiers entre eux ; on rend une fraction irréductible en divisant par le PGCD (corollaire du Théorème 4).

Exemple : $(n + 1) \times 1 + n \times (-1) = 1$ donc $\text{PGCD}(n, n + 1) = 1$ . Fraction : $\dfrac{252}{105} = \dfrac{12}{5}$ après division par 21.

Méthode 4 — résoudre une équation diophantienne $ax + by = c$ .

Calculer $d = \text{PGCD}(a, b)$ ; si $d \nmid c$ , pas de solution (Théorème 6). Sinon diviser l’équation par $d$ : on se ramène à $a'x + b'y = c'$ avec $a'$ et $b'$ premiers entre eux.
Trouver une solution particulière $(x_0, y_0)$ : par tâtonnement, ou en multipliant un couple de Bézout (Méthode 2) par $c'$ .
Soustraire : $a'(x - x_0) = b'(y_0 - y)$ ; comme $b' \mid a'(x - x_0)$ et $\text{PGCD}(a', b') = 1$ , le Théorème 5 (Gauss) donne $b' \mid x - x_0$ , d’où $x = x_0 + b'k$ puis $y = y_0 - a'k$ , $k \in \mathbb{Z}$ .
Vérifier réciproquement que tous ces couples conviennent.

$\boxed{x = x_0 + b'k, \quad y = y_0 - a'k, \quad k \in \mathbb{Z}}$

Exemple : $5x - 3y = 1$ : solution particulière $(2, 3)$ ; $5(x - 2) = 3(y - 3)$ , Gauss donne $3 \mid x - 2$ , d’où $x = 2 + 3k$ et $y = 3 + 5k$ . Exemple sans solution : $6x + 9y = 5$ car $3 \nmid 5$ . Exemple avec Bézout : $35x + 12y = 4$ : de $35 \times (-1) + 12 \times 3 = 1$ , on tire $(x_0, y_0) = (-4, 12)$ , puis $x = -4 + 12k$ , $y = 12 - 35k$ .

Méthode 5 — résoudre un problème de PGCD en posant $x = dx'$ , $y = dy'$ .

Si $\text{PGCD}(x, y) = d$ est imposé, poser $x = dx'$ et $y = dy'$ avec $x'$ et $y'$ premiers entre eux (corollaire du Théorème 4).
Traduire les autres contraintes sur $(x', y')$ et résoudre ce problème plus petit.
Revenir à $(x, y)$ en multipliant par $d$ , et vérifier.

Exemple : couples $(x, y) \in \mathbb{N}^2$ tels que $\text{PGCD}(x, y) = 6$ et $x + y = 60$ : $x = 6x'$ , $y = 6y'$ avec $x' + y' = 10$ et $\text{PGCD}(x', y') = 1$ ; les couples valables sont $(1, 9), (3, 7), (7, 3), (9, 1)$ , d’où $(6, 54), (18, 42), (42, 18), (54, 6)$ .

Définitions

Théorèmes et propriétés

Méthodes

Reste informé