Théorème de Bézout : au + bv = 1, la démonstration exigée et la remontée d'Euclide

Le théorème de Bézout se place dans l'arithmétique de l'option maths expertes, juste après le PGCD et l'algorithme d'Euclide. Il sert ensuite à démontrer le théorème de Gauss et à trouver l'inverse d'un entier modulo n.

Deux énoncés à ne pas confondre

Deux entiers a et b sont premiers entre eux lorsque PGCD(a ; b) = 1, c'est-à-dire lorsque leurs seuls diviseurs communs sont 1 et −1.

Le premier énoncé, souvent appelé identité de Bézout, vaut pour n'importe quel couple : si a et b ne sont pas tous deux nuls, il existe (u ; v) ∈ ℤ² tel que au + bv = PGCD(a ; b). Le second, le théorème de Bézout, ne parle que du cas où le PGCD vaut 1, mais il est une équivalence : PGCD(a ; b) = 1 ⇔ il existe (u ; v) ∈ ℤ² tel que au + bv = 1.

La différence compte. L'égalité 4 × 2 + 6 × 1 = 14 n'implique pas que PGCD(4 ; 6) vaut 14 ; elle dit seulement que le PGCD, ici 2, divise 14. Le passage de « au + bv = d » à « PGCD = d » n'est permis que pour d = 1.

Démontrer Bézout, comme le programme le demande

Le programme de 2019 cite parmi les démonstrations exigibles l'« écriture du PGCD de a et b sous la forme ax + by ». On note d = PGCD(a ; b) et E l'ensemble des entiers strictement positifs de la forme au + bv, avec u et v entiers.

E n'est pas vide. Si a ≠ 0, |a| = a × (±1) + b × 0 appartient à E ; sinon b ≠ 0 et |b| appartient à E. Toute partie non vide de ℕ a un plus petit élément : on note m = au₀ + bv₀ le plus petit élément de E.

m divise a. On écrit la division euclidienne a = mq + r, avec 0 ≤ r < m. Alors r = a − (au₀ + bv₀)q = a(1 − qu₀) + b(−qv₀). Si r était strictement positif, il appartiendrait à E tout en étant plus petit que m, ce qui contredit la définition de m. Donc r = 0 et m divise a. Le même raisonnement montre que m divise b.

m = d. m est un diviseur commun positif de a et b, donc m ≤ d. Inversement, d divise a et b, donc il divise au₀ + bv₀ = m, et comme m > 0, d ≤ m. Ainsi d = m = au₀ + bv₀.

Le théorème s'en déduit. Si PGCD(a ; b) = 1, l'identité donne u et v avec au + bv = 1. Réciproquement, si au + bv = 1, tout diviseur commun positif de a et b divise au + bv = 1, donc vaut 1.

Une conséquence sert dans les équations : ax + by = c a des solutions entières si et seulement si PGCD(a ; b) divise c. Ainsi 6x + 15y = 4 n'en a aucune, puisque 3 divise le membre de gauche et pas 4, alors que 6x + 15y = 9 en a, par exemple (−1 ; 1). La recherche de toutes les solutions demande le théorème de Gauss.

Trouver u et v en remontant l'algorithme d'Euclide

La méthode se fait en deux temps. On descend : on écrit les divisions euclidiennes jusqu'au reste 1. On remonte : on isole le reste 1 dans la dernière division, puis on remplace, ligne après ligne, chaque reste par son expression tirée de la division précédente, en gardant les deux derniers nombres sous forme de facteurs et sans développer. On vérifie toujours le résultat final par un calcul direct.

Exemple 1 · Un couple de Bézout pour 59 et 27, et l'inverse de 27 modulo 59

Descente. 59 = 2 × 27 + 5 ; 27 = 5 × 5 + 2 ; 5 = 2 × 2 + 1. Le dernier reste non nul est 1 : 59 et 27 sont premiers entre eux.

Remontée. De la dernière ligne, 1 = 5 − 2 × 2. La deuxième donne 2 = 27 − 5 × 5, donc 1 = 5 − 2 × (27 − 5 × 5) = 11 × 5 − 2 × 27. La première donne 5 = 59 − 2 × 27, donc 1 = 11 × (59 − 2 × 27) − 2 × 27 = 11 × 59 − 24 × 27.

Vérification. 11 × 59 = 649 et 24 × 27 = 648 : la différence vaut bien 1. Un couple de Bézout est (u ; v) = (11 ; −24).

