Algorithme d'Euclide étendu

Un article de Wikipédia, l'encyclopédie libre.

L'algorithme d'Euclide étendu est une version de l'algorithme d'Euclide ; à partir de deux entiers a et b, l'algorithme calcule leur plus grand commun diviseur (P.G.C.D.) ainsi que deux entiers x et y tels que ax + by = pgcd(a,b). L'algorithme d'Euclide permet d'obtenir de tels entiers parce qu'à chaque étape de l'algorithme, on n'a que des sommes de multiples de a et b.

L'équation ax + by = pgcd(a,b) est particulièrement utile quand a et b sont premiers entre eux  : x est alors l'inverse pour la multiplication de a modulo b.

Considérons par exemple le calcul du pgcd(120,23) avec l'algorithme d'Euclide :

Dividende	Diviseur	Quotient	Reste
120	23	5	5
23	5	4	3
5	3	1	2
3	2	1	1
2	1	2	0

120 ÷ 23 = 5 reste 5
23  ÷ 5  = 4 reste 3
5   ÷ 3  = 1 reste 2
3   ÷ 2  = 1 reste 1
2   ÷ 1  = 2 reste 0

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

Reste	=	Dividende	-	Quotient	×	Diviseur
5	=	120	-	5	×	23
3	=	23	-	4	×	5
2	=	5	-	1	×	3
1	=	3	-	1	×	2
0	=	2	-	2	×	1

120 ÷ 23 = 5 reste 5   ⇒ 5 = 120 - 5×23
23  ÷ 5  = 4 reste 3   ⇒ 3 = 23  - 4×5
5   ÷ 3  = 1 reste 2   ⇒ 2 = 5   - 1×3
3   ÷ 2  = 1 reste 1   ⇒ 1 = 3   - 1×2
2   ÷ 1  = 2 reste 0   ⇒ 0 = 2   - 2×1

Observons que 120 et 23 apparaissent dans la 1ere ligne.D'autre part, la valeur la plus à droite dans chaque ligne (à partir de la 2eme ligne du tableau) est le reste de la ligne précédente, et le dividende est - dans chaque égalité - le reste obtenu deux lignes plus haut. Nous pouvons ainsi calculer progressivement chaque reste successif comme sommes de produits des deux valeurs initiales 120 et 23.

Ici nous récrivons les deuxièmes équations dans la table ci-dessus mentionnée:

5	=	120	-	5	×	23	=						=	1	×	120	-	5	×	23
3	=	23	-	4	×	5	=	1×23	-	4	×	(1×120 - 5×23)	=	-4	×	120	+	21	×	23
2	=	5	-	1	×	3	=	(1×120 - 5×23)	-	1	×	(-4×120 + 21×23)	=	5	×	120	-	26	×	23
1	=	3	-	1	×	2	=	(-4×120 + 21×23)	-	1	×	(5×120 - 26×23)	=	-9	×	120	+	47	×	23

Dans la méthode de calcul avec les coefficients de Bezout, les chiffres marqués en vert sont appelés coefficients de Bezout (u et v). En bleu ce sont les quotients (q).

et .

L'état initial est : u₀ = 1, u₁ = 0, v₀ = 0 et v₁ = 1.

Remarquons que la dernière ligne donne 1 = -9×120 + 47×23, et nous fournit exactement ce que nous voulons : x = -9 et y = 47.

Ceci signifie que -9 est l'inverse pour la multiplication de 120 modulo 23, parce que 1 = -9 × 120 (mod 23).

Voici en Javascript l'implémentation de l'algorithme d'Euclide étendu qui devrait fonctionner dans la plupart des navigateurs :

// Ce programme ne fonctionne qu'avec des entiers naturels
// demande les données à l'utilisateur et convertit les chaînes de caractères en entiers
var a = parseInt(prompt("Entrer un entier naturel  a",0))
var b = parseInt(prompt("Entrer un entier naturel  b",0))

// On sauvegarde les valeurs de a et b.
a0 = a;
b0 = b;

// Initialisations. On laisse invariant p*a0 + q*b0 = a et  r*a0 + s*b0 = b.
p = 1; q = 0;
r = 0; s = 1;

// La boucle principale:
while (b != 0) { 
  c = a % b;
  quotient = Math.floor(a/b);  //Javascript n'a pas d'opération de division entière.
  a = b;
  b = c;
  nouveau_r = p - quotient * r; nouveau_s = q - quotient * s;
  p = r; q = s;
  r = nouveau_r; s = nouveau_s;
}

// Affiche le résultat.

alert("pgcd(" + a0 + "," + b0 + ")=" + p + "*" + a0 + "+(" + q + ")*" + b0 + "=" + a)

---

[modifier] Intégration en visual Basic

Public Function PGCD(a As Integer, b As Integer) As Integer
    
    If a < b Then
        Dim Temp As Integer     ' a doit être plus petit que b dans le cas contraire il y a échange
        Temp = a
        a = b
        b = Temp
    End If
    
    Dim reste As Integer
    reste = a Mod b
    
    Do Until reste = 0
        a = b
        b = reste
       reste = a Mod b
    Loop
    
    PGCD = b
    
End Function

[modifier] Liens internes

Identité de Bezout