Algorithme d'Euclide étendu

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, qui est parfois attribué à W. A. Blankinship[3] - [4] et appelé alors algorithme de Blankinship :

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 Bézout (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.

On présente, sous forme de suite, le calcul du PGCD et des coefficients de Bézout pour deux entiers naturels a et b. Le quotient (entier) de x par y est noté x ÷ y. Pour a = 120 et b = 23, on vérifiera que le calcul conduit aux trois colonnes r, u et v de l'exemple.

On obtient donc (cf. « finitude et exactitude de l'algorithme d'Euclide simple ») une suite finie (r_i, u_i, v_i), récurrente d'ordre 2, d'indice maximal n + 1, telle que r_n+1 = 0 et r_n = pgcd(a, b). De plus, à chaque étape, r_i = au_i + bv_i, par récurrence à partir des deux termes précédents (voir le tableau). En particulier, pgcd(a, b) = r_n = au_n + bv_n.

Au cours de la démonstration, on n'a jamais eu besoin de supposer le théorème de Bézout, et de fait, celle-ci fournit également une démonstration de ce théorème pour deux entiers naturels et on le déduit immédiatement pour deux entiers relatifs.

La définition par récurrence de la suite (r_i, u_i, v_i) fournit directement un algorithme pour calculer les coefficients de Bézout. L'algorithme va calculer à chaque étape deux triplets consécutifs de la suite (deux lignes consécutives du tableau ci-dessus). Par exemple on obtient le pgcd et les deux coefficients de Bézout par la définition récursive suivante :

eucl(r, u, v, 0, u', v') = (r, u, v)
eucl(r, u, v, r', u', v') = eucl(r', u', v', r - (r÷r')*r', u - (r÷r')*u', v - (r÷r')*v')  pour r' ≠ 0
euclid(a, b) = eucl(a, 1, 0, b, 0, 1)

On a alors euclid(a,b) = eucl(a, 1, 0, b, 0, 1) = (pgcd(a, b), u, v) avec pgcd(a, b)= a*u + b*v.

De façon à peu près équivalente, on a l'algorithme impératif suivant, qui utilise une boucle while, et une affectation simultanée (ou en parallèle) de plusieurs variables (ce qui est possible dans certains langages comme Python, Ruby, etc.). L'affectation est notée « := ».

Entrée : a, b entiers (naturels)
Sortie : r entier (naturel) et  u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v
Initialisation : (r, u, v, r', u', v') := (a, 1, 0, b, 0, 1)
                  q  quotient entier
les égalités r = a*u+b*v et r' = a*u'+b*v' sont des invariants de boucle
tant que (r' ≠ 0) faire
    q := r÷r' 
    (r, u, v, r', u', v') := (r', u', v', r - q *r', u - q*u', v - q*v')
    fait
renvoyer (r, u, v)

Pour les langages de programmation qui ne disposent pas d'une telle affectation simultanée, on introduit des variables auxiliaires pour conserver les valeurs des autres variables le temps du calcul, par exemple comme suit :

 Entrée : a, b entiers (naturels)
Sortie : r entier (naturel) et  u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v
Initialisation : r := a, r' := b, u := 1, v := 0, u' := 0, v' := 1
                  q  quotient entier
                  rs, us, vs  variables de stockage intermédiaires
les égalités r = a*u+b*v et r' = a*u'+b*v' sont des invariants de boucle
tant que (r' ≠ 0) faire
    q := r÷r'
    rs := r, us := u, vs := v,
    r := r', u := u', v := v',
    r' := rs - q*r', u' = us - q*u', v' = vs - q*v'
   fait
renvoyer (r, u, v)

Les calculs de u_i et v_i dépendent tous deux de celui des r_i, mais sont indépendants entre eux. On peut donc simplifier cet algorithme en ne calculant que (r_i, u_i). Cela suffit si l'on cherche l'inverse de a modulo b (cas où a et b sont premiers entre eux). On peut de toute façon calculer ensuite directement le second coefficient à partir du premier.

Cormen et al. dans Introduction à l'algorithmique en donne une version récursive[5] :

Entrée : a, b entiers (naturels)
Sortie : un triplet (d, u, v) où d est le pgcd de a et b, et u, v sont des entiers relatifs avec au + bv = d
fonction euclide-étendu(a, b)
    si b = 0 alors
          retourner (a, 1, 0)
    sinon
          (d', u', v') := euclide-étendu(b, a mod b)
          retourner (d', v', u' - (a÷b)v')

L'algorithme d'Euclide étendu a la même structure que l'algorithme d'Euclide : le nombre d'itérations est le même, seul change le nombre d'opérations à chaque itération.

Pour évaluer le nombre de pas d'itérations, c'est-à-dire l'entier noté n + 1 ci-dessus, on suppose tout d'abord que a ≥ b, pour que la suite (r_i) soit décroissante dès le début. On remarque alors que le quotient est, par construction, toujours supérieur ou égal à 1. En prenant la suite (r_i) dans l'ordre inverse, soit (r_{n + 1 - i}), et en remplaçant à chaque étape le quotient par 1, on reconnait la suite de Fibonacci, à la différence que si le premier terme, r_{n + 1 - 0}, est bien 0, le second, r_{n + 1 - 1}, est le PGCD de a et b. En notant d = pgcd(a, b), et (f_i) la suite de Fibonacci, on obtient donc :

r_{n + 1 - i} ≥ d.f_i

et donc (théorème de Lamé) :

r₁ = b ≥ d.f_n où le nombre d'itérations de l'algorithme est n+1.

Ce nombre est d'ailleurs effectivement atteint pour a et b deux nombres consécutifs de la suite de Fibonacci, ou multiples de ceux-ci : la suite de Fibonacci étant croissante, le quotient est bien 1 à chaque étape.

Comme f_n ~ [(1+√5)/2]ⁿ (voir l'article sur la suite de Fibonacci), le nombre d'itérations est donc en log b, à une constante multiplicative près.

Il n'est guère réaliste, sauf à ne manipuler que de petits nombres, de considérer que le coût des opérations effectuées à chaque itération, division, multiplication et soustraction, est constant. Si l'on suppose que celui-ci est linéaire en la taille de l'entrée (en binaire), on obtient une complexité en O(log²(sup(a, b))), c'est-à-dire, à une constante multiplicative près, celle de l'algorithme d'Euclide ordinaire.

Développement en fraction continue d'un rationnel