Voir la source de Algorithme d'Euclide


En [[mathématiques]], l''''algorithme d'Euclide''' est un [[algorithme]] qui calcule efficacement le [[plus grand commun diviseur]] (PGCD) de deux [[entier relatif|entiers]], c'est-à-dire le plus grand entier qui [[divisibilité|divise]] les deux entiers, c'est-à-dire qu'ils sont tous les deux [[multiple (mathématiques)|multiples]] de celui-ci. C'est un des plus anciens algorithmes connus, mais il reste toujours d'actualité.

L'algorithme ne requiert pas de connaître la [[décomposition en produit de facteurs premiers|factorisation]] de ces deux nombres.

== Histoire ==
[[Fichier:Euklid.jpg|vignette|Peinture censée représenter le mathématicien Euclide d'Alexandrie, par le peintre [[Joos van Wassenhove]].]]

Selon [[Donald Knuth]], l'algorithme d'Euclide est l'un des plus anciens algorithmes<ref name=":1" />. Il est décrit dans le [[Livre VII des Éléments d'Euclide|livre VII]] (Proposition 1-3) des ''[[Éléments d'Euclide|Éléments]]'' d'[[Euclide]] (vers {{date-|-300}}) sous la forme de l'[[anthyphérèse]].  Il est aussi décrit dans le livre X (Proposition 2), mais pour un problème de façon [[géométrie|géométrique]] : comment trouver une « unité de mesure » commune pour deux longueurs de [[Segment (mathématiques)|segments]]. Il procède par [[soustraction]]s répétées de la longueur du plus court segment sur la longueur du plus long. Cela correspond à une adaptation de la méthode naïve de calcul de la [[division euclidienne]], telle que décrite dans l'article consacré. Pour ce problème géométrique, l'algorithme d'Euclide ne termine pas forcément (dans un langage plus moderne, cela correspond à exécuter l'algorithme d'Euclide pour des nombres réels).

L'algorithme n'a probablement pas été découvert par Euclide, qui aurait compilé des résultats d'autres mathématiciens dans ses ''Éléments''<ref name="Weil_1983">{{Ouvrage|lang=en|prénom1=A.|nom1=Weil|lien auteur1=André Weil|titre=Number Theory|sous-titre=An approach through history|lieu=Boston|éditeur=Birkhäuser|année=1983|page=4-6|isbn=978-0-8176-3141-3|bnf=36146878}}.</ref>{{,}}<ref name="Jones_1994">{{Chapitre|langue=en|auteur=[[Alexander Jones (historien des sciences)|Alexander Jones]]|titre ouvrage=Companion Encyclopedia of the History and Philosophy of the Mathematical Sciences|lieu=New York|éditeur=Routledge|année=1994|page=46-48|isbn= 978-1-13488755-2|titre=Greek mathematics to AD 300|url={{Google Livres|YrJSDwAAQBAJ|page spéciale=PT46}}}}.</ref>. Pour le mathématicien et historien [[Bartel Leendert van der Waerden|B. L. van der Waerden]], le livre VII vient d'un livre de [[théorie des nombres]] écrit par un mathématicien de l'école de Pythagore<ref name="van_der_Waerden_1954">{{ouvrage|lang=en|lien auteur=Bartel Leendert van der Waerden|nom=van der Waerden|prénom=B. L.|année=1954|titre=Science Awakening|traducteur=Arnold Dresden|éditeur=P. Noordhoff|lieu=Groningen|page=114-115}}.</ref>. L'algorithme était probablement connu d'[[Eudoxe de Cnide]] (vers {{date-|-375}})<ref name="Knuth, p. 318">{{harvnb|Knuth|1997|p=318}}.</ref>{{,}}<ref>{{article|lang=en|auteur=[[Kurt von Fritz]]|année=1945|titre=The Discovery of Incommensurability by Hippasus of Metapontum|journal=[[Annals of Mathematics]]|volume=46|page=242-264|jstor=1969021|numéro=2}}.</ref>. Il se peut même que l'algorithme ait existé avant Eudoxe<ref>{{ouvrage|lang=en|lien auteur=Thomas Heath|nom=Heath|prénom=T. L.|année=1949|titre=Mathematics in Aristotle|éditeur=Oxford Press|page=80-83}}.</ref>{{,}}<ref>{{Ouvrage|langue=en|prénom1=D. H.|nom1=Fowler|lien auteur1=David Fowler|titre=The Mathematics of Plato's Academy|sous-titre=A New Reconstruction|lieu=Oxford|éditeur=Oxford University Press|année=1987|page=31-66|isbn=978-0-19-853912-4|isbn10=0-19-853912-6|bnf=34952462}}.</ref>, vu les termes techniques ἀνθυφαίρεσις (''anthyphairesis'', soustraction réciproque) dans les travaux d'Euclide et aussi d'[[Aristote]]<ref>{{article|lang=de|auteur=[[Oskar Becker]]|année=1933|titre=Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid|volume=2|page=311-333|journal=Quellen und Studien zur Geschichte der Mathematik B}}.</ref>.

Quelques siècles plus tard, l'algorithme d'Euclide est inventé de manière indépendante à la fois en [[Inde]] et en [[Chine]]<ref>{{Ouvrage|langue=Anglais|auteur=[[John Stillwell]]|titre=Numbers and Geometry|éditeur=Springer|isbn=0-387-98289-2|url={{Google Livres|4elkHwVS0eUC|page=31}}|page=31}}.</ref>. L'objectif était de résoudre des [[Équation diophantienne|équations diophantiennes]] issues de l'[[astronomie]] et de faire des calendriers plus précis. Au {{s-|V}}, le mathématicien et astronome indien [[Aryabhata]] a décrit cet algorithme comme le « pulvérisateur »<ref>{{Ouvrage|langue=Anglais|auteur=J. J. Tattersall|titre=Elementary Number Theory in Nine Chapters|date=2005|éditeur=[[Cambridge University Press]]|isbn=978-0-521-85014-8|url={{Google Livres|QGgLbf2oFUYC|page=64}}|page=64}}.</ref>, à cause de son efficacité pour résoudre les équations diophantiennes<ref>{{Ouvrage|langue=Anglais|auteur1=K. H. Rosen|titre=Elementary Number Theory and its Applications|numéro d'édition=4|passage=86-87|date=2000}}.</ref>.

== Présentation ==
Le PGCD (plus grand commun diviseur) de deux [[Entier relatif|entiers relatifs]] est égal au PGCD de leurs valeurs absolues. De ce fait, on se restreint dans cette section aux [[Entier naturel|entiers positifs]]. 

=== Algorithme original (par différences successives) ===
L'algorithme part du constat suivant : le PGCD de deux nombres n'est pas changé si on remplace le plus grand d'entre eux par leur différence. Autrement dit, {{math|§=pgcd(''a'', ''b'') = pgcd(''a''−''b'', ''b'')}}. Par exemple, le PGCD de 21 et 15 est aussi égal au PGCD de 21 - 15 = 6 et 15. Puis, le PGCD de 6 et 15 est égal au PGCD de 15 - 6 = 9 et 6. Le tableau suivant contient les valeurs successives des deux nombres afin de calculer le PGCD de 21 et 15 :
{| class="wikitable"
|+
!Etapes
!Premier nombre
!Deuxième nombre
|-
|1ère étape
|21
|15
|-
|2e étape
|21 – 15 = 6
|15
|-
|3e étape
|6
|15 – 6 = 9
|-
|4e étape
|6
|9 – 6 = 3
|-
|5e étape
|6 – 3 = 3
|3
|}
On s'arrête lorsque les deux nombres sont égaux : dans l'exemple, on est arrivé à 3. Ce nombre est le PGCD des deux nombres à chaque ligne, en particulier des deux nombres initiaux (sur l'exemple 21 et 15). Ce processus se termine toujours car le remplacement de ces nombres diminue strictement le plus grand d'entre eux.

=== Algorithme standard (par division euclidienne) ===
On peut utiliser un raccourci en remplaçant des soustractions successives par une division euclidienne. Par exemple, on peut remplacer les soustractions successives :
* 15 – 6 = 9
* 9 – 6 = 3

par la division euclidienne de 15 par 6 qui donne 15 = 6 × 2 + 3. L'algorithme d'Euclide opère en utilisant ce raccourci : on remplace le plus grand des deux nombres par le reste de la [[division euclidienne]] du plus grand nombre par le plus petit. Ici, on remplace 15 par le reste 3. Dans [[Introduction à l'algorithmique]] de Cormen et al. (voir Th. 31.9<ref name=":0">{{Ouvrage|auteur1=Thomas H. Cormen|auteur2=Charles E. Leiserson|auteur3=Ronald L. Rivest |auteur4=Clifford Stein |année=2004|titre=[[Introduction à l'algorithmique]]|passage=Section 31.2|éditeur=Dunod|numéro édition=2|pages totales=1176|lire en ligne=|isbn=2 10 003922 9}}</ref>), les auteurs appellent ''théorème de la [[récursivité]] pour le PGCD'' le fait suivant :

:{{math|§=pgcd(''a'', ''b'') = pgcd(''b'', ''r'')}} où {{math|''r''}} est le reste de la division euclidienne de {{math|''a''}} par {{math|''b''}}.

Une description précise de l'algorithme d'Euclide sur deux nombres entiers positifs {{math|''a''}} et {{math|''b''}} avec {{math|''a'' > ''b'' ⩾ 0}} est donc :

* si {{math|§=''b'' = 0}}, l'algorithme se termine et rend la valeur {{math|''a''}} ;
* sinon, l'algorithme calcule le reste {{math|''r''}} de la division euclidienne de {{math|''a''}} par {{math|''b''}}, puis recommence avec {{math|§=''a'' := ''b''}} et {{math|§=''b'' := ''r''}}.

Formellement l'algorithme d'Euclide construit une suite finie d'entiers {{math|(''r<sub>n</sub>'')}} par récurrence double : 

* {{math|§=''r''<sub>0</sub> = ''a''}},  {{math|§=''r''<sub>1</sub> = ''b''}} ;
* pour {{math|''n'' ⩾ 1}}, {{math|''r''<sub>''n''+1</sub>}} est le reste de la division euclidienne de {{math|''r''<sub>''n''-1</sub>}}  par {{math|''r<sub>n</sub>''}}, en particulier {{math|''r<sub>n+1</sub>'' < ''r<sub>n</sub>''}}.

La suite {{math|(''r<sub>n</sub>'')}} est une suite strictement décroissante d'entiers positifs à partir du rang 1 : elle est donc finie et s'arrête au premier {{math|''n''}} tel que {{math|§=''r<sub>n</sub>'' = 0}}.

==== Exemple ====
Le tableau suivant montre le calcul du PGCD de 21 et 15. On réalise la division euclidienne de {{math|§=''a'' = 21}} et {{math|§=''b'' = 15}} : le quotient est 1 et le reste 6. L'algorithme continue avec {{math|§=''a'' := ''b''}} et {{math|§=''b'' := }} le précédent reste, jusqu'à trouver un reste nul. L'algorithme s'arrête alors et retourne le dernier reste non nul trouvé, ici <math>r_3 = 3</math> qui est bien le PGCD de 21 et 15 :
{| class="wikitable" id="basic_Euclidean_algorithm"
!Étape {{math|''n''}}
!Dividende <math>r_{n-1}</math>
!Diviseur <math>r_n</math>
!Équation <math>r_{n-1} = r_nq_n + r_{n+1}</math>
!Quotient <math>q_n</math>
!Reste <math>r_{n+1}</math>
|-
|1
|21
|15
|21 = 15 × 1 + 6
|1
|6
|-
|2
|15
|6
|15 = 6 × 2 + 3
|2
|3
|-
|3
|6
|3
|6 = 3 × 2 + 0
|2
|0
|-
|4
|3
|0
|fin de l'algorithme
|
|
|}

=== Explications géométriques ===
Dans la tradition [[Grèce antique|grecque]], en comprenant un nombre entier comme une longueur et un couple d'entiers comme un rectangle, leur PGCD est la longueur du côté du plus grand carré permettant de carreler entièrement ce rectangle. L'algorithme décompose ce rectangle en carrés, de plus en plus petits, par divisions euclidiennes successives, de la longueur par la largeur, puis de la largeur par le reste, jusqu'à un reste nul.

Considérons par exemple le rectangle de dimensions L = 21 par l = 15 représenté ci-dessous. On peut glisser un carré de côté 15 mais il reste un rectangle de côtés 15 et 6. On peut y glisser deux carrés de côté 6 mais il reste un rectangle de côtés 6 et 3 que l'on peut carreler entièrement de carrés de côté 3. Les carrés de côté 6 ou 15 peuvent aussi se carreler en carrés de côté 3. Le rectangle entier peut se carreler en carrés de côté 3. Il n'existe pas de carré plus grand permettant un tel carrelage. 
[[Fichier:Euclide1521.svg|centré|vignette|782x782px|Explication géométrique de l'algorithme d'Euclide sur les entiers 21 et 15.]]

== Implémentation ==
=== Version itérative ===
[[Image:algo_Euclide.png|thumb|upright=2|Algorithme d'Euclide sous la forme d'un [[Organigramme de programmation|organigramme]]. On pose la question "est-ce que b = 0 ?". Si oui, le pgcd est égal à a. Sinon, on part dans la boucle "Non". On revient à la question avec les nouvelles valeurs de a et b.]][[Donald Knuth]], dans ''{{Lang|en|[[The Art of Computer Programming]]}}'', écrit une version itérative de l'algorithme d'Euclide<ref name=":1">{{Ouvrage|langue=en|prénom1=Donald E.|nom1=Knuth|titre=[[The Art of Computer Programming]]|vol=2|numéro d'édition=3|sous-titre=Seminumerical Algorithms|éditeur=Addison-Wesley Longman|année=1997|pages totales=762|isbn=978-0-201-89684-8}}.</ref> :
{{Pseudo code
|titre=Algorithme d’Euclide itératif
|entree=Deux entiers a et b
|sortie=Le PGCD de a et b
|code=
fonction euclide(a, b)
    tant que b ≠ 0
        t := b; 
        b := a modulo b; 
        a := t; 
    retourner a;
}}
où l'on note <code>a modulo b</code> le reste de la division euclidienne de a et b.

La version originale de l'algorithme d'Euclide, où l'on n’effectue que des différences successives, est<ref name=":1" /> :
{{Pseudo code
|titre=Algorithme d’Euclide original|entree=Deux entiers a et b|sortie=Le PGCD de a et b
|code=
fonction euclide(a, b)
    tant que a ≠ b 
        si a > b alors
            a := a − b;
        sinon
            b := b − a;
    retourner a;
}}

=== Version récursive ===
Cormen et al., dans [[Introduction à l'algorithmique]] en donne une version [[algorithme récursif|récursive]]<ref name=":0" /> ; Dasgupta et al.<ref name=":2">{{Ouvrage|langue=en|auteur1=Sanjoy Dasgupta|auteur2=Christos Papadimitriou|auteur3=Umesh Vazirani|titre=Algorithms|éditeur=McGraw-Hill|année=2008|isbn=}}</ref> en donne la même version :
{{Pseudo code
|titre=Algorithme d’Euclide récursif
|entree=Deux entiers a et b
|sortie=Le PGCD de a et b
|code=
fonction euclide(a, b)
    si b = 0 alors retourner a;
    sinon retourner euclide(b, a modulo b);
}}
L'appel à <code>euclide(a, b)</code> s'arrête et retourne la valeur a si b = 0. Sinon, l'appel continue avec les nombres b et a modulo b. L'exécution du calcul de PGCD de 21 et 15 donne : {{nobr|euclide(21, 15) {{=}} euclide(15, 6) {{=}} euclide(6, 3) {{=}} euclide(3, 0) {{=}} 3}}.

=== Correction et terminaison ===
{{Voir|Plus grand commun diviseur de nombres entiers#Propriétés{{!}}Propriétés du PGCD}}On sait que {{math|1=PGCD(''a'', 0) = ''a''}} et que {{math|1=PGCD(''a'', ''b'') = PGCD(''b'', ''a'' mod ''b'')}}. On progresse dans l'algorithme en diminuant à chaque étape les nombres considérés par calcul du modulo. L'algorithme termine bien : pour une valeur non nulle de ''b'', le calcul de PGCD(''a'', ''b'') fait appel au calcul de PGCD(''a''’, ''b''’), où 0 ≤ ''b''’ < |''b''|, car ''b''’ est le reste d'une division euclidienne par ''b''.

== Complexité ==
[[Fichier:Algorithme euclide nb etapes.png|vignette|Nombre d'étapes de l'algorithme d'Euclide en fonction des nombres entiers a et b (respectivement en abscisse et en ordonnées). Plus le point de coordonnées (a, b) est foncé, plus le calcul de PGCD(a, b) nécessite d'étapes. Les points (a, b) avec a > b les plus foncés sont concentrés autour de la droite a = bφ, où φ est le nombre d'or.]]
Dans cette section, nous étudions la [[Analyse de la complexité des algorithmes|complexité  temporelle]] de l'algorithme d'Euclide, c'est-à-dire le nombre d'étapes de calcul en fonction des entiers a et b. La première analyse de complexité connue est due à A. L. Reynaud en 1811 : il écrit que le nombre d'étapes de l'algorithme d'Euclide sur a et b est borné par b<ref>{{chapitre | auteurs ouvrage = Bezout et Reynaud | auteur1 = A. A. L. Reynaud | titre ouvrage = Cours de mathématiques à l'usage de la marine et de l'artillerie | titre chapitre = Notes explicatives| passage = Théorie du plus grand commun diviseur | lire en ligne = https://gallica.bnf.fr/ark:/12148/bpt6k9771911n/f451}}, {{gallica}}.</ref>{{,}}<ref>{{ouvrage|nom=Reynaud|prénom=A.-A.-L.|année=1811|titre=Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique|edition=6th|éditeur=Courcier|lieu=Paris|passage=Note 60, p.&nbsp;34}} As cited by {{harvtxt|Shallit|1994}}.</ref>. En 1841, P.-J.-E. Finck  démontre que le nombre d'étapes est borné par 2&nbsp;log<sub>2</sub>&nbsp;''b''&nbsp;+&nbsp;1<ref>{{ouvrage|nom=Finck|prénom=P.-J.-E.|titre=Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales|langue=fr|éditeur=Derivaux|année=1841}}</ref>. Cela démontre que l'algorithme d'Euclide s'exécute en temps polynomial en la taille de l'entrée (nombre de chiffres pour écrire les nombres a et b)<ref name="Shallit">{{article|lien auteur=Jeffrey Shallit|nom=Shallit|prénom=J.|année=1994|titre=Origins of the analysis of the Euclidean algorithm|journal=Historia Math.|volume=21|pages=401–419|doi=10.1006/hmat.1994.1031}}</ref>. En 1844, [[Gabriel Lamé]] raffine les résultats de Finck : il démontre que l'algorithme effectue au plus 5 fois le nombre de chiffres en base 10 du plus petit nombre<ref>{{article|lien auteur=Gabriel Lamé|nom=Lamé|prénom=G.|année=1844|titre=Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers|langue=fr|journal=Comptes Rendus Acad. Sci.|volume=19|pages=867–870}}</ref>.

=== Première analyse ===
Nous donnons d'abord une analyse qui part du constat suivant<ref name=":2" /> :
:Si a ≥ b, alors a mod b < a / 2
Ainsi, si a et b sont codés sur n bits, au bout de deux appels récursifs, leurs tailles contient un bit de moins. Il y a donc O(n) appels récursifs. Comme la division euclidienne s'exécute en O(n<sup>2</sup>) opérations, l'algorithme d'Euclide est en O(n<sup>3</sup>)<ref name=":2" />.

=== Analyse via le théorème de Lamé ===
La précédente analyse permet de montrer rapidement que l'algorithme d'Euclide est en O(log<sub>2</sub>(''b'')) divisions. 
Une analyse plus fine<ref>Détaillée par exemple dans {{harvsp|Cormen|Leiserson|Rivest|Stein|2004|page=830-831}}.</ref>, due pour l'essentiel à [[Gabriel Lamé|Lamé]], permet une meilleure évaluation (c'est la constante pour cette évaluation en O(log<sub>2</sub>(''b'')) qui peut être améliorée). Elle utilise la [[suite de Fibonacci]] définie par 
: F<sub>0</sub> = 0, F<sub>1</sub> = 1, F<sub>k+2</sub> = F<sub>k+1</sub> + F<sub>k</sub>, pour tout k ≥ 0, 
et dont les premiers termes sont :
{| class="wikitable" style="text-align:center;"
|<math> F_0</math>
|<math> F_1</math>
|<math> F_2</math>
|<math> F_3</math>
|<math>F_4</math>
|<math>F_5</math>
|<math> F_6</math>
|<math> F_7</math>
|<math> F_8</math>
|<math> F_9</math>
|<math> F_{10}</math>
|<math> F_{11}</math>
|<math> F_{12}</math>
|<math> F_{13}</math>
|<math> F_{14}</math>
|<math> F_{15}</math>
|<math> F_{16}</math>
|...
|-
|0
|1
|1
|2
|3
|5
|8
|13
|21
|34
|55
|89
|144
|233
|377
|610
|987
|...
|}.
Quand l'algorithme d'Euclide est appelé sur deux nombres de Fibonacci consécutifs F<sub>k+2</sub> et F<sub>k+1</sub>
, il utilise ''k'' appels récursifs :
:euclide( F<sub>k+2</sub> ,  F<sub>k+1</sub> ) = euclide( F<sub>k+1</sub> ,  F<sub>k</sub> ) = ... euclide(F<sub>2</sub>, F<sub>1</sub>) = euclide(F<sub>1</sub>, F<sub>0</sub>)
et comme pour chaque division euclidienne invoquée par l'algorithme le quotient est 1, cette situation est la pire du point de vue de la complexité, plus précisément on a le théorème de [[Gabriel Lamé|Lamé]]<ref>{{harvsp|Cormen|Leiserson|Rivest|Stein|2004}}, Th. 31.11</ref> :

{{Théorème|énoncé=Pour tout entier k ≥ 1, si a > b ≥ 1, et b < F<sub>k+1</sub>, alors l'algorithme d'Euclide sur a et b réalise moins de k appels récursifs.|nom=Théorème de Lamé}}

{{boîte déroulante/début|titre=Démonstration}}
On suppose sans perte de généralité que a > b (si a < b, l'algorithme échange a et b, si a = b, alors l'algorithme s'arrête en une étape). On démontre par récurrence sur k que si on effectue plus de k appels récursifs alors a ≥ F<sub>k+2</sub> et b ≥ F<sub>k+1</sub><ref>{{harvsp|Cormen|Leiserson|Rivest|Stein|2004}}, lemme 31.10.</ref>.

* Pour k = 1, si on effectue au moins un appel récursif, cela signifie que a > b ≥ 1 et donc a ≥ F<sub>2</sub> et b ≥ F<sub>1</sub>. 
* Supposons que la propriété est vraie pour k-1 et considérons a et b pour lesquelles l'algorithme effectue plus de k appels. L'algorithme effectue k-1 appels pour b et a mod b. Par hypothèse de récurrence, cela signifie que b ≥ F<sub>k+1</sub> et que a mod b ≥ F<sub>k</sub>. Mais a ≥ b + (a mod b) ≥ F<sub>k+1</sub> + F<sub>k</sub> = F<sub>k+2</sub>.
{{boîte déroulante/fin}}
Cette majoration est la meilleure possible, puisqu'elle est atteinte quand <math>a</math> et <math>b</math> sont deux [[nombre de Fibonacci|nombres de Fibonacci]] consécutifs. 

Via la formule de Binet, F<sub>k</sub> est [[Équivalent#L'%C3%A9quivalence pour les suites|équivalent]] à <math>\varphi^k / \sqrt{5}</math> où <math>\varphi</math> est le [[nombre d'or]]. Ainsi, on en déduit à nouveau que le nombre d'appels récursifs est <math>O(\log(b))</math>. Plus précisément, il y a au plus <math>1+\log_\varphi(b)</math> appels récursifs, où <math>\log_\varphi</math>désigne le [[logarithme]] en base <math>\varphi</math>. On peut même montrer qu'il y a <math>1+\log_\varphi(b / pgcd(a, b))</math><ref>{{harvsp|Cormen|Leiserson|Rivest|Stein|2004}}, exercice 31.2.5.</ref>.

=== Complexité quadratique ===
Soit n le nombre de bits dans les nombres d'entrées. Comme l'algorithme effectue une division euclidienne à chaque appel récursif, qui coûte O(n<sup>2</sup>), et qu'il  y a O(n) appels récursifs, l'algorithme est en O(n<sup>3</sup>)<ref name=":2" />. Toutefois, une analyse fine montre que l'algorithme s'exécute en temps quadratique en le nombre de bits des nombres d'entrées (voir Problème 31.2 laissé en exercice dans <ref name=":0" />, p. 902).

== Généralisation ==

=== Algorithme étendu aux coefficients de Bézout ===

{{Article détaillé|Algorithme d'Euclide étendu}}

Le [[théorème de Bachet-Bézout]] assure l'existence de deux entiers <math>u</math> et <math>v</math> tels que : <math>au+bv=PGCD(a,b)</math>. L'algorithme d'Euclide étendu calcule de tels coefficients.

Pour cela, on introduit deux suites <math>(u_n)</math> et <math>(v_n)</math> telles que pour tout <math>n</math>, on ait la relation : <math>au_n+bv_n=a_n</math> où <math>a_n</math>est la valeur de <math>a</math> à la ''n''-ième étape de l'algorithme. Les termes <math>u_N,v_N</math> constitueront une paire de coefficients de Bézout pour <math>a</math> et <math>b</math>, où <math>N</math> est le numéro de la dernière étape de l'algorithme.

On choisit <math>u_0=1, v_0=0</math> et <math>u_1=0,v_1=1</math> (afin que <math>au_n+bv_n=a_n</math> soit vrai pour <math>n=0</math> et pour <math>n=1</math>), puis la [[Suite définie par récurrence|relation de récurrence]] de pas 2 entre les <math>a_n</math> montre :

<math> a_{n+2}=a_n-q_{n+2}a_{n+1}
=au_n+bv_n-q_{n+2}(au_{n+1}+bv_{n+1})
=a(u_n-q_{n+2}u_{n+1})+b(v_n-q_{n+2}v_{n+1})
</math>

On peut ainsi définir <math>(u_n)</math> par la relation de récurrence de pas 2 : <math>u_{n+2}=u_n-q_{n+2}u_{n+1}</math> et l'initialisation précédente, et <math>(v_n)</math> par <math>v_{n+2}=v_n-q_{n+2}v_{n+1}</math> et l'initialisation précédente ; et on obtient bien la relation annoncée pour tout <math>n</math>.

L'algorithme étendu s'implémente comme l'algorithme classique ; il suffit de rajouter des variables correspondant aux coefficients ''u'' et ''v'' à calculer, et de faire une multiplication et une soustraction supplémentaires, pour calculer chacun des deux nouveaux coefficients, à chaque étape.

=== Anneau euclidien ===
Cet algorithme repose sur la structure d’[[anneau euclidien]] de l’[[anneau unitaire|anneau]] '''Z''' des entiers relatifs, plus particulièrement sur la propriété de [[division euclidienne]]. Il se généralise donc à d’autres anneaux, en particulier les anneaux de [[polynôme]]s à coefficients dans un corps. L’algorithme se généralise pour permettre le calcul des [[Équation diophantienne ax + by = c|coefficients de Bézout]].

L’algorithme est effectif à condition de disposer d’un algorithme effectif de [[division euclidienne]]. La possibilité de disposer d’un tel algorithme rend de nombreux autres calculs effectifs, notamment, en [[algèbre linéaire]], le calcul de [[Théorème des facteurs invariants|facteurs invariants]].

=== Fractions continues ===
{{Article détaillé|fraction continue}}
Les quotients successifs qui apparaissent quand l'algorithme d'Euclide est appliqué aux données ''a'' et ''b'', sont précisément les nombres qui apparaissent dans la représentation sous forme de [[fraction continue]] de ''a''/''b''. Considérons l'exemple de ''a'' = {{formatnum:1071}} et ''b'' = {{formatnum:1029}} utilisé ci-dessus.

Voici le calcul avec les quotients soulignés (successivement '''1''', '''24''' et '''2''') : 
:{{formatnum:1071}} = {{formatnum:1029}} × '''1''' + 42
:{{formatnum:1029}} = 42 × '''24''' + 21
:42 = 21 × '''2''' + 0
De cela on tire :
:<math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}}</math>.
Dans l'égalité précédente, le second membre s'appelle la fraction continue ou continuée du quotient {{formatnum:1071}}/{{formatnum:1029}}.

On peut en déduire les trois approximations suivantes de la fraction, classées par ordre de précision croissante :
* <math>\frac{1071}{1029} \simeq \mathbf{1} = \frac{1}{1}</math> ;
* <math>\frac{1071}{1029} \simeq \mathbf{1} + \frac{1}{\mathbf{24}} = \frac{25}{24}</math> ;
* <math>\frac{1071}{1029} = \mathbf{1} + \frac{1}{\mathbf{24} + \frac{1}{\mathbf{2}}} = \frac{51}{49}</math>.
 
Cette méthode peut également être utilisée pour des [[nombre réel|nombres réels]] ''a'' et '' b'' ; comme dans le cas de deux entiers, la suite de quotients calculés représente la « ''décomposition en fraction continue'' » de ''a''/''b'' et fournit une suite d'approximations successives, de qualité croissante, du quotient ''a''/''b''.
Dans le cas où ce quotient est [[nombre irrationnel|irrationnel]], l'algorithme d'Euclide ne termine pas et la suite des approximations obtenues est infinie{{Référence nécessaire|date=29 septembre 2019}}.

'''Nota''' : 
La décomposition en fraction continue (et la série d'approximations successives correspondante) peut être appliquée, non seulement à un nombre réel quelconque, mais également à une fonction : cette démarche consiste à rechercher les [[approximant de Padé|approximants de Padé]], dont on peut définir le principe comme suit : ''Au voisinage d'un point, le développement en [[série de Taylor]] d'une fonction donnée fournit un polynôme qui réalise une approximation de la fonction. Mais on peut également chercher une fraction rationnelle qui satisfasse les mêmes conditions que la partie polynomiale du développement de Taylor : l'égalité des dérivées de la fonction et de son approximation, jusqu'à un certain ordre donné{{Référence nécessaire|date=29 septembre 2019}}.''

La comparaison de ces deux types de développements permet de très intéressants développements, comme la démonstration de l'[[Théorème d'Apéry|irrationalité de ζ(3)]]{{Référence nécessaire|date=29 septembre 2019}}

== Notes et références ==
{{Traduction/Référence|en|Euclidean_algorithm|921161285|type=n}}
{{Références}}

== Voir aussi ==
=== Articles connexes ===
*[[Liste de sujets portant le nom d'Euclide]]
*[[Algorithme binaire de calcul du PGCD]]
*[[Constante de Porter]], intervenant dans l'évaluation du nombre moyen d'étapes dans l'algorithme d'Euclide
* [[Anneau euclidien]]

=== Lien externe ===
{{YouTube|Q89mh5gYFIY|« Calcul du PGCD avec l'algorithme d'Euclide »|fr}}, téléversé le {{date-|12 mai 2014}}

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

[[Catégorie:Théorie algorithmique des nombres|Euclide, Algorithme d']]
[[Catégorie:Algorithme numérique|Euclide, Algorithme d']]
[[Catégorie:Euclide]]