logo

Algorithme d'Euclide étendu



Algorithme d'Euclide étendu : encyclopédie mathématiques

wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.
Aller à : navigation, rechercher

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 (et v est de la même façon l'inverse modulaire de b, modulo a), ce qui est un cas particulièrement utile. L'algorithme d'Euclide étendu fournit également une méthode efficace non seulement pour déterminer 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[modifier | modifier le code]

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

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 PGCD √©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

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 2e ligne du tableau) est le reste de la ligne pr√©c√©dente, et le dividende est ‚ÄĒ dans chaque √©galit√© √† partir de la 3e 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 :

r = u √ó a + v √ó b
120 = 1 √ó 120 + 0 √ó 23
23 = 0 √ó 120 + 1 √ó 23
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

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.

L'algorithme[modifier | modifier le code]

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.

r u v
r0 = a u0 = 1 v0 = 0
r1 = b u1 = 0 v1 = 1
… … …
ri-1 ui-1 vi-1
ri ui vi
ri-1 - (ri-1√∑ri)ri ui-1 - (ri-1√∑ri)ui vi-1 - (ri-1√∑ri)vi
… … …
rn= pgcd(a, b) un = u vn = v
0 un+1 vn+1

On obtient donc une suite (ri, ui, vi), r√©currente d'ordre 2, n√©cessairement finie car la suite (rn) est strictement d√©croissante au plus tard √† partir du second rang, et parce que l'on ne peut diviser par 0. On a pos√© n+1 le premier indice tel que rn+1=0 qui est donc l'indice maximal d'un √©l√©ment de la suite. On peut justifier cette construction, plus pr√©cis√©ment justifier que l'avant dernier terme de la suite, soit (rn, un, vn) fournit bien le pgcd de a et b et deux coefficients de B√©zout u et v v√©rifiant pgcd(a, b)= ua + bv. En effet, il est imm√©diat, par r√©currence √† partir des deux termes pr√©c√©dents, qu'√† chaque √©tape ri= aui + bvi (voir le tableau). On en d√©duit que tout diviseur de a et b divise les ri, combinaisons lin√©aires de a et b, en particulier rn. Enfin on remarque que si un entier divise ri+1 et ri, il divise ri-1 (voir le tableau) ; comme rn divise bien rn+1 = 0 et rn, on en d√©duit par r√©currence qu'il divise tous les ri, en particulier r0 = a et r1 = b, c'est donc bien le pgcd de a et b.

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 (ri, ui, vi) fournit directement un algorithme tr√®s simple 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 ui et vi d√©pendent tous deux de celui des ri, mais sont ind√©pendants entre eux. On peut donc simplifier cet algorithme en ne calculant que (ri, ui). Cela suffit si 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.

Complexité de l'algorithme[modifier | modifier le code]

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 (ri) 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 (ri) dans l'ordre inverse, soit (rn + 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, rn + 1 - 0, est bien 0, le second, rn + 1 - 1, est le PGCD de a et b. En notant d = pgcd(a, b), et (fi) la suite de Fibonacci, on obtient donc :

rn + 1 - i ‚Č• d.fi

et donc (th√©or√®me de Lam√©) :

r1 = b ‚Č• d.fn 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 fn ~ [(1+‚ąö5)/2]n (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.

Généralisations[modifier | modifier le code]

Les entiers relatifs[modifier | modifier le code]

On pourrait facilement ramener le calcul du pgcd et des coefficients de Bézout de deux entiers relatifs, à celui de deux entiers naturels. L'algorithme indiqué s'applique cependant sans aucune modification aux entiers relatifs. Il suffit de remarquer que, dans la division euclidienne, c'est alors la valeur absolue du reste qui est plus petite que la valeur absolue du diviseur, ce qui assure la terminaison de l'algorithme. En effet, si on définit de la même façon à partir de deux entiers relatifs a et b la suite (ri, ui, vi), c'est cette fois-ci la suite des valeurs absolues des ri qui est strictement décroissante à partir du second rang. On montre de façon identique que rn, l'avant dernier terme de la suite, est un diviseur commun de a et de b, multiple de tout diviseur commun de a et de b, c'est-à-dire un plus grand (au sens de la divisibilité) diviseur commun de a et b, et donc le pgcd de a et b ou son opposé. Pour les mêmes raisons les nombres un, vn satisfont l'identité de Bézout.

Les anneaux euclidiens[modifier | modifier le code]

L'anneau des entiers relatifs est un anneau euclidien, et ce sont les seules propri√©t√©s utiles pour l'algorithme d'Euclide √©tendu. Celui-ci se g√©n√©ralise donc directement aux anneaux euclidiens, et se justifie de la m√™me fa√ßon. Seules changent les op√©rations de base, et la division. Comme pour les entiers relatifs, il n'y a pas forc√©ment unicit√©, et l'algorithme d√©termine un plus grand diviseur commun, les autres s'en d√©duisent par multiplication par une unit√© (1 et -1. pour les entiers relatifs). De m√™me que pour les entiers, il peut √™tre l√©g√®rement modifi√© quand le pgcd est d√©fini de fa√ßon unique gr√Ęce √† une condition suppl√©mentaire, de fa√ßon √† ce que le r√©sultat v√©rifie celle-ci.

Bibliographie[modifier | modifier le code]

Michel Demazure, Cours d'alg√®bre : primalit√©, divisibilit√©, codes [d√©tail des √©ditions]

Article connexe[modifier | modifier le code]

Développement en fraction continue d'un rationnel

wikipediaCet article est issu de l'encyclopédie libre Wikipedia.
Vous pouvez consulter l'article ici ainsi que son historique.
Les textes et les images sont disponibles sous les termes de la Licence de documentation libre GNU.


maths - prof de maths - cours particuliers haut de pagehaut Retrouvez cette page sur ilemaths l'île des mathématiques
© Tom_Pascal & Océane 2015