Voir la source de Algorithme d'Euclide étendu

En [[mathématiques]], l''''algorithme d'Euclide étendu''' est une variante de l'[[algorithme d'Euclide]]. À partir de deux entiers  ''a'' et ''b'', il calcule non seulement leur [[plus grand commun diviseur]] (PGCD), mais aussi un de leurs couples de [[théorème de Bachet-Bézout|coefficients de Bézout]], c'est-à-dire deux entiers ''u'' et ''v'' tels que ''au'' + ''bv'' = PGCD(''a'', ''b'')<ref>{{Ouvrage|prénom1=Marc|nom1=Hindry|titre=Arithmétique : primalité et codes, théorie analytique des nombres, équations diophantiennes, courbes elliptiques|éditeur=Calvage et Mounet|date=2008|isbn=978-2-916352-04-6|oclc=276993164}}.</ref>{{,}}<ref>{{Demazure1}}.</ref>. Quand ''a'' et ''b'' sont [[premiers entre eux]], ''u'' est alors l'inverse pour la multiplication de ''a'' [[Congruence sur les entiers|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. Alors que l'algorithme d'Euclide détermine quand une [[Équation diophantienne ax + by = c|équation diophantienne {{nobr|1=''ax'' + ''by'' = ''c''}}]] possède une solution, l'algorithme d'Euclide étendu en fournit également 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ôme]]s à 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 fini]]s, etc.

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

