Algorithme d'Euclide étendu - Définition

Introduction

L'algorithme d'Euclide étendu est une variante de l'algorithme d'Euclide qui permet, à partir de deux entiers a et b, de calculer non seulement leur plus grand commun diviseur (PGCD), mais aussi un de leurs couples de coefficients de Bézout (deux entiers u et v tels que au + bv = PGCD(a, b)). Quand a et b sont premiers entre eux, u est alors l'inverse pour la multiplication de a modulo b, ce qui est un cas particulièrement utile. L'algorithme d'Euclide étendu fournit également une méthode efficace non seulement pour déteminer quand une équation diophantienne ax+by = c possède une solution, ce que permet déjà l'algorithme d'Euclide simple, mais également pour en calculer dans ce cas une solution particulière, dont on déduit facilement la solution générale.

Comme l'algorithme d'Euclide, l'algorithme étendu se généralise aux anneaux euclidiens, tels celui des polynômes à une variable sur un corps commutatif. De même que pour les entiers, il permet alors de calculer l'inverse d'un polynôme modulo un polynôme avec lequel il est premier, et donc des calculs d'inverse dans les anneaux ou corps construits par quotient sur l'anneau des polynômes : corps de rupture, corps finis …

Exemple introductif

Considérons par exemple le calcul du PGCD de 120 et 23 avec l'algorithme d'Euclide :

Dans ce cas, le reste obtenu à l'avant dernière ligne donne le PGCD égal à 1 ; c'est-à-dire que 120 et 23 sont premiers entre eux. Maintenant présentons autrement les divisions précédentes :

Observons que 120 et 23 apparaissent sur les deux premières lignes. D'autre part, la valeur la plus à droite dans chaque ligne (à partir de la 2^e ligne du tableau) est le reste de la ligne précédente, et le dividende est — dans chaque égalité à partir de la 3^e ligne — le reste obtenu deux lignes plus haut. Nous pouvons ainsi calculer progressivement chaque reste successif comme combinaison linéaire des deux valeurs initiales 120 et 23.

Cependant cette méthode n'est pas la plus efficace. On écrit d'abord ces calculs de façon à faire apparaître un algorithme plus direct :

Remarquons que la dernière ligne donne 1 = -9×120 + 47×23, et nous fournit exactement ce que nous voulons : u = -9 et v = 47. Ceci signifie que -9 est l'inverse pour la multiplication de 120 modulo 23, parce que 1 = -9 × 120 (mod 23). De même 47 est l'inverse, pour la multiplication modulo 120, de 23.

On a en bleu les calculs successifs qui conduisent au pgcd par reste de la division des deux nombres précédents (algorithme d'Euclide ordinaire). On a noté en jaune les quotients correspondants. Les deux colonnes vertes donnent les calculs successifs qui aboutissent aux coefficients de Bezout (u et v). On peut vérifier que ces coefficients se calculent à partir des deux coefficients les précédant dans la même colonne, à l'aide des quotients de la colonne jaune : les formules sont précisées dans le tableau du paragraphe suivant.