Modulo 59, l'égalité devient 27 × (−24) ≡ 1 [59], et −24 ≡ 35 [59]. L'inverse de 27 modulo 59 est 35 : c'est la capacité « déterminer un inverse de a modulo n lorsque a et n sont premiers entre eux » du programme, détaillée dans l'article sur les congruences.

Exemple 2 · Montrer que n et 2n + 1 sont premiers entre eux

Rédaction. Pour tout n ∈ ℕ*, (2n + 1) × 1 + n × (−2) = 1. Il existe donc des entiers u = 1 et v = −2 tels que (2n + 1)u + nv = 1 : d'après le théorème de Bézout, n et 2n + 1 sont premiers entre eux.

Avec des expressions en n, on ne passe pas par l'algorithme : on cherche directement une combinaison qui élimine n et donne 1. Si elle donne un autre nombre, il faut revenir à la méthode du PGCD qui dépend de n.

La figure : descendre, puis remonter

La figure reprend l'exemple 1. À gauche, les trois divisions euclidiennes apparaissent une par une, de 59 = 2 × 27 + 5 jusqu'au reste 1. À droite, la remontée s'écrit ensuite ligne par ligne : 1 = 5 − 2 × 2, puis le remplacement de 2, puis celui de 5, jusqu'à 1 = 11 × 59 − 24 × 27. Le dernier cadre donne le couple (11 ; −24) et l'inverse de 27 modulo 59. On lit sur la figure que chaque ligne de remontée utilise une ligne de descente, prise dans l'ordre inverse.

Les erreurs sur Bézout qui coûtent des points

• Conclure PGCD(a ; b) = d à partir de au + bv = d avec d ≠ 1.
• Développer les produits pendant la remontée : on perd la trace de quels nombres sont a et b, et l'on aboutit à une égalité juste mais inutile.
• Oublier la vérification finale, alors qu'une erreur de signe dans la remontée est fréquente et se voit en un calcul.
• Parler « du » couple de Bézout : il n'est pas unique. Si au + bv = 1, alors a(u + kb) + b(v − ka) = 1 pour tout entier k.

Trois exercices corrigés sur Bézout

Exercice 1 · Deux expressions en n premières entre elles

Énoncé. Montrer que, pour tout n ∈ ℕ, les entiers 12n + 5 et 5n + 2 sont premiers entre eux.

Correction. On élimine n : 5(12n + 5) − 12(5n + 2) = 60n + 25 − 60n − 24 = 1. Avec u = 5 et v = −12, on a (12n + 5)u + (5n + 2)v = 1 ; d'après le théorème de Bézout, 12n + 5 et 5n + 2 sont premiers entre eux.

Exercice 2 · Un couple de Bézout pour 97 et 35, en cinq divisions

Énoncé. Justifier que 97 et 35 sont premiers entre eux et déterminer un couple d'entiers (u ; v) tel que 97u + 35v = 1. En donner un deuxième.

Correction. Descente : 97 = 2 × 35 + 27 ; 35 = 1 × 27 + 8 ; 27 = 3 × 8 + 3 ; 8 = 2 × 3 + 2 ; 3 = 1 × 2 + 1. Le dernier reste non nul est 1, donc PGCD(97 ; 35) = 1.

Remontée : 1 = 3 − 2 ; puis 2 = 8 − 2 × 3 donne 1 = 3 − (8 − 2 × 3) = 3 × 3 − 8 ; puis 3 = 27 − 3 × 8 donne 1 = 3 × 27 − 10 × 8 ; puis 8 = 35 − 27 donne 1 = 13 × 27 − 10 × 35 ; enfin 27 = 97 − 2 × 35 donne 1 = 13 × 97 − 36 × 35.

Vérification : 13 × 97 = 1 261 et 36 × 35 = 1 260. Le couple (13 ; −36) convient. En ajoutant 35 à u et en retranchant 97 à v, (48 ; −133) convient aussi : 97 × 48 + 35 × (−133) = 4 656 − 4 655 = 1.

Exercice 3 · Premier avec b et avec c, donc premier avec bc

Énoncé. Soient a, b, c des entiers non nuls. Montrer que si a est premier avec b et avec c, alors a est premier avec bc.

Correction. D'après le théorème de Bézout, il existe des entiers u, v, s, t tels que au + bv = 1 et as + ct = 1. En multipliant membre à membre : 1 = (au + bv)(as + ct) = a(uas + uct + bvs) + bc(vt).

Les nombres U = uas + uct + bvs et V = vt sont entiers et vérifient aU + bcV = 1. Par la réciproque du théorème de Bézout, a et bc sont premiers entre eux. Ce résultat sert, par exemple, à passer de PGCD(p ; q) = 1 à PGCD(p ; q³) = 1.