L'identité et le théorème de Bézout

L'algorithme d'Euclide donne le PGCD. En le parcourant à l'envers, il donne bien plus : une écriture du PGCD comme combinaison des deux nombres de départ.

L'identité de Bézout

Pour tous entiers a et b, il existe des entiers u et v tels que

a u + b v = PGCD(a , b)

Les coefficients u et v s'appellent les coefficients de Bézout. Ils ne sont pas uniques.

1071 × (-3) + 462 × 7 = -3213 + 3234 = 21 = PGCD(1071 , 462)   ✔

Les trouver : l'algorithme d'Euclide étendu

On remonte les divisions successives en exprimant chaque reste à partir des deux lignes précédentes.

Descente (Euclide) :

   1071 = 2 × 462 + 147      ->    147 = 1071 - 2×462
    462 = 3 × 147 +  21      ->     21 = 462 - 3×147
    147 = 7 ×  21 +   0

Remontée :

   21 = 462 - 3 × 147
      = 462 - 3 × (1071 - 2 × 462)
      = 462 - 3 × 1071 + 6 × 462
      = 7 × 462 - 3 × 1071

   ->  u = -3   et   v = 7

La vérification est immédiate et devrait être systématique : -3 × 1071 + 7 × 462 = -3213 + 3234 = 21 ✔.

Le théorème de Bézout

C'est le cas particulier le plus utile, et c'est une équivalence :

a et b sont PREMIERS ENTRE EUX   <=>   il existe u, v tels que  a u + b v = 1

Le sens direct découle de l'identité. Le sens réciproque est tout aussi simple : si au + bv = 1, tout diviseur commun de a et b divise 1, donc vaut 1.

5 × 2 + 3 × (-3) = 10 - 9 = 1      ->  5 et 3 sont premiers entre eux

Cette équivalence est précieuse : elle transforme une propriété de divisibilité — difficile à manipuler — en une égalité algébrique, que l'on peut reporter dans d'autres calculs.

L'application majeure : l'inverse modulaire

Si a et n sont premiers entre eux, Bézout fournit u et v tels que :

a u + n v = 1        d'où        a u ≡ 1  (mod n)

Autrement dit, u est l'inverse de a modulo n. C'est le calcul qui permet de « diviser » en arithmétique modulaire, et c'est exactement ce que fait RSA pour construire la clé de déchiffrement à partir de la clé de chiffrement.

inverse de 5 modulo 3 :  5 × 2 ≡ 10 ≡ 1 (mod 3)   ->  l'inverse est 2

L'algorithme d'Euclide étendu est donc bien plus qu'une curiosité scolaire : c'est la routine qu'exécute votre navigateur à chaque connexion sécurisée.

En résumé

• Identité de Bézout : il existe toujours u, v avec au + bv = PGCD(a , b).
• On les obtient en remontant l'algorithme d'Euclide.
• Les coefficients ne sont pas uniques.
• Théorème de Bézout : a et b premiers entre eux ⟺ au + bv = 1 a une solution.
• L'équivalence transforme une divisibilité en égalité algébrique.
• Application : le calcul de l'inverse modulaire, au cœur de RSA.