{| class="wikitable centre"
|-
|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. On présente autrement les divisions précédentes :

{| class="wikitable centre"
|Reste||=||Dividende||–||Quotient||×||Diviseur
|-
|{{fond or}}|5||=
||<font color="#aa0000">'''120'''</font>
||–||5||×
||<font color="#aa0000">'''23'''</font>
|-
|{{fond bleu}}|3||=
||<font color="#aa0000">'''23'''</font>
||–||4||×
|{{fond or}}|5
|-
|{{fond vert}}|2||=
|{{fond or}}|5
||–||1||×
|{{fond bleu}}|3
|-
|1||=
|{{fond bleu}}|3
||–||1||×
|{{fond vert}}|2
|-
|0||=
|{{fond vert}}|2
||–||2||×||1
|}

On remarque 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, qui est parfois attribué à W. A. Blankinship<ref>{{Article
|langue=en
|prénom=W. A.
|nom=Blankinship
|titre=A New Version of the Euclidean Algorithm
|périodique=[[American Mathematical Monthly]]
|date=1963
|numéro=70
|pages=742-745}}</ref>{{,}}<ref>{{Ouvrage
|prénom=Raymond
|nom=Séroul
|titre=Math-info. Informatique pour mathématiciens
|éditeur=[[InterÉditions]]
|collection=IIA Informatique, intelligence artificielle
|date=1995
|pages totales=395
|passage=147-151
|isbn=2-7296-0568-1
|ean=9782729605681}}</ref> et appelé alors ''algorithme de Blankinship'' :

{| class="wikitable centre"
!r  !!  colspan="12"|          !! = !! u             !! × !! a !! + !!   v           !! × !! b
|-
|{{fond bleu}}|120|| ||   ||   ||                   || ||  ||  ||    ||   || || ||              || = ||{{fond vert}}|1||× ||120|| + ||{{fond vert}}|0||× ||23
|-
|{{fond bleu}}|23||  ||   ||   ||                   || ||  ||  ||    ||   || || ||              || = ||{{fond vert}}|0||× ||120|| + ||{{fond vert}}|1||× ||23
|-
|{{fond bleu}}|5|| = ||120|| – ||{{fond or}}|5||×||23||  ||    ||   || || ||              || = ||{{fond vert}}|1||× ||120|| + ||{{fond vert}}|–5||× ||23
|-
|{{fond bleu}}|3|| = ||23|| –||{{fond or}}|4||×||5||  = ||1×23          || – ||4||×||(1×120 - 5×23)  || = ||{{fond vert}}|–4||×||120|| + ||{{fond vert}}|21||×||23
|-
|{{fond bleu}}|2|| = ||5|| – ||{{fond or}}|1||×||3|| =  ||(1×120 – 5×23)|| – ||1||×||(–4×120 + 21×23)|| = ||{{fond vert}}|5||× ||120|| + ||{{fond vert}}|-26||×||23
|-
|{{fond bleu}}|1|| = ||3|| – ||{{fond or}}|1||×||2|| = ||(–4×120 + 21×23) || – ||1||×||(5×120 - 26×23) || = ||{{fond vert}}|–9||×||120|| + ||{{fond vert}}|47||×||23
|}
On remarque que la dernière ligne donne {{nobr|1 {{=}} –9 × 120 + 47 × 23}}, et fournit exactement les valeurs recherchées : {{nobr|''u'' {{=}} –9}} et {{nobr|''v'' {{=}} 47}}. Ceci signifie que –9 est l'inverse pour la multiplication de 120 modulo 23, parce que {{nobr|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.

== Description ==
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é {{nobr|''x'' ÷ ''y''}}. Pour {{nobr|''a'' {{=}} 120}} et {{nobr|''b'' {{=}} 23}}, on vérifiera que le calcul conduit aux trois colonnes '''r''', '''u''' et '''v''' de l'exemple.
{| class="wikitable centre"
|-
! r
! u
! v
|-
|r<sub>0</sub> = a || u<sub>0</sub> = 1   || v<sub>0</sub> = 0
|-
|r<sub>1</sub> = b || u<sub>1</sub> = 0   || v<sub>1</sub> = 1
|-
|… || …   ||  …
|-
|r<sub>i–1</sub> || u<sub>i–1</sub>   ||   v<sub>i–1</sub>
|-
|r<sub>i</sub> || u<sub>i</sub>   ||   v<sub>i</sub>
|-
|r<sub>i–1</sub> - (r<sub>i–1</sub>÷r<sub>i</sub>)r<sub>i</sub> || u<sub>i–1</sub> – (r<sub>i–1</sub>÷r<sub>i</sub>)u<sub>i</sub>   || v<sub>i–1</sub> – (r<sub>i–1</sub>÷r<sub>i</sub>)v<sub>i</sub>
|-
|… || …   ||  …
|-
|r<sub>n</sub>= pgcd(a, b)|| u<sub>n</sub> = u   ||   v<sub>n</sub> = v
|-
|0 || u<sub>n+1</sub>   ||   v<sub>n+1</sub>
|}
On obtient donc (cf. « [[Algorithme d'Euclide#Démonstration de sa finitude et de son exactitude|finitude et exactitude de l'algorithme d'Euclide simple]] ») une suite finie {{nobr|(''r<sub>i</sub>'', ''u<sub>i</sub>'', ''v<sub>i</sub>'')}}, récurrente d'ordre 2, d'indice maximal {{nobr|''n'' + 1}}, telle que {{nobr|''r''<sub>''n'' + 1</sub> {{=}} 0}} et {{nobr|''r{{ind|n}}'' {{=}} pgcd(''a'', ''b'')}}. De plus, à chaque étape, {{nobr|''r<sub>i</sub>'' {{=}} ''au<sub>i</sub>'' + ''bv<sub>i</sub>''}}, par récurrence à partir des deux termes précédents (voir le tableau). En particulier, {{nobr|pgcd(''a'', ''b'') {{=}} ''r{{ind|n}}'' {{=}} ''au{{ind|n}}'' + ''bv{{ind|n}}''}}.

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

== Pseudo-code ==
La [[définition par récurrence]] de la suite {{nobr|(''r<sub>i</sub>'', ''u<sub>i</sub>'', ''v<sub>i</sub>'')}} 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 [[algorithme récursif|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 (informatique)|affectation]] simultanée (ou en parallèle) de plusieurs variables (ce qui est possible dans certains langages comme [[Python (langage)|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 [[invariant de boucle|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 [[Langage de programmation|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''<sub>''i''</sub> et ''v''<sub>''i''</sub> dépendent tous deux de celui des ''r''<sub>''i''</sub>, mais sont indépendants entre eux. On peut donc simplifier cet algorithme en ne calculant que {{nobr|(''r<sub>i</sub>'', ''u<sub>i</sub>'')}}. 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 [[Algorithme récursif|récursive]]<ref name=":0">{{Cormen2fr}}, Section 31.2.</ref> :
 '''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')

== Complexité de l'algorithme ==
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''<sub>''i''</sub>) 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''<sub>''i''</sub>) dans l'ordre inverse, soit (''r''<sub>''n'' + 1 - ''i''</sub>), 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''<sub>''n'' + 1 - 0</sub>, est bien 0, le second, ''r''<sub>''n'' + 1 - 1</sub>, est le PGCD de ''a'' et ''b''. En notant ''d'' = pgcd(''a'', ''b''), et (f<sub>''i''</sub>) la suite de Fibonacci, on obtient donc :
:<math>r_{n + 1 - i} \geqslant d \cdot f_i</math>
et donc (théorème de Lamé) :
:<math>r_1 = b \geqslant  d \cdot f_n</math> 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 <math display=inline>f_n \sim \left[\frac{1+\sqrt{5}}{2}\right]^n</math> (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 <math>O(\log^2(\sup(a,b)))</math>, c'est-à-dire, à une constante multiplicative près, celle de l'[[algorithme d'Euclide]] ordinaire.

== Généralisations ==
=== Les entiers relatifs ===
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 [[entier relatif|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 d'un algorithme|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 (''r''<sub>''i''</sub>, ''u''<sub>''i''</sub>, ''v''<sub>''i''</sub>), c'est cette fois-ci la suite des valeurs absolues des  ''r''<sub>''i''</sub> qui est strictement décroissante à partir du second rang. On montre de façon identique que ''r''<sub>''n''</sub>, 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 ''u''<sub>''n''</sub>, ''v''<sub>''n''</sub> satisfont l'identité de Bézout.

=== Les anneaux euclidiens ===
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 euclidienne|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 [[groupe des unités|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 que le résultat vérifie celle-ci.

== Notes et références ==
{{Références}}

==Article connexe==
[[Fraction continue#Développement en fraction continue d'un rationnel|Développement en fraction continue d'un rationnel]]

{{Portail|informatique théorique|arithmétique}}

[[Catégorie:Algorithme|Euclide]]
[[Catégorie:Euclide]]