Mostra la font per a Algorisme d'Euclides

L{{'}}'''[[algorisme]] d'[[Euclides]]'''{{Ref_label|a|a|none}} és un mètode eficaç per a calcular el [[màxim comú divisor]] ('''mcd''') entre dos [[nombre enter|nombres enters]]. Rep el nom del [[matemàtic]] [[grec]] [[Euclides]] el qual el va descriure en els volums VII i X del llibre ''[[Elements d'Euclides|Elements]]''.<ref>[[Thomas Little Heath|{{Versaleta|Heath}}, Thomas Little]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref>

L'algorisme consisteix en diverses [[divisió|divisions]] enteres successives. En la primera divisió, es pren com a dividend el major dels nombres i com a divisor l'altre. Després, el divisor i el residu serveixen respectivament de dividend i divisor de la següent divisió. El procés es para quan s'obté un residu nul. El '''mcd''' és llavors el penúltim residu de l'algorisme.<ref>{{ref-llibre|cognom=Corbalán Yuste |nom=F. et al. |títol=Gamma 2 : matemàtiques : Educació Secundària, segon curs |pàgines=11 |lloc=Barcelona |editorial=Vicens Vives |any=2003 |isbn=84-316-6978-2 |edició=1a.}}</ref> <br/>
Formalment, si anomenem ''a'', ''b'' els enters inicials, r<sub>1</sub>, r<sub>n</sub> ... r<sub>n-1</sub> i r<sub>n</sub> = 0 els residus successius, llavors:

<center>'''mcd''' (a, b) = '''mcd''' (b, r<sub>1</sub>), amb ''r<sub>1</sub> = a - b·q'' (''q'' és el quocient de ''a'' per ''b'')</center>

Després el menor dels divisors comuns és el mateix, i repetint l'operació:

<center>'''mcd''' (b, r<sub>1</sub>) = '''mcd''' (r<sub>1</sub>, r₂) = '''mcd''' (r₂, r₃) = ... = '''mcd''' (r<sub>n-1</sub>, r<sub>n</sub>) = '''mcd''' (r<sub>n-1</sub>, 0) = r<sub>n-1</sub>.</center>

Això permet detallar l'algorisme efectiu:

{| align=center width70% border=1
| bgcolor=#FFFF99 |
* dades d'entrada '''a''' i '''b''' &nbsp;- si cal, canvieu-los a positius
* l'algorisme:
:mentre b ≠ 0 repetiu les tres instruccions següents:
:: r ← residu de a entre b &nbsp;&nbsp; (doneu a '''r''' el valor del residu de a entre b)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
:: a ← b &nbsp;&nbsp; (el nou valor de '''a''' és l'antic valor de '''b''')
:: b ← r &nbsp;&nbsp; (el nou valor de '''b''' és el valor de '''r''')
* el resultat és '''a''' (el seu últim valor).
|}

Aquest algorisme dona com a resultat 0 si a i b són nuls, mentre que en matemàtiques el major divisor de zero no existeix.

== Fonaments ==
=== Màxim comú divisor ===
L'algorisme d'Euclides calcula el [[MCD|màxim comú divisor (MCD)]] de dos [[nombre natural|nombres naturals]] ''a'' i ''b''. El màxim comú divisor ''g'' és el nombre natural més gran que divideixi els dos ''a'' i ''b'' és a dir, que al dividir tant ''a'' com ''b'' entre ''g'' el residu és zero. El màxim comú divisor s'escriu sovint com MCD(''a'', ''b'') o, més simplement, com (''a'', '' b''),<ref>Stark, pàg. 16.</ref> encara que l'última notació també es fa servir per a altres conceptes matemàtics, com [[vector (matemàtiques) |vectors]] bidimensionals.

Si MCD(''a'', '' b'') = 1, llavors ''a'' i ''b'' s'anomenen [[nombres coprimers|coprimers]].<ref>Stark, pàg. 21.</ref> Aquesta propietat és independent de si ''a'' i ''b'' són ells mateixos [[nombre primer|nombres primers]].<ref>LeVeque, pàg. 32.</ref> Per exemple, ni 6 ni 35 són nombres primers, ja que els dos tenen dos factors primers: 6 = 2 × 3 i 35 = 5 × 7. No obstant això, 6 i 35 són coprimers. Cap nombre natural diferent d'1 no és divisor al mateix temps de 6 i de 35, ja que no tenen cap factor primer en comú.

[[Fitxer:Square tiling 24x60.svg|miniatura|alt="Rectangle dividit en un reixat de quadrats. El rectangle és de dos quadrats d'ample i cinc quadrats d'alt."|Un rectangle de 24-per-60 es cobreix amb deu rajoles quadrades de 12-per-12, on 12 és el MCD de 24 i 60. De manera més general, un rectangle de ''a''-per-''b'' pot ser cobert amb rajoles quadrades de llargada de costat ''c'' només si ''c'' és un divisor comú de ''a'' i ''b''.]]

Sia ''g'' = MCD(''a'', '' b''). Com que ''a'' i ''b'' són tots dos múltiples de ''g'', es poden escriure com ''a'' = ''mg'' i ''b'' = ''ng'', i no hi ha cap nombre més gran ''G'' > ''g'' per al qual això es compleixi. Els nombres naturals ''m'' i ''n'' han de ser coprimers, ja que qualsevol factor comú es podria treure de ''m'' i ''n'' i fer ''g'' més gran. Així, qualsevol altre nombre ''c'' que divideix els dos ''a'' i ''b'' també ha de dividir ''g''. El màxim comú divisor ''g'' de ''a'' i ''b'' es pot definir com el comú divisor que és divisible per qualsevol altre comú divisor ''c''.<ref>Leveque, pàg. 31.</ref>

El MCD es pot visualitzar de la manera següent.<ref>{{ref-llibre|autor = Grossman JW |any = 1990 |títol = Discrete Mathematics |editorial = Macmillan |lloc = Nova York|isbn = 0-02-348331-8 |pàgines = 213}}</ref> Es considera una àrea rectangular ''a'' per ''b'', i qualsevol divisor comú ''c'' que divideix tant ''a'' com ''b'' exactament. Els costats del [[rectangle]] es poden dividir en segments de llargada ''c'', que divideix el rectangle en un reixat de [[Quadrat (polígon)|quadrats]] de llargada de costat ''c''. El màxim comú divisor ''g'' és el valor més gran de ''c'' per al qual això és possible. Per a la il·lustració, una àrea rectangular de 24-per-60 pot ser dividida a un reixat de: quadrats d'1-per-1, quadrats de 2-per-2, quadrats de 3-per-3, quadrats de 6-per-6 o quadrats de 12-per-12. Per això, 12 és el màxim comú divisor de 24 i 60. Una àrea rectangular de 24-per-60 pot ser dividida en un reixat de quadrats de 12-per-12, amb dos quadrats al llarg d'una aresta (24/12 = 2) i cinc quadrats al llarg de l'altre (60/12 = 5).

El MCD de dos nombres ''a'' i ''b'' pot ser definit com el producte dels factors primers compartits pels dos nombres.<ref name="Schroeder_21" >Schroeder, pàg. 21-22.</ref> Per exemple, com que 462 es pot [[descomposició en factors primers|descompondre en factors]] com 2 × 3 × 7 × 11 i 1071 es pot descompondre com 3 × 3 × 7 × 17, el màxim comú divisor de 462 i 1071 és igual a 21 = 3 × 7, el producte dels seus factors primers compartits. Si dos nombres no tenen cap factor primer en comú, el seu màxim comú divisor és 1, llavors són coprimers. Un avantatge clau de l'algorisme d'Euclides és que pot trobar el MCD eficaçment sense haver de calcular els factors primers.<ref>Schroeder, pàg. 19.</ref><ref>. {{ref-llibre|autor = Ogilvy CS, Anderson JT |any = 1966 |títol = Excursions in number theory |editorial = [[Oxford University Press]] |lloc = Nova York|id = LCCN 66-0-14484 |pàgines = p. 27–29}}</ref> La [[factorització dels enters|factorització]] d'enters grans es creu que és un problema tan difícil que s'hi basen molts sistemes de criptografia moderns.<ref name="Schroeder_216" >Schroeder, pàg. 216-219.</ref>

Una definició més subtil del MCD és útil en matemàtiques avançades, especialment en [[teoria d'anells]].<ref name="Leveque_p33"/> El màxim comú divisor ''g'' de dos nombres ''a'' i ''b'' és també el seu múltiple enter més petit, és a dir, el nombre més petit de la forma ''ua'' + ''vb'' on ''u'' i ''v'' són enters (cal tenir en compte que un sempre és negatiu i l'altre positiu). Se segueix que el [[conjunt]] de tots els múltiples enters de ''a'' i ''b'' (tots els nombres ''ua'' + ''vb'') és el mateix com el conjunt de tots els múltiples enters de ''g'' (''mg'', on ''m'' és un enter). En llenguatge matemàtic modern, l'[[ideal (matemàtiques)|ideal]] format per ''a'' i ''b'' és un [[ideal principal]] generat per ''g''. L'equivalència d'aquesta definició de MCD amb les altres definicions es descriu més avall.

El MCD de tres o més nombres és igual al producte dels factors primers comuns a tots els nombres,<ref>Stark, pàg. 25.</ref> que es pot calcular prenent el MCD de cada parella de nombres.<ref>Oregon, pàg. 47-48.</ref> Per exemple

: <math>MCD(a,b,c)=MCD(a,MCD(b,c))=MCD(MCD(a,b),c)=MCD(MCD(a,c),b).</math>

Per tant, l'algorisme d'Euclides, que calcula el MCD de dos enters, és suficient per calcular el MCD d'una quantitat arbitrària d'enters.

=== Inducció, recursivitat i descens infinit ===
Tres mètodes matemàtics relacionats s'utilitzen en els arguments següents: [[demostració per inducció|inducció]], [[recursivitat]] i [[mètode del descens infinit|descent infinit]]. La inducció<ref>{{Ref-llibre|nom = Donald E.|cognom = Knuth|enllaçautor = Donald Knuth|any = 1997|títol = The Art of Computer Programming, Volume 1: Fundamental Algorithms|edició =3a ed.|editorial = Addison-Wesley|isbn = 0-201-89683-4}} (Secció 1.2.1: Inducció matemàtica, pàg. 11-21.)</ref> sovint es fa servir per demostrar un teorema per a tots els [[nombre natural|nombres naturals]] ''n''.<ref>Rosen, pàg. 18-21.</ref> Aquest enfocament comença demostrant que, si el teorema es compleix per ''n'', també es compleix per ''n'' + 1. Per això, si el teorema es compleix per a un cas (típicament ''n'' = 1), es compleix per a tots els casos més alts (''n'' = 2, 3, etc.). Una recurrència<ref>Rosen, pàg. 21-24.</ref> és una [[equació]] que relaciona nombres que formen una [[sèrie matemàtica|sèrie]] ''a''<sub>1</sub>, ''a''₂, ''a''₃, etc.<ref>{{ref-llibre|autor = Anderson JA |any = 2001 |títol = Discrete Mathematics with Combinatorics |editorial = Prentice Hall |lloc = de localitzacions, Nj|isbn = 0-13-086998-8 |pàgines = 165–223}}</ref> El terme ''n''-èsim de la sèrie, ''a''<sub>''n''</sub>, sovint s'expressa en funció de termes anteriors de la sèrie, com ''a''<sub>''n'' −1</sub>. Per exemple, els [[Successió de Fibonacci|nombres de Fibonacci]] es defineixen recursivament; cada terme és la suma dels dos termes anteriors: ''F''<sub>''n''</sub> = ''F''<sub>''n'' −1</sub> + ''F''<sub>''n'' −2</sub>. Unes quantes equacions associades amb l'algorisme euclidià són recursives. Finalment, en el descens infinit,<ref>Rosen, pàg. 492.</ref> una solució donada en nombres naturals és utilitzada per construir una solució amb nombres naturals més petits.<ref>{{ref-llibre|autor = Anderson JA |any = 2001 |títol = Discrete Mathematics with Combinatorics |editorial = Prentice Hall |lloc = de localitzacions, Nj|isbn = 0-13-086998-8 |pàgines = 109–119}}</ref> Tanmateix, les solucions no es poden encongir indefinidament, ja que només hi ha un nombre finit de nombres naturals més petits que qualsevol nombre natural. Per això, la solució original era impossible, o la construcció de solucions més petites ha d'acabar. L'últim argument s'utilitza per demostrar que l'algorisme euclidià per a nombres naturals ha d'acabar en un nombre finit de passos.<ref name="Stark_p18"/>

== Descripció ==
=== Procediment ===
L'algorisme d'Euclides és iteratiu, això vol dir que la resposta es troba seguint una sèrie de passos repetitius; el resultat de cada pas es fa servir com a dada per al pròxim pas.<ref name="Stark, pàg. 16-20">Stark, pàg. 16-20.</ref> Sia ''k'' un enter que compta els passos de l'algorisme, començant amb zero. Així, el pas inicial es correspon a ''k'' = 0, el pròxim pas es correspon a ''k'' = 1, etcètera.

Cada pas comença amb dos residus no negatius ''r''<sub>''k''−1</sub> i ''r''<sub>''k''−2</sub>. Com que l'algorisme assegura que els residus disminueixen constantment a tots els passos ''r''<sub>''k''−1</sub> és menor que el seu predecessor ''r''<sub>''k''−2</sub>. L'objectiu del ''k''-èsim pas és trobar un [[quocient]] ''q''<sub>''k'' </sub> i un [[Residu (aritmètica) |residu]] ''r''<sub>''k'' </sub> tals que satisfan l'[[equació]]

: <math>r_{k-2}=q_k\ r_{k-1}+r_k</math>

on ''r''<sub>''k''</sub> < ''r''<sub>''k''−1</sub>. En altres paraules, múltiples del nombre més petit ''r''<sub>''k''−1</sub> són restats del nombre el més gran ''r''<sub>''k''−2</sub> fins que la resta sigui més petita que el ''r''<sub>''k''−1</sub>.

Al pas inicial ''(k'' = 0), els residus ''r''<sub>−2</sub> i ''r''<sub>−1</sub> són iguals a ''a'' i ''b'', els nombres per als quals es busca el MCD. Al següent pas ''(k'' = 1), els residus són iguals a ''b'' i el residu ''r'' <sub>0</sub> del pas inicial, etcètera. Així, l'algorisme es pot escriure com a seqüència d'equacions

: <math>a=q_0\ b+r_0</math>
: <math>b=q_1\ r_0+r_1</math>
: <math>r_0=q_2\ r_1+r_2</math>
: <math>r_1=q_3\ r_2+r_3</math>
: …

Si ''a'' és més petit que ''b'', el primer pas de l'algorisme intercanvia els nombres. Per exemple, si ''a'' < ''b'', el quocient inicial ''q''<sub>0</sub> és igual a zero, i el residu ''r''<sub>0</sub> és ''a''. Així ''r''<sub>''k''</sub> és més petit que el seu predecessor ''r''<sub>''k''−1</sub> per a tot ''k'' ≥ 0.

Com que els residus disminueixen amb tots els passos però mai no poden ser negatius, al final un residu ''r''<sub>''N'' </sub> ha de ser igual a zero, en aquest punt s'atura l'algorisme.<ref name="Stark_p18" >Stark, pàg. 18.</ref> L'últim residu diferent de zero ''r''<sub>''N''−1</sub> és el màxim comú divisor de ''a'' i ''b''. El nombre ''N'' no pot ser infinit perquè hi ha només un nombre finit d'enters no negatius entre el residu inicial ''r''<sub>0</sub> i zero.

=== Demostració de validesa ===
La validesa de l'algorisme d'Euclides es pot demostrar per un argument de dos passos.<ref name="Stark, pàg. 16-20"/> Al primer pas, es demostra que l'últim residu diferent de zero ''r''<sub>''N'' −1</sub> és un divisor dels dos ''a'' i ''b''. Com que és divisor comú, ha de ser menor o igual que el màxim comú divisor ''g''. Al segon pas, es demostra que qualsevol divisor comú de ''a'' i ''b'', incloent-hi ''g'', ha de dividir ''r''<sub>''N'' −1</sub>; per això ''g'' ha de ser menor que o igual a ''r''<sub>''N'' −1</sub>. Aquestes dues conclusions impliquen que ''r''<sub>''N'' −1</sub> = ''g''.

Per demostrar que ''r''<sub>''N'' −1</sub> divideix els dos ''a'' i ''b'' (el primer pas), ''r''<sub>''N'' −1</sub> divideix el seu predecessor ''r''<sub>''N''−2</sub>

: <math>r_{N-2}=q_N\ r_{N-1}</math>

com que el residu final ''r''<sub>''N'' </sub> és zero. ''r'' <sub>''N'' −1</sub> també divideix el seu pròxim predecessor ''r''<sub>''N''−3</sub>

: <math>r_{N-3}=q_{N-1}\ r_{N-2} + r_{N-1}</math>

perquè divideix els dos termes del costat dret de l'equació. Iterant el mateix argument ''r''<sub>''N''−1</sub> divideix tots els residus anteriors, incloent-hi ''a'' i ''b''. Cap dels residus anteriors ''r''<sub>''N''−2</sub>, ''r''<sub>''N''−3</sub>, etc. divideix ''a'' i ''b'', ja que donen un residu diferent de zero. Com que {{nowrap|''r''<sub>''N''−1</sub>}} és un divisor comú de ''a'' i ''b'', ''r''<sub>''N''−1</sub> ≤ ''g''.

Al segon pas, qualsevol nombre natural ''c'' que divideix tant ''a'' com ''b'' (en altres paraules, qualsevol comú divisor de ''a'' i ''b'') divideix els residus ''r''<sub>''k'' </sub>. Per definició ''a'' i ''b'' es poden escriure com múltiples de ''c'' : ''a'' = ''mc'' i ''b'' = ''nc'', on ''m'' i ''n'' són nombres naturals. Per això ''c'' divideix el residu inicial ''r''<sub>0</sub>, des de ''r''<sub>0</sub> = ''a'' − ''q'' <sub>0</sub>''b'' = ''mc'' − ''q''<sub>0</sub>''nc'' = (''m'' − ''q''<sub>0</sub>''n'')''c''. Un argument anàleg demostra que ''c'' també divideix els subsegüents residus ''r''<sub>1</sub>, ''r''₂, etc. Per això, el màxim comú divisor ''g'' ha de dividir ''r''<sub>''N''−1</sub>, el que implica que ''g'' ≤ ''r''<sub>''N''−1</sub>. Com que la primera part de l'argument mostrava l'invers (''r''<sub>''N''−1</sub> ≤ '' g''), resulta que ''g'' = ''r''<sub>''N''−1</sub>. Així ''g'' és el màxim comú divisor de tots els parells de la successió:<ref>Knuth, pàg. 320.</ref><ref name="Lovasz_2003">. {{ref-llibre|autor = Lovász L, Pelikán J, Vesztergombi K |any = 2003 |títol = Discrete Mathematics: Elementary and Beyond |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-95584-4 |pàgines = 100–101}}</ref>

:<math>g=MCD(a,b)=MCD(b,r_0)=MCD(r_0,r_1)=...=MCD(r_{N-2}, r_{N-1})=r_{N-1}</math>
com es volia veure.

=== Exemple ===
[[Fitxer:Euclidean algorithm 1071 462.gif|miniatura|alt=Animació on rajoles quadrades progressivament més petites s'afegeixen per cobrir completament un rectangle.|Animació de l'algorisme. El rectangle verd inicial té dimensions ''a'' = 1071 i ''b'' = 462. S'afegeixen rajoles quadrades de 462×462 fins que romangui un rectangle de 462×147 verd. Aquest s'enrajola amb rajoles quadrades de 147×147 fins que romangui un rectangle de 21×147. Aquest tercer rectangle s'enrajola amb rajoles quadrades de 21×21, no queda cap residu. Així, 21 és el màxim comú divisor de 1071 i 462.]]

Per a il·lustrar-ho, l'algorisme d'Euclides es pot fer servir per trobar el màxim comú divisor de ''a'' = 1071 i ''b'' = 462. Per començar, es resten de 1071 múltiples de 462 fins que el residu sigui menor de 462. Se'n poden restar dos (''q''<sub>0</sub> = 2), deixant un residu de 147

: 1071 = 2 × 462 + 147.

Llavors es resten de 462 múltiples de 147 fins que la resta sigui menor de 147. Se'n poden restar tres (''q''<sub>1</sub> = 3), deixant un residu de 21

: 462 = 3 × 147 + 21.

Llavors es resten de 147 múltiples de 21 fins que la resta sigui menor de 21. Se'n poden restar set (''q''₂ = 7), no deixa cap residu

: 147 = 7 × 21 + 0.

Com que l'últim residu és zero, l'algorisme acaba amb 21 com el màxim comú divisor de 1071 i 462. Això està d'acord amb el MCD(1071, 462) trobat per factorització [[#fonaments|més amunt]]. En forma tabular, els passos són

{| class=wikitable id="algorisme d'Euclides bàsic" style="margin-left:auto; margin-right:auto; text-align:center"
!Pas ''k'' !!Equació!!Quocient i residu
|-
| 0 || 1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub> || ''q''<sub>0</sub> = 2 i ''r''<sub>0</sub> = 147
|-
| 1 || 462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub> || ''q''<sub>1</sub> = 3 i ''r''<sub>1</sub> = 21
|-
| 2 || 147 = ''q''₂ 21 + ''r''₂ || ''q''₂ = 7 i ''r''₂ = 0; l'algorisme s'acaba
|}

=== Visualització ===
L'algorisme d'Euclides es pot visualitzar en termes de l'analogia d'enrajolar donada abans per al màxim comú divisor.<ref name="Kimberling_1983">{{ref-publicació|autor = Kimberling C | any = 1983 | article = A Visual Euclidean Algorithm | publicació = Mathematics Teacher | volum = 76 | pàgines = 108–109}}</ref> Suposant que es vol cobrir completament un rectangle de ''a''-per-''b'' amb rajoles quadrades, on ''a'' és el més gran dels dos nombres. Primer s'intenta enrajolar el rectangle fent servir rajoles quadrades de ''b''-per-''b''; tanmateix, això deixa un rectangle residual ''r''<sub>0</sub>-per-''b'' sense enrajolar, on ''r''<sub>0</sub><''b''. Llavors s'intenta enrajolar el rectangle residual amb rajoles quadrades de r<sub>0</sub>-per-''r''<sub>0</sub>. Això deixa un segon rectangle residual ''r''<sub>1</sub>-per-''r''<sub>0</sub>, que s'intenta enrajolar emprant rajoles quadrades de ''r''<sub>1</sub>-per-''r''<sub>1</sub>, etcètera. La seqüència acaba quan no hi ha cap rectangle residual, és a dir, quan les rajoles quadrades cobreixen el rectangle residual previ exactament. La llargada dels costats de la rajola quadrada més petita és el MCD de les dimensions del rectangle original. Per exemple, la rajola quadrada més petita en la figura adjacent és 21-per-21 (es mostra en vermell), i 21 és el MCD de 1071 i 462, les dimensions del rectangle original (que es mostra en verd).

=== Càlcul dels quocients i els residus ===
{{Vegeu també|Divisió euclidiana}}
A tots els passos ''k'', l'algorisme d'Euclides calcula un quocient ''q''<sub>''k''</sub> i un residu ''r''<sub>''k''</sub> de dos nombres ''r''<sub>''k'' −1</sub> i ''r''<sub>''k'' −2</sub>

: <math>r_{k-2}=q_k\ r_{k-1}+r_k</math>

on la [[valor absolut|magnitud]] de ''r''<sub>''k''</sub> és estrictament menor que la de ''r''<sub>''k'' −1</sub>. L'[[divisió euclidiana|algorisme de divisió]] assegura que sempre existeixen el quocient i el residu. L'algorisme de divisió per a nombres naturals també estableix que ''q''<sub>''k''</sub> i ''r''<sub>''k''</sub> són únics, però això no cal per a l'algorisme d'Euclides.<ref name="Cohn_1962">Cohn, pàg. 104-110.</ref>

En la versió original de l'algorisme d'Euclides, el quocient i el residu es troben per sostracció repetida; és a dir ''r''<sub>''k'' −1</sub> es resta de ''r''<sub>''k'' −2</sub> repetidament fins que la resta ''r''<sub>''k''</sub> és més petita que ''r''<sub>''k'' −1</sub>. Un enfocament més eficient fa servir la divisió d'enters i l'[[operació mòdul]] per calcular el quocient i el residu, respectivament. L'operació mòdul dona el residu de dos nombres després de dividir-los; així

: <math>r_k \equiv r_{k-2}\ mod\ r_{k-1}</math>

El residu és equivalent a la classe de congruència en [[aritmètica modular]].

=== Implementacions ===
Les aplicacions de l'algorisme es poden expressar en el [[pseudocodi]]. Per exemple, la versió basada en la divisió es pot [[programació d'ordinadors|programar]] com.<ref>Knuth, pàg. 319-320.</ref>

 '''funció''' mcd(a, b)
 '''mentre''' b ≠ 0
 t := b
 b := a '''mod''' b
 a := t
 '''retorna''' a

Al començament de la iteració ''k''-èsima, la variable ''b'' conté l'últim residu ''r''<sub>''k''−1</sub>, mentre que la variable ''a'' conté el seu predecessor, ''r''<sub>''k''−2</sub>. El pas ''b'' := ''a'' mod ''b'' és equivalent a la fórmula de recurrència citada ''r''<sub>''k''</sub> ≡ ''r''<sub>''k'' −2</sub> mod ''r''<sub>''k'' −1</sub>. La [[variable auxiliar]] ''t'' conté el valor de ''r''<sub>''k''−1</sub> mentre el proper residu ''r''<sub>''k'' </sub> està sent calculat. Al final de la iteració del bucle, la variable ''b'' conté el residu ''r''<sub>''k''</sub>, mentre que la variable ''a'' conté el seu predecessor, ''r''<sub>''k'' −1</sub>.

En la versió basada en la sostracció definida per Euclides, el càlcul del residu (''b'' = ''a'' mod ''b'') és reemplaçat per una sostracció repetida.<ref>Knuth, pàg. 318-319.</ref>

 '''funció''' mcd(a, b)
 '''si''' a = 0
 '''retorna''' b
 '''mentre''' b ≠ 0
 '''si''' a > b
 a := a − b
 '''altrament'''
 b := b − a
 '''retorna''' a

Les variables ''a'' i ''b'' contenen alternativament els residus previs ''r''<sub>''k'' −1</sub> i ''r''<sub>''k'' −2</sub>. Suposant que ''a'' és més gran que ''b'' al començament d'una iteració; llavors ''a'' és igual a ''r''<sub>''k'' −2</sub>, com que ''r''<sub>''k'' −2</sub> > ''r''<sub>''k'' −1</sub>. Durant la iteració del bucle ''a'' es redueix per múltiples restes de ''b'' fins que ''a'' és més petit que ''b''. Llavors ''a'' és el pròxim residu ''r''<sub>''k''</sub>. Llavors ''b'' es redueix per múltiples restes de ''a'' fins que sigui una altra vegada més petit que ''a'', donant el pròxim residu ''r''<sub>''k'' +1</sub>, etcètera.

La versió recursiva<ref>Stillwell, pàg. 14.</ref> es basa en la igualtat de MCDs dels successius residus i la condició d'aturada MCD('' r''<sub>''N'' −1</sub>, 0) = ''r''<sub>''N'' −1</sub>.

 '''funció''' mcd(a, b)
 '''si''' b = 0
 '''retorna''' a
 '''altrament'''
 '''retorna''' mcd(b, a '''mod''' b)

Per il·lustrar-ho, el MCD(1071, 462) es calcula a partir de l'equivalent MCD(462, 1071 mod 462) = MCD(462, 147). Aquest últim MCD es calcula a partir del MCD(147, 462 mod 147) = MCD(147, 21), que al seu torn es calcula a partir de MCD(21, 147 mod 21) = MCD(21, 0) = 21.

=== Mètode dels residus mínims absoluts ===
En una altra versió de l'algorisme d'Euclides, el quocient a cada pas s'augmenta en una unitat si el residu negatiu que resulta és més petit en magnitud que el residu positiu típic.<ref name="Ore_least_abs_remainders" >Oregon, pàg. 43.</ref><ref name="Stewart_1964">. {{ref-llibre|autor = Stewart BM |any = 1964 |títol = Theory of Numbers |edició =2a ed.|editorial = Macmillan |lloc = Nova York|id = LCCN 64-0-10964 |pàgines = 43–44}}</ref> Prèviament, l'equació

: <math>r_{k-2}=q_k\ r_{k-1} + rk</math>

suposa que ''r''<sub>''k'' −1</sub> > ''r''<sub>''k'' </sub> > 0. Tanmateix, es pot calcular un residu negatiu alternatiu ''e''<sub>''k'' </sub>

: <math>r_{k-2}=(q_k+1)\ r_{k-1} + e_k</math>

on ''r''<sub>''k'' −1</sub> se suposa que és positiu. Si |''e''<sub>''k''</sub>| < |''r''<sub>''k''</sub>|, llavors ''r''<sub>''k'' </sub> és reemplaçat per ''e''<sub>''k''</sub>. Com va demostrar [[Leopold Kronecker]], aquesta versió és la que exigeix el mínim nombre de passos de totes les versions de l'algorisme d'Euclides.<ref name="Ore_least_abs_remainders"/><ref name="Stewart_1964"/>

== Desenvolupament històric ==
[[Fitxer:Euklid.jpg|miniatura|alt="Quadre que representa Euclides com un home barbut que aguanta un parell de compassos de puntes sobre una tauleta."|L'algorisme d'Euclides es va inventar probablement segles abans d'[[Euclides]], que es mostra aquí amb un parell de [[compàs de puntes|compassos de puntes]] a la mà.]]

L'algorisme d'Euclides és un dels algorismes més antics que encara es fa servir habitualment.<ref name="Knuth, pàg. 318">Knuth, pàg. 318.</ref> Apareix als [[elements d'Euclides]] (circa. 300 aC), específicament al Llibre 7 (Proposicions 1-2) i al Llibre 10 (Proposicions 2-3). En el Llibre 7, l'algorisme es formula per a enters, mentre que al Llibre 10, es formula per a llargades de segments de recta. (En l'ús modern, es diria que aquí es formulava per a [[nombre real|nombres reals]]. Però les llargades, àrees, i volums, representats com nombres reals en l'ús modern, no es mesuren en les mateixes unitats i no hi ha cap unitat natural de llargada, àrea, o volum, i el concepte de nombres reals era desconegut en aquella època.) L'últim algorisme és geomètric. El MCD de dues llargades ''a'' i ''b'' correspon a la llargada més gran ''g'' que mesura ''a'' i ''b'' uniformement; en altres paraules, les llargades ''a'' i ''b'' són les dues múltiples enteres de la llargada ''g''.

Probablement l'algorisme no el va descobrir [[Euclides]], qui va compilar els resultats de matemàtics anteriors en el seu llibre ''Elements''.<ref name="Weil_1983">{{ref-llibre|autor = [[André Weil|Weil A]] |any = 1983 |títol = Number Theory |editorial = Birkhäuser |lloc = Boston|isbn = 0-8176-3141-0 |pàgines = 4–6}}</ref><ref name="Jones_1994">. {{ref-llibre|autor = Jones A |any = 1994 |capítol = Greek mathematics to AD 300 |títol = Companion encyclopedia of the history and philosophy of the mathematical sciences |editorial = Routledge |lloc = Nova York|isbn = 0-415-09238-8 |pàgines = 46–48}}</ref> El matemàtic i l'historiador [[Bartel van der Waerden]] suggereix que el Llibre VII deriva d'un llibre de text sobre [[teoria de nombres]] escrit per matemàtics de l'escola de [[Pitàgores]].<ref name="van_der_Waerden_1954">{{ref-llibre|autor = [[Bartel van der Waerden|van der Waerden BL]] |any = 1954 |títol = Science Awakening |col·lecció = translated by Arnold Dresden |editorial = P. Noordhoff Ltd |lloc = Groningen|pàgines = 114–115}}</ref> L'algorisme probablement era conegut per [[Èudox de Cnidos]] (sobre el 375 AC.).<ref name="Knuth, pàg. 318"/><ref>. {{ref-publicació|autor = von Fritz K | data = 1945 | article = The Discovery of Incommensurability by Hippasus of Metapontum | publicació = Ann. Math. | volum = 46 | pàgines = 242–264 | doi = 10.2307/1969021}}</ref> L'algorisme pot fins i tot predatar Èudox,<ref>{{ref-llibre|autor = T. L. Heath|enllaçautor=Thomas Little Heath |any = 1949 |títol = Mathematics in Aristotle |editorial = Oxford Press |pàgines = 80–83}}</ref><ref>. {{ref-llibre|autor = [[David Fowler (mathematician)|Fowler DH]] |any = 1987 |títol = The Mathematics of Plato's Academy: A New Reconstruction |editorial = Oxford University Press |lloc = Oxford|isbn = 0-19-853912-6 |pàgines = 31–66}}</ref> sobre la base de l'ús del terme tècnic ἀνθυφαίρεσις (''anthyphairesis'', sostracció recíproca) en treballs d'Euclides i Aristòtil.<ref>{{ref-publicació|autor = Becker O | any = 1933 | article = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | publicació = Quellen und Studien zur Geschichte der Mathematik B | volum = 2 | pàgines = 311–333}}</ref>

Segles més tard, l'algorisme d'Euclides es descobria independentment tant a l'Índia com a la Xina,<ref name="Stillwell, pàg. 31">Stillwell, pàg. 31.</ref> principalment per resoldre equacions diofàntiques que sorgeixen en astronomia i per fer calendaris acurats. A finals del {{segle|V}}, el matemàtic i l'astrònom indi [[Aryabhata]] descriu l'algorisme com el "polvoritzador",<ref name="Tattersall, pàg. 70">Tattersall, pàg. 70.</ref> potser a causa de la seva eficàcia en la solució d'[[Equació diofàntica|equacions diofàntiques]].<ref>Rosen, pàg. 86-87.</ref> Encara que un cas especial del [[teorema xinès del residu]] ja havia estat descrit pel matemàtic i astrònom xinès [[Sun Tzu (matemàtic)|Sun Tzu]],<ref>Oregon, pàg. 247-248.</ref> la solució general era publicada per [[Qin Jiushao]] al seu llibre de 1247 ''Shushu Jiuzhang'' (數書九章 [[Els nou capítols de les arts matemàtiques]]).<ref>Tattersall, pàg. 72, 184-185.</ref> L'algorisme euclidià es descrivia per primera vegada a Europa a la segona edició del llibre de [[Claude Gaspard Bachet de Méziriac|Bachet]] ''Problèmes plaisants et délectables'' (''problemes agradables i divertits'', 1624).<ref name="Tattersall, pàg. 70"/> A Europa, s'utilitzava igualment per resoldre equacions diofàntiques i per obtenir desenvolupaments de [[fracció contínua|fraccions contínues]]. L'[[algorisme d'Euclides ampliat]] era publicat pel matemàtic anglès [[Nicholas Saunderson]], que l'atribuïa a [[Roger Cotes]] com a mètode de càlcul eficient de fraccions contínues.<ref>Tattersall, pàg. 72-76.</ref>

El 1811, [[Antoine André Louis Reynaud|Reynaud]] feia el que sembla el primer anàlisi explícit de l'algorisme.<ref>Shallit, pàg. 409.</ref> Al {{segle|XIX}}, l'algorisme euclidià portava al desenvolupament de nous sistemes de nombres, com els [[Enter de Gauss|Enters gaussians]] i els [[Enter d'Eisenstein|enters d'Eisenstein]]. El 1815, [[Carl Friedrich Gauß|Carl Gauss]] utilitzava l'algorisme euclidià per demostrar la factorització única dels [[Enter de Gauss|Enters gaussians]], encara que el seu treball es publicava per primera vegada el 1832.<ref name="Gauss_1832"/> Gauss esmenta l'algorisme en el seu ''[[Disquisitiones arithmeticae]]'' (publicat el 1801), però només com a mètode per [[fracció contínua|fraccions contínues]].<ref name="Stillwell, pàg. 31"/> [[Émile Léger]] (1837) sembla haver estat el primer en descobrir el pitjor cas de l'algorisme: quan els inputs són [[nombres de Fibonacci]] consecutius.<ref>Shallit, pàg. 410.</ref> [[Johann Peter Gustav Lejeune Dirichlet|Peter Dirichlet]] sembla haver estat el primer a descriure l'algorisme euclidià com la base de gran part de la teoria de nombres.<ref>Stillwell, pàg. 31-32.</ref> Dirichlet va observar que molts resultats de la teoria de nombres, com la factorització única, valdrien per a qualsevol altre sistema de nombres al qual es pogués aplicar l'algorisme euclidià.<ref>Dirichlet, pàg. 29-31.</ref> les conferències de Dirichlet sobre teoria de nombres eren editades i difoses per [[Richard Dedekind]], que utilitzava l'algorisme d'Euclides per estudiar [[enters algebraics]], un tipus general nou de nombres. Per exemple, Dedekind era el primer a demostrar el [[Teorema de la suma de dos quadrats]] de Fermat que utilitza la factorització única d'enters gaussians.<ref>{{ref-llibre|autor = [[Richard Dedekind|Dedekind R]] |any = 1894 |capítol = Supplement XI |títol = Vorlesungen über Zahlentheorie |editor = PGL Dirichlet}}</ref> Dedekind també definia el concepte d'un [[anell euclidià|domini euclidià]], un sistema de nombres en el qual es pot definir una versió generalitzada de l'algorisme euclidià (com es descriu [[#Dominis euclidians|més avall]]). En les dècades finals del {{segle|XIX}}, tanmateix, l'algorisme euclidià gradualment es veia eclipsat per la teoria més general de Dedekind d'[[ideal (matemàtiques)|ideals]].<ref>{{ref-llibre|autor = [[John Stillwell|Stillwell J]] |any = 2003 |títol = Elements of Number Theory |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-95587-9 |pàgines = 41–42}}</ref>

{| class="toccolours" style="float: left; margin-left: 1em; margin-right: 1em; font-size: 85%; background:#c6dbf7; color:black; width:23em; max-width: 25%;" cellspacing="5"
| style="text-align: left;" |
"[L'algorisme d'Euclides] és el iaio de tots els algorismes, perquè és l'algorisme no trivial més vell que ha sobreviscut fins al dia d'avui."
|-
| style="text-align: left;" | [[Donald Knuth]], ''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', 2a edició (1981), pàg. 318.
|}

Altres aplicacions de l'algorisme d'Euclides es desenvolupaven al {{segle|XIX}}. El 1829 [[Jacques Charles François Sturm|Charles Sturm]] mostrava que l'algorisme era útil en el mètode [[Teorema de Sturm|la cadena de Sturm]] per comptar les arrels reals de polinomis en qualsevol interval donat.<ref>{{ref-publicació|autor = Sturm C | any = 1829 | article = Mémoire sur la résolution des équations numériques | publicació = Bull. des sciences de Férussac | volum = 11 | pàgines = 419–422}}</ref>

L'algorisme euclidià va ser el primer [[algorisme de relació entera]], que és un mètode per trobar relacions enteres entre nombres reals proporcionals. En els darrers anys s'han desenvolupat uns quants algorismes de relació entera nous, com l'[[algorisme de Ferguson-Forcade]] (1979) el de [[Helaman Ferguson]] i R.W. Forcade,<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> i els seus parents, l'[[algorisme LLL]], l'[[algorisme HJLS]], i l'[[algorisme PSLQ]].<ref>{{ref-publicació|autor = Peterson I | data = 12 agost 2002 | url = http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm |article = Jazzing Up Euclid's Algorithm | publicació = ScienceNews}}</ref><ref>. {{ref-publicació | autor = Cipra BA | url = http://amath.colorado.edu/resources/archive/topten.pdf | article = The Best of the 20th Century: Editors Name Top 10 Algorithms] | publicació = SIAM News | volum = 33 | exemplar = 4 | data = 16 maig 2000 | editorial = [[Society for Industrial and Applied Mathematics]] | consulta = 30 de maig 2010 | arxiuurl = https://web.archive.org/web/20090407080904/http://amath.colorado.edu/resources/archive/topten.pdf | arxiudata = 7 d’abril 2009 }} {{Webarchive|url=https://web.archive.org/web/20090407080904/http://amath.colorado.edu/resources/archive/topten.pdf |date=7 d’abril 2009 }}</ref>

El 1969, Cole i Davie desenvolupaven un joc de dos jugadors basat en l'algorisme euclidià, anomenat ''El Joc d'Euclides'',<ref>{{ref-publicació|autor = Cole AJ, Davie AJT | any = 1969 | article = A game based on the Euclidean algorithm and a winning strategy for it | publicació = Math. Gaz. | volum = 53 | pàgines = 354–357 | doi = 10.2307/3612461}}</ref> que té una estratègia òptima.<ref>{{ref-publicació|autor = Spitznagel EL | any = 1973 | article = Properties of a game based on Euclid's algorithm | publicació = Math. Mag. | volum = 46 | pàgines = 87–92}}</ref> Els jugadors comencen amb dues piles de ''a'' i ''b'' pedres. Els jugadors, per torns, treuen ''m'' múltiples de la pila més petita de la més gran. Així, si les dues piles consisteixen en ''x'' i ''y'' pedres, on ''x'' és més gran que ''y'', el pròxim jugador pot reduir la pila més gran de ''x'' pedres a ''x'' − ''my'' pedres, mentre quedi un enter no negatiu. El guanyador és el primer jugador que redueixi una pila a zero pedres.<ref>Rosen, pàg. 95.</ref><ref>. {{ref-llibre|autor = Roberts J |any = 1977 |títol = Elementary Number Theory: A Problem Oriented Approach |editorial = [[MIT Press]] |lloc = Cambridge, Ma|isbn = 0-262-68028-0 |pàgines = 1–8}}</ref>

== Aplicacions matemàtiques ==
=== La identitat de Bézout ===
La [[identitat de Bézout]] estableix que el màxim comú divisor ''g'' de dos enters ''a'' i ''b'' es pot representar com una suma lineal dels dos nombres ''a'' i ''b''.<ref>{{ref-llibre|autor = Jones GA, Jones JM |any = 1998 |capítol = Bezout's Identity |títol = Elementary Number Theory |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|pàgines = 7–11}}</ref> En altres paraules, sempre és possible trobar enters ''s'' i ''t'' tals que ''g'' = ''sa'' + ''tb''.<ref>Rosen, pàg. 81.</ref><ref>. Cohn, pàg. 104.</ref>

Els enters ''s'' i ''t'' es poden calcular a partir dels quocients ''q''<sub>0</sub>, ''q''<sub>1</sub>, etc. tirant enrere l'ordre de les equacions en l'algorisme d'Euclides.<ref>Rosen, pàg. 91.</ref> Començant amb l'equació més propera al final, ''g'' es pot expressar en termes del quocient ''q''<sub>''N'' −1</sub> i els dos residus precedents, ''r''<sub>''N'' −2</sub> i ''r'' <sub>''N''−3</sub>.

: <math>g = r_{N-1} = r_{N-3} - q_{N-1}\ r_{N-2}</math>

De la mateixa manera Aquests dos residus es poden expressar en termes dels seus quocients i dels residus anteriors,

: <math>r_{N-2} = r_{N-4} - q_{N-2}\ r_{N-3}</math>
: <math>r_{N-3}= r_{N-5} - q_{N-3}\ r_{N-4}</math>

Substituint aquestes fórmules per ''r''<sub>''N''−2</sub> i ''r''<sub>''N''−3</sub> a la primera equació dona ''g'' com a suma lineal dels residus ''r''<sub>''N''−4</sub> i ''r''<sub>''N''−5</sub>. El procés de substituir residus per fórmules que impliquen els seus predecessors es pot continuar fins que s'arriba als nombres originals ''a'' i ''b''

: <math>r_2 = r_0 - q_2\ r_1</math>
: <math>r_1 = b - q_1\ r_0</math>
: <math>r_0 = a - q_0\ b</math>

Després que tots els residus ''r''<sub>0</sub>, ''r''<sub>1</sub>, etc. han estat substituïts, l'equació final expressa ''g'' com a suma lineal de ''a'' i ''b'': ''g'' = ''sa'' + ''tb''. La [[identitat de Bézout]] i, per tant, l'algorisme previ, es poden generalitzar al context de [[Anell euclidià|dominis euclidians]].

=== Ideals principals i problemes relacionats ===
La identitat de Bézout proporciona encara una altra definició del màxim comú divisor ''g'' de dos nombres ''a'' i ''b''.<ref name="Leveque_p33" >Leveque, pàg. 33.</ref> Considerem el conjunt de tots els nombres ''ua'' + ''vb'', on ''u'' i ''v'' són dos enters qualssevol. Com que ''a'' i ''b'' són els dos divisibles entre ''g'', tots els nombres en el conjunt són divisibles entre ''g''. En altres paraules, tots els nombres del conjunt són múltiples enters de ''g''. Això és cert per a tots els divisors comuns de ''a'' i ''b''. Tanmateix, a diferència dels altres comuns divisors, el màxim comú divisor és un membre del conjunt; per la identitat de Bézout, triant ''u'' = ''s'' i ''v'' = ''t'' dona ''g''. Un comú divisor més petit no pot ser un membre del conjunt, ja que tots els membres del conjunt han de ser divisibles entre ''g''. Al contrari, qualsevol múltiple ''m'' de ''g'' pot ser obtingut triant ''u'' = ''ms'' i ''v'' = ''mt'', on ''s'' i ''t'' són els enters de la identitat de Bézout. Això es pot veure multiplicant la identitat de Bézout per ''m''

: <math>mg=msa+mtb</math>

Per això, el conjunt de tots els nombres ''ua'' + ''vb'' és equivalent al conjunt de múltiples ''m'' de ''g''. En altres paraules, el conjunt de totes les sumes possibles de múltiples enters de dos nombres (''a'' i ''b'') és equivalent al conjunt de múltiples de MCD(''a'',''b''). El MCD es diu que és el generador de l'[[ideal (matemàtiques)|ideal]] de ''a'' i ''b''. Aquesta definició de MCD condueix als conceptes [[àlgebra abstracta|algebraics abstractes]] moderns d'un [[ideal principal]] (un ideal generat per un únic element) i un [[domini d'ideals principals]] (un [[Domini d'integritat|domini]] en el qual tots els ideals són principals).

Certs problemes es poden resoldre utilitzant aquest resultat.<ref>Schroeder, pàg. 23.</ref> Per exemple, considerem dues copes de volum ''a'' i ''b''. Sumant/restant ''u'' múltiples de la primera copa i ''v'' múltiples de la segona copa, es pot mesurar qualsevol volum ''ua'' + ''vb''. Aquests volums són tots els múltiples de ''g'' = MCD(''a'', '' b'').

=== Algorisme d'Euclides ampliat ===
{{article principal|Algorisme d'Euclides ampliat}}
Els enters ''s'' i ''t'' de la identitat de Bézout es posen calcular eficaçment emprant l'[[algorisme d'Euclides ampliat]]. Aquesta ampliació afegeix dues equacions recursives a l'algorisme d'Euclides.<ref>Rosen, pàg. 90-93.</ref>

: <math>s_k=s_{k-2}-q_{k-1}s_{k-1}</math>
: <math>t_k=t_{k-2}-q_{k-1}t_{k-1}</math>

amb els valors d'engegada

: ''s''<sub>−2</sub> = 1, ''t''<sub>−2</sub> = 0
: ''s''<sub>−1</sub> = 0, ''t''<sub>−1</sub> = 1

Emprant aquesta recurrència, els enters de Bézout ''s'' i ''t'' venen donats per ''s'' = ''s''<sub>''N''</sub> i ''t'' = ''t''<sub>''N''</sub>, on ''N'' és el pas en el qual acaba l'algorisme amb ''r''<sub>''N''</sub> = 0.

La validesa d'aquesta aproximació es pot demostrar per inducció. Suposant que la fórmula de recurrència és correcta fins al pas ''k'' −1 de l'algorisme; en altres paraules, suposant que

: <math>r_j = s_ja + t_jb</math>

per a tot ''j'' menor que ''k''. El pas ''k''-èsim de l'algorisme dona l'equació

: <math>r_k = r_{k-2} - q_{k-1}\ r_{k-1}</math>

Com que la fórmula de recurrència s'ha suposat que és correcte per ''r''<sub>''k''−2</sub> i ''r''<sub>''k''−1</sub>, es poden expressar en termes dels corresponents ''s'' i ''t'' variables

: <math>r_k = (s_{k-2}\ a + t_{k-2}\ b) - q_{k-1}(s_{k-1}\ a + t_{k-1}\ b)</math>

Redistribuint aquesta equació produeix la fórmula de recurrència pel pas ''k'', com calia

: <math>r_k = s_k\ a + t_k\ b = (s_{k-2} - q_{k-1}\ s_{k-1})\ a + (t_{k-2} - q_{k-1}\ t_{k-1})\ b</math>

=== Mètode matricial ===
Els enters ''s'' i ''t'' també es poden trobar emprant un mètode [[matriu (matemàtiques)|matricial]] equivalent.<ref name="Koshy_2002">{{ref-llibre|autor = Koshy T |any = 2002 |títol = Elementary Number Theory with Applications |editorial = Harcourt/Academic Press |lloc = Burlington, Ma|isbn = 0-12-421171-2 |pàgines = 167–169}}</ref> La seqüència d'equacions de l'algorisme d'Euclides

: <math>a = q_0\ b + r_0</math>
: <math>b = q_1\ r_0 + r_1</math>
: …
: <math>r_{N-2} = q_N\ r_{N-1} + 0</math>

es pot escriure com a producte de matrius quocient 2-per-2 que multipliquen un vector residu bidimensional

:<math alt=t="Un sèrie d'equacions que consisteixen en vectors bidimensionals multiplicats per un nombre sempre creixent de matrius 2-per-2. El vector un b és igual a la matriu q sub zero 1 1 0 vegades el vector b r sub zero. També les igual a la matriu q sub zero 1 1 0 vegades la matriu q sub un 1 1 0 vegades el vector r sub zero r sub un. Continuant fins al final el pas N de l'algorisme, guala el producte de totes les matrius 2-per-2 de la forma q sub i 1 1 0 multiplicat pel vector r sub N menys un sub N. L'índex i varia des de 0 fins a N i l'últim residu sub N és zero.">
\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_{0} \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_{1} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{0} \\ r_{1} \end{pmatrix} =
\cdots =
\prod_{i=0}^{N} \begin{pmatrix} q_{i} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix}
</math>

Si '''M''' representa el producte de totes les matrius quocient

:<math alt="La matriu 2-per-2 M té quatre components, m sub 1 1, m sub 1 2, m sub 2 1, i m sub 2 2. Es defineix com el producte de totes les matrius 2-per-2 de la forma q sub i 1 1 0, on l'índex i varia de 0 a N.">
\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} =
\prod_{i=0}^{N} \begin{pmatrix} q_{i} & 1 \\ 1 & 0 \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_{1} & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix}
</math>

Això simplifica l'algorisme euclidià a la forma

:<math alt="El vector bidimensional de a b és igual a la matriu M multiplicada pel vector final, r sub N menys un zero. El residu diferent de zero final és el màxim comú divisor g. Per això, el vector a b és igal a la matriu M pel vector g zero.">
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix}
</math>

Per expressar ''g'' com a suma lineal de ''a'' i ''b'', els dos costats d'aquesta equació es poden multiplicar per l'[[matriu invertible|invers]] de la matriu '''M'''.<ref name="Koshy_2002"/><ref name="Bach_1996">{{ref-llibre|autor = Bach E, Shallit J |any = 1996 |títol = Algorithmic number theory |editorial = MIT Press |lloc = Cambridge, Ma|isbn = 0-262-02405-5 |pàgines = 70–73}}</ref> El [[determinant (matemàtiques)|determinant]] de '''M''' és igual a (−1)<sup>''N''+1</sup>, ja que és igual al producte dels determinants de les matrius quocient, cada un dels quals és menys u. Com que el determinant de '''M''' no és mai zero, el vector dels residus finals es pot resoldre fent servir l'invers de '''M'''

:<math alt="El vector bidimensional g 0 és igual a l'invers de la matriu M pel vector a b. Això és igual a menys u elevat a la potència Nèssima més u, per la matriu amb components m sub 2 2, menys m sub 1 2, menys m sub 2 1, i m sub 1 1, pel vector a b.">
\begin{pmatrix} g \\ 0 \end{pmatrix} =
\mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} =
(-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix}
</math>

Com que la primera equació dona

:<math>g=(-1)^{N+1}\ (m_{22}\ a - m_{12}\ b)</math>

els dos enters de la identitat de Bézout són <math>s=(-1)^{N+1} m_{22}</math> i <math>t=(-1)^N m_{12}</math>. El mètode matricial és tan eficient com la recurrència equivalent, amb dues multiplicacions i dues addicions per pas de l'algorisme euclidià.

=== El lema d'Euclides i la factorització única ===
La identitat de Bézout és essencial per moltes aplicacions de l'algorisme d'Euclides, com per exemple per demostrar la [[domini de factorització única|factorització única]] de nombres en factors primers.<ref>Stark, pàg. 26-36.</ref> Per il·lustrar això, suposem que un nombre ''L'' es pot escriure com a producte de dos factors ''u'' i ''v'', és a dir ''L'' = ''uv''. Si un altre nombre ''w'' també divideix ''L'' però és coprimer amb ''u'', llavors ''w'' ha de dividir ''v'', per l'argument següent: Si el màxim comú divisor de ''u'' i ''w'' és 1, llavors es poden trobar enters ''s'' i ''t'' tals que

: 1 = ''su'' + ''tw''

per la identitat de Bézout. Multiplicant els dos costats per ''v'' dona la relació

: ''v'' = ''suv'' + ''twv'' = ''sL'' + ''twv''

Com que ''w'' divideix els dos termes del costat dret, també ha de dividir el costat esquerre, ''v''. Aquest resultat es coneix com el [[lema d'Euclides]].<ref name="Oregon, pàg. 44">Oregon, pàg. 44.</ref> Específicament, si un nombre primer divideix ''L'', llavors ha de dividir com a mínim un factor de ''L''. Recíprocament, si un nombre ''w'' és coprimer amb cada un d'una sèrie de nombres <math>a_1,a_2,...,a_n</math>, llavors ''w'' és també coprimer amb el seu producte, <math>a_1\times a_2\times \ldots\times a_n</math>.<ref name="Oregon, pàg. 44"/>

El lema d'Euclides és suficient per demostrar que tots els nombres tenen una factorització única en nombres primers.<ref>Stark, pàg. 281-292.</ref> Per veure això, suposant el contrari, que hi ha dues factoritzacions independents de ''L'' en ''m'' i ''n'' factors primers, respectivament

: <math>L = p_1p_2\ldots p_m = q_1q_2\ldots q_n</math>

Com que cada primer ''p'' divideix ''L'' per hipòtesi, també ha de dividir un dels ''q'' factors; com que cada ''q'' també és primer, ha de ser ''p'' = ''q''. Iterativament dividint entre ''p'' factors es demostra que cada ''p'' té una contrapartida igual ''q''; les dues factoritzacions en nombres primers són idèntiques amb l'excepció del seu ordre. La factorització única de nombres primers té moltes aplicacions en demostracions matemàtiques, com es mostra més avall.

=== Equacions diofàntiques lineals ===
[[Fitxer:Diophante Bezout.svg|miniatura|alt="línia diagonal de la cantonada de dalt a l'esquerra a la de baix a la dreta. Quinze circumferències s'espaien a intervals regulars al llarg de la línia. Els eixos de coordenades x-y perpendiculars tenen el seu origen a la cantonada d'abaix a l'esquerra; la línia creua l'eix d'ordenades a dalt a l'esquerra i l'eix d'abcisses a baix a la dreta."|Gràfic d'una [[Equació diofàntica]] lineal, 9''x'' + 12''y'' = 483. Les solucions es mostren com circumferències blaves.]]

Les [[Equació diofàntica|equacions diofàntiques]] són equacions en les quals les solucions es restringeixen a enters; se'ls posa el nom del matemàtic alexandrí de {{segle|III}} [[Diofant d'Alexandria|Diofant]].<ref>Rosen, pàg. 119-125.</ref> Una equació diofàntica ''lineal'' típica busca enters ''x'' i ''y'' tals que:<ref>Schroeder, pàg. 106-107.</ref>

: ''ax'' + ''by'' = ''c''

on ''a'', ''b'' i ''c'' són enters donats. Això es pot escriure com equació de ''x'' en [[aritmètica modular]]

: ''ax'' &equiv; ''c'' mod ''b''.

Sia ''g'' el màxim comú divisor de ''a'' i ''b''. Els dos termes de ''ax'' + ''by'' són divisibles per ''g''; per això ''c'' també ha de ser divisible entre ''g'', o l'equació no té solucions. Dividint els dos costats per ''c''/''g'', l'equació es pot reduir a la identitat de Bézout

: ''sa'' + ''tb'' = ''g''

on ''s'' i ''t'' es poden trobar amb l'algorisme euclidià estès.<ref>Schroeder, pàg. 108-109.</ref> Això proporciona una solució a l'equació diofàntica, <math>x_1=s(c/g)</math> i <math>y_1=t(c/g)</math>.

En general, una equació diofàntica lineal no té solucions, o en té un nombre infinit.<ref>Rosen, pàg. 120-121.</ref> Per trobar-les en l'últim cas, considerant dues solucions, <math>(x_1,y_1)</math> i <math>(x_2,y_2)</math>

: <math>ax_1+by_1=c=ax_2+by_2</math>

o equivalentment

: <math>a(x_1-x_2)=b(y_2-y_1)</math>.

Per això, la diferència més petita entre dues solucions ''x'' és ''b''/''g'', mentre que la diferència més petita entre dues solucions ''y'' és ''a''/''g''. Així, les solucions es poden expressar com

:<math>x=x_1-bt/g</math>
:<math>y=y_1+at/g</math>.

Permetent que ''t'' variï sobre tots els enters possibles, es pot generar una família infinita de solucions a partir d'una solució única (''x''<sub>1</sub>, ''y''<sub>1</sub>). Si s'exigeix que les solucions siguin enters ''positius'' (''x'' > 0, ''y'' > 0), només hi ha un nombre finit de solucions possibles. Aquesta restricció de les solucions acceptables permet que sistemes d'equacions diofàntiques siguin resoltes amb més incògnites que equacions;<ref>Stark, pàg. 47.</ref> això és impossible per a un [[sistema d'equacions lineals]] quan les solucions poden ser [[nombre real|nombres reals]] qualssevol.

=== Inversa multiplicativa i l'algorisme RSA ===
Un [[cos finit]] és un conjunt de nombres amb quatre operacions generalitzades. Les operacions s'anomenen addició, sostracció, multiplicació i divisió i tenen les seves propietats habituals, com la [[propietat commutativa]], la [[propietat associativa]] i la [[propietat distributiva]]. Un exemple d'un cos finit és el conjunt de 13 nombres {0, 1, 2, …, 12} emprant [[aritmètica modular]]. En aquest cos, els resultats de qualsevol operació matemàtica (addició/sostracció/multiplicació/divisió) es redueix [[mòdul]] 13; és a dir, s'afegeixen múltiples de 13 o es resten fins que el resultat es porti dins de la gamma 0-12. Per exemple, el resultat de 5 × 7 = 35 mod 13 = 9. Tals cossos finits es poden definir per a qualsevol primer ''p''; fent servir definicions més sofisticades, també es poden definir per a qualsevol potència ''m'' d'un nombre primer ''p''<sup>''m''</sup>. Els cossos finits s'anomenen sovint cossos de [[Évariste Galois|Galois]], i s'abreugen com GF(''p'') o GF(''p''<sup>''m''</sup>).

En un cos amb ''m'' nombres, tot [[Element (matemàtiques)|element]] diferent de zero ''a'' té un [[inversos multiplicatius|invers multiplicatiu]] [[modular]] únic, ''a''<sup>−1</sup> tal que ''aa''<sup>−1</sup> = ''a''<sup>−1</sup>''a'' ≡ 1 mod ''m''. Aquest invers es pot trobar resolent l'equació de congruència ''ax'' ≡ 1 mod ''m'',<ref>Schroeder, pàg. 107-109.</ref> o l'equació diofàntica lineal equivalent.<ref>Stillwell, pàg. 186-187.</ref>

: ''ax'' + ''my'' = 1

Aquesta equació pot ser resolta per l'algorisme euclidià, com s'ha descrit [[#Equacions diofàntiques lineals|més amunt]]. Trobar inversos multiplicatius és un pas essencial en l'[[RSA|algorisme de RSA]], que s'utilitza àmpliament en [[comerç electrònic]]; específicament, l'equació determina l'enter utilitzat per desxifrar el missatge.<ref>Schroeder, pàg. 134.</ref> Cal notar que, encara que l'algorisme RSA fa servir [[anell (matemàtiques)|anells]] més que cossos, l'algorisme euclidià encara es pot fer servir per trobar un invers multiplicatiu on existeix. L'algorisme euclidià també té altres aplicacions a [[Reed-Solomon|codis correctors]]; per exemple, es pot utilitzar com a alternativa a l'[[algorisme de Berlekamp-Massey]] per desxifrar els codis [[codi BCH|BCHh]] i [[codi Reed-Solomon|Reed-Solomon]], es quals es basen en cossos de Galois.<ref>"Error correction coding: mathematical methods and algorithms", pàgina 266, Todd K. Moon, John Wiley and sons, 2005, Isbn 0471648000</ref>

=== Teorema xinès del residu ===
L'algorisme d'Euclides també es pot fer servir per resoldre equacions diofàntiques lineals múltiples.<ref>Rosen, pàg. 143-170.</ref> Tals equacions sorgeixen en el [[teorema xinès del residu]], que descriu un mètode nou per representar un enter ''x''. En comptes de representar un enter pels seus dígits, pot ser representat pels seus residus ''x''<sub>''i''</sub> mòdul un conjunt de ''N'' nombres coprimers ''m''<sub>''i''</sub>.<ref>Schroeder, pàg. 194-195.</ref>

: ''x''<sub>1</sub> &equiv; ''x'' mod ''m''<sub>1</sub>
: ''x''₂ &equiv; ''x'' mod ''m''₂
:…
: ''x''<sub>''N''</sub> &equiv; ''x'' mod ''m''<sub>''N''</sub>

L'objectiu és determinar ''x'' a partir dels seus ''N'' residus ''x''<sub>''i''</sub>. La solució és combinar les equacions múltiples en una única equació diofàntica lineal amb un mòdul molt més gran ''M'' que és el producte de tots els mòduls individuals ''m''<sub>''i'' </sub>, i definir el ''M''<sub>''i''</sub>

: ''M''<sub>''i''</sub> = ''M'' / ''m''<sub>''i''</sub>

Així, cada ''M''<sub>''i''</sub> és el producte de tots els mòduls ''excepte'' ''m''<sub>''i''</sub>. La solució depèn de trobar ''N'' nombres nous ''h''<sub>''i''</sub> tals que

:''M''<sub>''i''</sub>''h''<sub>''i''</sub> &equiv; 1 mod ''m''<sub>''i''</sub>

Amb aquests nombres ''h''<sub>''i''</sub>, qualsevol enter ''x'' pot ser reconstruït a partir dels seus residus ''x''<sub>''i''</sub> per l'equació

: x &equiv; (''x''<sub>1</sub>''M''<sub>1</sub>''h''<sub>1</sub> + ''x''₂''M''₂''h''₂ + … + ''x''<sub>''N''</sub>''M''<sub>''N''</sub>''h''<sub>''N''</sub>) mod ''M''

Com que aquests nombres ''h''<sub>''i''</sub> són els inversos multiplicatius de ''M''<sub>''i''</sub>, es poden trobar emprant l'algorisme d'Euclides com s'ha descrit en la subsecció prèvia.

=== Fraccions Contínues ===
L'algorisme euclidià està íntimament relacionat amb les [[fracció contínua|fraccions contínues]].<ref name="Vinogradov_1954">{{ref-llibre|autor = [[Ivan Matveyevich Vinogradov|Vinogradov IM]] |any = 1954 |títol = Elements of Number Theory |editorial = Dover |lloc = Nova York|pàgines = 3–13}}</ref> La successió d'equacions es pot escriure de la forma

:<math>
\begin{align}
\frac{a}{b} &= q_0 + \frac{r_0}{b} \\
\frac{b}{r_0} &= q_1 + \frac{r_1}{r_0} \\
\frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\
& {}\ \vdots \\
\frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\
& {}\ \vdots \\
\frac{r_{N-2}}{r_{N-1}} &= q_N
\end{align}
</math>

El darrer terme del costat dret és sempre igual a l'invers del costat esquerre de la pròxima equació. Així, les primeres dues equacions es poden combinar per formar

:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}} </math>

La tercera equació es pot utilitzar per substituir el terme del denominador ''r''<sub>1</sub>/''r''<sub>0</sub>, donant

:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}} </math>

La proporció final de residus ''r'' <sub>''k''</sub>/''r''<sub>''k''−1</sub> sempre es pot reemplaçar utilitzant la pròxima equació en la sèrie, fins a l'equació final. El resultat és una fracció contínua

:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \ldots, q_N ] </math>

En l'[[#Exemple|exemple de més amunt]], es calculava el MCD(1071, 462), i els quocients ''q''<sub>''k''</sub> eren 2, 3 i 7, respectivament. Per això, la fracció 1071/462 es pot escriure

:<math>\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3, 7]</math>

com es pot confirmar per càlcul.

=== Algorismes de factorització ===
Calcular un màxim comú divisor és un pas essencial en diversos algorismes de [[factorització dels enters]],<ref>{{ref-llibre|autor = Crandall R, Pomerance C |any = 2001 |títol = Prime Numbers: A Computational Perspective |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-94777-9 |pàgines = 225–349}}</ref> com l'[[algorisme rho de Pollard]],<ref>Knuth, pàg. 369-371.</ref> l'[[algorisme de Shor]],<ref>{{ref-publicació|enllaçautor = Peter Shor |autor=Shor PW | any = 1997 | article = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | publicació = SIAM J. Sci. Statist. Comput. | volum = 26 | pàgines = 1484}}</ref> el [[mètode de factorització de Dixon]]<ref>{{ref-publicació|autor = Dixon JD | any = 1981 | article = Asymptotically fast factorization of integers | publicació = Math. Comput. | volum = 36 | pàgines = 255–260 | doi = 10.2307/2007743}}</ref> i la [[Factorització per corba el·líptica de Lenstra]].<ref>{{ref-publicació|enllaçautor = Hendrik Lenstra |autor=Lenstra Jr. HW | any = 1987 | article = Factoring integers with elliptic curves | publicació = Annals of Mathematics | volum = 126 | pàgines = 649–673 | doi = 10.2307/1971363}}</ref> L'algorisme euclidià es pot utilitzar per trobar aquest MCD eficientment. La [[factorització de fracció contínua]] fa servir fraccions contínues, que es determinen emprant l'algorisme d'Euclides.<ref>Knuth, pàg. 380-384.</ref>

== Eficiència algorísmica ==
[[Fitxer:Euclidean algorithm running time X Y.png|miniatura|alt="Un conjunt de línies pintades de colors que radien cap enfora de l'origen d'un sistema de coordenades de x-y. Cada línia correspon a un conjunt de parells de nombres que exigeixen el mateix nombre de passos en l'algorisme euclidià."|Nombre de passos en l'algorisme euclidià per trobar el MCD(x,y). Els punts vermells indiquen relativament pocs passos (més ràpid), mentre que els punts grocs, verds i blaus indiquen successivament més passos (més lent).]]

L'eficiència computacional de l'algorisme d'Euclides s'ha estudiat minuciosament.<ref>Knuth, pàg. 339-364.</ref> Aquesta eficiència es pot descriure pel nombre de passos que l'algorisme requereix, multiplicat per la despesa computacional de cada pas. Com va demostrar per primera vegada [[Gabriel Lamé]] el 1844,<ref>{{ref-publicació|enllaçautor = Gabriel Lamé|autor=Lamé G | any = 1844 | article = Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers | publicació = Comptes Rendus Acad. Sci. | volum = 19 | pàgines = 867-870}}</ref> el nombre de passos requerits per a l'acabament no és mai més gran que cinc vegades el nombre ''h'' de dígits (base 10) del nombre ''b'' (el més petit).<ref>{{ref-publicació|autor = Grossman H | any = 1924 | article = On the Number of Divisions in Finding a G.C.D. | publicació = The American Mathematical Monthly | volum = 31 | pàgina = 443 | doi = 10.2307/2298146}}</ref><ref>. {{ref-llibre|autor = Honsberger R |any = 1976 |títol = Mathematical Gems II |editorial = The [[Mathematical Association of America]] |isbn = 0-88385-302-7 |pàgines = 54–57}}</ref> Com que la despesa computacional de cada pas és també típicament d'ordre ''h'', la despesa global creix com ''h''².

=== Nombre de passos ===
El nombre de passos per calcular el MCD de dos nombres naturals ''a'' i ''b'', es pot denotar per ''T''(''a'','' b'').<ref name="Knuth, pàg. 344">Knuth, pàg. 344.</ref> Si ''g'' és el MCD de ''a'' i ''b'', llavors ''a'' = ''mg'' i ''b'' = ''ng'' per a dos nombres coprimers ''m'' i ''n''. Llavors

: ''T''(''a'', ''b'') = ''T''(''m'', ''n'')

com es pot veure dividint tots els passos de l'algorisme euclidià per ''g''.<ref>Oregon, pàg. 45.</ref> Pel mateix argument, el nombre de passos roman el mateix si ''a'' i ''b'' es multipliquen per un factor comú ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb''). Per això, el nombre de passos ''T'' pot variar dramàticament entre parells veïns de nombres, com T(''a'', ''b'') i T(''a'', ''b'' + 1), depenent de la mida del dos MCD.

La natura recursiva de l'algorisme euclidià dona una altra equació

: ''T''(''a'', ''b'') = 1 + ''T''(''b'', ''r''<sub>0</sub>) = 2 + ''T''(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = ''N'' + ''T''(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''N'' + 1

on ''T''(''x'', 0) = 0 per hipòtesi.<ref name="Knuth, pàg. 344"/>

==== Nombre de passos en el cas pitjor ====
Si l'algorisme euclidià exigeix ''N'' passos per a un parell de nombres naturals ''a'' > ''b'' > 0, els valors més petits de ''a'' i ''b'' per als quals això és cert són els [[nombres de Fibonacci]] ''F''<sub>''N''+2</sub> i ''F''<sub>''N''+1</sub>, respectivament.<ref name="Knuth, pàg. 343">Knuth, pàg. 343.</ref> Això es pot demostrar per [[demostració per inducció|inducció]].<ref>Mollin, pàg. 21.</ref> Si ''N'' = 1, ''b'' divideix ''a'' sense residu; els nombres naturals més petits per als quals això es compleix són ''b'' = 1 i ''a'' = 2, que és ''F''₂ i ''F''₃, respectivament. Ara suposant que el resultat es compleix per a tots els valors de ''N'' fins a ''M'' − 1. El primer pas de l'algorisme de ''M'' - 1 passos és ''a'' = ''q''<sub>0</sub>''b'' + ''r''<sub>0</sub>, i el segon pas és ''b'' = ''q''<sub>1</sub>''r''<sub>0</sub> + ''r''<sub>1</sub>. Com que l'algorisme és recursiu, exigirà ''M'' − 1 passos per trobar el MCD(''b'', ''r''<sub>0</sub>) i els seus valors més petits són ''F''<sub>''M''+1</sub> i ''F''<sub>''M''</sub>. El valor més petit de ''a'' és per tant quan ''q''<sub>0</sub> = 1, que dona ''a'' = ''b'' + ''r''<sub>0</sub> = ''F''<sub>''M'' +1</sub> + ''F''<sub>''M''</sub> = ''F''<sub>''M'' +2</sub>. Aquesta demostració, publicada per Gabriel Lamé el 1844, representa el començament de la [[complexitat computacional|teoria de complexitat computacional]],<ref>LeVeque, pàg. 35.</ref> i també la primera aplicació pràctica dels nombres de Fibonacci.<ref name="Knuth, pàg. 343"/>

Aquest resultat és suficient per mostrar que el nombre de passos en l'algorisme d'Euclides mai no pot ser més que cinc vegades el nombre dels seus dígits (base 10).<ref>Mollin, pàg. 21-22.</ref> El raonament és el següent: si l'algorisme exigeix ''N'' passos, llavors ''b'' és més gran que o igual a ''F''<sub>''N'' +1</sub> que a canvi és més gran que o igual a ''φ''<sup>''N'' −1</sup>, on ''φ'' és la [[secció àuria|proporció àuria]]. Com que ''b'' ≥ ''φ''<sup>''N'' −1</sup>, llavors ''N'' − 1 ≤ log<sub>''φ''</sub>''b''. Com que log<sub>10</sub>''φ'' > 1/5, (''N'' − 1)/5 < log<sub>10</sub>''φ'' log<sub>''φ''</sub>''b'' = log<sub>10</sub>''b''. Així ''N'' ≤ 5 log<sub>10</sub>'' b''. Per tant, l'algorisme euclidià sempre necessita menys que ''O''(''h'') divisions, on ''h'' és el nombre de dígits del nombre més petit ''b''.

==== Nombre mitjà de passos ====
El nombre mitjà de passos emprats per l'algorisme euclidià s'ha definit de tres maneres diferents. La primera definició és el temps mitjà ''T''(''a'') exigit per calcular el MCD d'un nombre donat ''a'' i un nombre natural més petit ''b'' escollit amb probabilitat igual dels enters 0 a ''a'' − 1.<ref name="Knuth, pàg. 344"/>

:<math alt="La funció T de a és igual a un sobre a multiplicat pel sumatori de la funció T de a coma b sobre tots els valors no negatius de b més petits que a." >
T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b).
</math>

Tanmateix, com que ''T''(''a'', '' b'') fluctua dramàticament amb el MCD dels dos nombres, la funció mitjana ''T''(''a'') és de la mateixa manera "sorollosa".<ref>Knuth, pàg. 353.</ref>

Per reduir aquest soroll, una segona mitjana τ(''a'') es pren sobre tots els nombres coprimers amb ''a''

:<math alt="La funció tau és igual a un sobre la funció phi de a multiplicada pel sumatori de la funció T da a coma b sobre tots els valors no negatius de b menors que A, on b és coprimer amb a." >
\tau(a) = \frac{1}{\varphi(a)} \sum_{{0 \leq b<a \atop \mathrm{GCD}(a, b) = 1}} T(a, b).
</math>

Hi ha ''φ''(''a'') enters coprimers menors que ''a'', on ''φ'' és la [[Funció Fi d'Euler]]. Aquesta mitjana de τ augmenta suaument amb ''a''.<ref>Knuth, pàg. 357.</ref><ref>. {{ref-publicació|autor = Tonkov T | any = 1974 | article = On the average length of finite continued fractions | publicació = Acta arithmetica | volum = 26 | pàgines = 47–57}}</ref>

:τ(''a'') = (12/π²) ln 2 ln a + ''C'' + [[Notació de Landau|''O''(''a''<sup>−(1/6) + ε</sup>)]]

amb l'error residual de l'ordre de ''a''<sup>−(1/6) + ε</sup>, on ε és [[mètodes infinitesimals|infinitesimal]]. La constant ''C'' en aquesta fórmula és igual a

:''C'' = −(1/2) + 6 (ln 2/π²)(4γ − 24π²ζ'(2) + 3 ln 2 − 2) ≈ 1,467

on γ és la [[constant d'Euler-Mascheroni]] i ζ' és la [[derivada]] de la [[Funció zeta de Riemann]].<ref>{{ref-publicació|autor = Porter JW | any = 1975 | article = On a Theorem of Heilbronn | publicació = Mathematika | volum = 22 | pàgines = 20–28}}</ref><ref>{{ref-publicació|autor = Knuth DE | any = 1976 | article = Evaluation of Porter's Constant | publicació = Computers and Mathematics with Applications | volum = 2 | pàgines = 137–139 | doi = 10.1016/0898-1221(76)90025-0}}</ref> El coeficient principal (12/π²) ln 2 es va determinar per dos mètodes independents.<ref>{{ref-publicació|autor = Dixon JD | any = 1970 | article = The Number of Steps in the Euclidean Algorithm | publicació = J. Number Theory | volum = 2 | pàgines = 414–422 | doi = 10.1016/0022-314X(70)90044-2}}</ref><ref>. {{ref-llibre|autor = Heilbronn HA |any = 1969 |capítol = On the Average Length of a Class of Finite Continued Fractions |títol = Number Theory and Analysis |editor = [[Pál Turán]] |editorial = Plenum |lloc = Nova York|id = LCCN 68-00-8991 |pàgines = 87–96}}</ref>

Ja que la primera mitjana es pot calcular a partir de la mitjana de τ sumant sobre els divisors ''d'' de ''a''.<ref>Knuth, pàg. 354.</ref>

:<math alt="La funció T de a és igual a u sobre a multiplicat perl sumtori d'un argument estes sobre tots els divisors d de a. L'argument és igual a la funció phi de d multiplicada per la funció tau de d.">
T(a) = \frac{1}{a} \sum_{d | a} \varphi(d) \tau(d)
</math>

es pot aproximar per la fórmula:<ref name="Norton_1990">{{ref-publicació|autor = Norton GH | any = 1990 | article = On the Asymptotic Analysis of the Euclidean Algorithm | publicació = Journal of Symbolic Computation | volum = 10 | pàgines = 53–58 | doi = 10.1016/S0747-7171(08)80036-3}}</ref>

:''T''(''a'') ≈ ''C'' + (12/π²) ln 2 (ln ''a'' − Σ<sub>''d''|''a''</sub> Λ(''d'')/''d'')

on Λ(''d'') és la [[funció de von Mangoldt]].<ref>Knuth, pàg. 355.</ref>

Una tercera mitjana ''Y'' (''n'') es definieix com el nombre mig de passos requerits quan els dos nombres ''a'' i ''b'' són escollits a l'atzar (amb la distribució uniforme) des de l'1 a ''n''<ref name="Norton_1990"/>

:<math alt="La funció Y és de n és igual a u sobre n quadrat vegades el doble de la suma de la funció T de a coma b per a tots els valors de a i b variant de 1 a n. Això és igual a u sobre n vegades la suma de la funció T de a sobre tots els valors de a variant des de u fins a n.">
Y(n) = \frac{1}{n^{2}} \sum_{a=1}^{n} \sum_{b=1}^{n} T(a, b) = \frac{1}{n} \sum_{a=1}^{n} T(a).
</math>

Substituint la fórmula aproximada per ''T''(''a'') a aquesta equació dona una estimació per ''Y''(''n'').<ref>Knuth, pàg. 356.</ref>

:''Y''(''n'') ≈ (12/π²) ln 2 ln ''n'' + 0,06.

=== Despesa computacional per pas ===
A cada pas ''k'' de l'algorisme euclidià, el quocient ''q''<sub>''k''</sub> i residu ''r''<sub>''k''</sub> es calculen per a un parell donat d'enters ''r''<sub>''k''−2</sub> i ''r''<sub>''k''−1</sub>

: <math>r_{k-2} = q_k\ r_{k-1} + r_k.</math>

La despesa computacional per pas està associada principalment amb trobar ''q''<sub>''k''</sub>, donat que el residu ''r''<sub>''k''</sub> es pot calcular ràpidament a partir de ''r''<sub>''k''−2</sub>, ''r''<sub>''k''−1</sub>, i ''q''<sub>''k''</sub>

: <math>r_k=r_{k-2}-q_k\ r_{k-1}.</math>

La despesa computacional de dividir nombres de ''h'' bits és ''O''(''h''(''ℓ''+1)), on ''ℓ'' és la longitud del quocient.<ref>Knuth, pàg. 257-261.</ref>

Comparativament, l'algorisme basat en la sostracció original d'Euclides pot ser molt més lent. Una única divisió d'enter és equivalent a un nombre de sostraccions igual al quocient ''q''. Si la proporció de ''a'' i ''b'' és molt gran, el quocient és gran i calen moltes sostraccions. D'altra banda, s'ha demostrat que és molt probable que els quocients siguin enters petits. La probabilitat d'un quocient donat ''q'' és aproximadament ln|''u''/(''u'' − 1)|, on ''u'' = (''q'' + 1)².<ref>Knuth, pàg. 352.</ref> Per tenir una idea, la probabilitat que un quocient sigui 1, 2, 3 o 4 és aproximadament un 41,5%, un 17,0%, un 9,3%, i un 5,9%, respectivament. Com que l'operació de sostracció és més ràpida que la divisió, especialment per a nombres grans,<ref>{{ref-llibre|autor = Wagon S |any = 1999 |títol = Mathematica in Action |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-98252-3 |pàgines = 335–336}}</ref> l'algorisme d'Euclides basat en la sostracció és competitiu amb la versió basada en la divisió.<ref>Cohen, pàg. 14.</ref> Això s'explota en la [[versió binària]] de l'algorisme d'Euclides.<ref>Cohen, pàg. 14-15, 17-18.</ref>

Combinant el nombre aproximat de passos amb la despesa computacional aproximada per pas es mostra que l'algorisme de l'Euclides augmenta de manera quadràtica (''h''²) amb el nombre mitjà de dígits ''h'' dels dos nombres inicials ''a'' i ''b''. Sia ''h''<sub>0</sub>, ''h''<sub>1</sub>, …, ''h''<sub>''N''−1</sub> el nombre de dígits en els successius residus ''r''<sub>0</sub>, ''r''<sub>1</sub>, …, ''r''<sub>''N''−1</sub>. Com que el nombre de passos ''N'' creix linealment amb ''h'', el temps d'execució queda fitat per

:<math alt="L'ordre del sumatori sobre tot i menor que N de h sub i multiplicat per parèntesi h sub i menys h sub i més u més 2 tanca parèntesi és un subconjunt de l'ordre de h pel sumatori sobre tot i menor que N de h sub i menys h sub i més u més 2, que a la vegada és un subconjunt de l'ordre de h multiplicat per h sub zero més 2 N, que a l'hora és un subconjunt de l'ordre de h al quadrat.">
O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2)\Big)\subseteq O(h(h_0+2N))\subseteq O(h^2).</math>

=== Eficiència de mètodes alternatius ===
L'algorisme d'Euclides es fa servir a bastament en la pràctica, especialment per a nombres petits, a causa de la seva simplicitat. Per comparació, es pot determinar l'eficiència d'alternatives a l'algorisme d'Euclides.

Una aproximació ineficaç per trobar el MCD de dos nombres naturals ''a'' i ''b'' és trobar tots els seus divisors comuns; el MCD és llavors el comú divisor més gran. Els divisors comuns es poden trobar dividint els dos nombres per enters successius des de 2 fins al nombre més petit ''b''. El nombre de passos d'aquest enfocament augmenta linealment amb ''b'', o exponencialment en el nombre de dígits. Una altra aproximació ineficaç és trobar els factors primers d'un o els dos nombres. Com s'ha comentat més [[#Màxim Comú Divisor|amunt]], el MCD és igual al producte dels factors primers compartits pels dos nombres ''a'' i ''b''.<ref name="Schroeder_21"/> Els mètodes actuals per [[descomposició en factors primers]] són també ineficients; molts sistemes de criptografia moderns fins i tot depenen d'aquesta ineficiència.<ref name="Schroeder_216"/>

L'[[algorisme de Stein]] és una alternativa eficient que substitueix la divisió per operacions més ràpides explotant la representació [[Codi binari|binària]] emprada pels ordinadors.<ref>Knuth, pàg. 321-323.</ref><ref>{{ref-publicació|autor = Stein J | any = 1967 | article = Computational problems associated with Racah algebra | publicació = Journal of Computational Physics | volum = 1 | pàgines = 397–405 | doi = 10.1016/0021-9991(67)90047-2}}</ref> Tanmateix, aquesta alternativa també és ''O''(''H''²). És generalment més ràpid en ordinadors reals, però l'ordre de magnitud és el mateix que a l'algorisme euclidià.<ref name="Crandall_2001">{{ref-llibre|autor = Crandall R, Pomerance C |any = 2001 |títol = Prime Numbers: A Computational Perspective |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-94777-9 |pàgines = 77–79, 81–85, 425–431}}</ref> L'eficiència addicional es pot assolir gràcies a examinar només els dígits principals dels dos nombres ''a'' i ''b''.<ref>Knuth, pàg. 328.</ref><ref>. {{ref-publicació|autor = Lehmer DH | any = 1938 | article = Euclid's Algorithm for Large Numbers | publicació = The American Mathematical Monthly | volum = 45 | pàgines = 227–233 | doi = 10.2307/2302607}}</ref> L'algorisme de Stein que treballa en base 2 es pot estendre a altres bases (algorismes base ''k''),<ref>{{ref-publicació|autor = Sorenson J | any = 1994 | article = Two fast MCD algorithms | publicació = J. Algorithms | volum = 16 | pàgines = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref> amb augments de velocitat de fins a un factor 5.<ref>{{ref-publicació|autor = Weber K | any = 1995 | article = The accelerated MCD algorithm | publicació = ACM Trans. Math. Soft. | volum = 21 | pàgines = 111–122 | doi = 10.1145/200979.201042}}</ref>

Un enfocament recursiu per a enters molt grans (amb més de 25.000 dígits) porta a ''algorismes de MCD subquadràtics'',<ref>{{ref-llibre|autor = [[Alfred Aho|Aho A]], [[John Hopcroft|Hopcroft J]], [[Jeffrey Ullman|Ullman J]] |any = 1974 |títol = The Design and Analysis of Computer Algorithms |editorial = Addison–Wesley |lloc = Nova York|pàgines = 300–310}}</ref> com els de Schönhage,<ref>{{ref-publicació|autor = Schönhage A | article = Schnelle Berechnung von Kettenbruchentwicklungen | publicació = Acta Informatica | volum = 1 | pàgines = 139–144 | doi = 10.1007/BF00289520 | any = 1971}}</ref><ref>. {{ref-llibre|autor = Cesari G |any = 1998 |capítol = Parallel implementation of Schönhage's integer MCD algorithm |títol = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR |editor = G. Buhler |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|pàgines = 64–76}} Volum 1423 en ''bitllets de Conferència en la Informàtica''.</ref> i Stehlé i Zimmermann.<ref>{{ref-llibre|autor = Stehlé D, Zimmermann P |any = 2005 |capítol = Gal's accurate tables method revisited |títol = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) |editorial = [[IEEE Computer Society Press]] |lloc = Los Alamitos, Ca}}</ref> Aquests algorismes exploten la forma de matriu de 2×2 de l'algorisme euclidià donat [[#Mètode matricial|més amunt]]. Aquests mètodes subquadràtics generalment tenen una complexitat de {{nowrap|''O''(''h'' (log ''h'')² (log log ''h'')).}}<ref name="Crandall_2001"/><ref>{{ref-publicació | autor = Möller N | url = http://www.lysator.liu.se/~nisse/archive/sMCD.pdf | article = On Schönhage's algorithm and subquadratic integer MCD computation | publicació = Mathematics of Computation | volum = 77 | pàgines = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | any = 2008}}{{Enllaç no actiu|bot=InternetArchiveBot |data=2022}}</ref>

== Altres sistemes de nombres ==
Com descrit a dalt, l'algorisme euclidià s'utilitza per trobar el màxim comú divisor de dos nombres naturals (enters positius). Tanmateix, es pot generalitzar als nombres reals, i a més sistemes de nombre exòtics com [[polinomi]]s, [[enters quadràtics]] i [[quaternions de Hurwitz]]. En els últims casos, l'algorisme euclidià s'utilitza per demostrar la propietat fonamental que la factorització és única, és a dir, que tals nombres es poden factoritzar de forma única en [[elements irreductibles]], els homòlegs dels nombres primers. La factorització única és essencial per moltes demostracions de teoria de nombres.

=== Nombres racionals i reals ===
L'algorisme d'Euclides es pot aplicar a [[nombre real|nombres reals]], com va descriure Euclides al Llibre 10 del seu ''[[Elements d'Euclides|Elements]]''. L'objectiu de l'algorisme és identificar un nombre real ''g'' tal que donats dos nombres reals, ''a'' i ''b'', són múltiples enters d'aquest: ''a'' = ''mg'' i ''b'' = ''ng'', on ''m'' i ''n'' són [[nombre enter|enters]].<ref name="Weil_1983"/> Aquesta identificació és equivalent a trobar una [[relació entera]] entre els nombres reals ''a'' i ''b''; és a dir, determinar enters ''s'' i ''t'' tals que ''sa'' + ''tb'' = 0. Euclides utilitza aquest algorisme per tractar la qüestió de [[longituds incommensurables]].<ref>{{ref-llibre|cognom = Boyer |nom= CB|enllaçautor=Carl Boyer|cognom2=Merzbach|nom2=UC |any = 1991 |títol = A History of Mathematics |edició =2a ed.|editorial = Wiley |lloc = Nova York|isbn = 0-471-54397-7 |pàgines = 116–117}}</ref><ref>. {{ref-llibre|autor = [[Florian Cajori|Cajori F]] |any = 1894 |títol = A History of Mathematics |editorial = Macmillan |lloc = Nova York|pàgines = 70}}</ref>

L'algorisme euclidià per nombres reals difereix del seu homòleg d'enters en dos aspectes. Primer, els residus ''r''<sub>''k''</sub> són nombres reals, encara que els quocients ''q''<sub>''k''</sub> són enters com abans. Segon, no està garantit que l'algorisme acabi en un nombre finit ''N'' de passos. Si ho fa, la fracció ''a''/''b'' és un nombre racional, és a dir, la raó de dos enters

: ''a''/''b'' = ''mg''/''ng'' = ''m''/''n''

i es pot escriure com a fracció contínua finita <math>[q_0;q_1,q_2,...,q_N]</math>. Si l'algorisme no s'atura, la fracció ''a'' /''b'' és un [[nombre irracional]] i es pot descriure per una fracció contínua infinita <math>[q_0;q_1,q_2,...]</math>. Exemples de fraccions contínues infinites són la [[secció àuria]] ''φ'' = [1; 1, 1, …] i l'[[arrel quadrada de dos]], √2 = [1; 2, 2, …]. En general, és improbable que l'algorisme s'aturi, ja que [[Quasi pertot|gairebé tots]] els casos ''a'' /''b'' de dos nombres reals són irracionals.

Una fracció contínua infinita es pot truncar en un pas <math>k [q_0;q_1,q_2,...,q_k]</math> per obtenir una aproximació a ''a''/''b'' que millora a mesura que ''k'' creix. L'aproximació es descriu per ''m''<sub>''k''</sub>/''n''<sub>''k''</sub>; els numeradors i els denominadors són coprimers i obeeixen la recurrència

:<math>m_k=q_k\ m_{k-1}+m_{k-2}</math>
:<math>n_k=q_k\ n_{k-1}+n_{k-2}</math>

on ''m''<sub>−1</sub> = ''n''<sub>−2</sub> = 1 i ''m''<sub>−2</sub> = ''n''<sub>−1</sub> = 0 són els valors inicials de la recurrència. La successió ''m''<sub>''k''</sub>/''n''<sub>''k''</sub> és la millor aproximació d'un [[nombre racional]] a ''a''/''b'' amb el denominador ''n''<sub>''k''</sub>:

:<math alt="El valor absolut de la diferència de dues proporcions (a partit per b menys m sub k partit per n sub k) és més petit que un partit per n sub k al quadrat.">
\left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.
</math>

=== Polinomis ===
Els polinomis d'una única variable ''x'' es poden sumar, multiplicar i factoritzar en [[factorització dels polinomis|polinomis irreductibles]], que són els anàlegs als nombres primers per a enters. El polinomi màxim comú divisor ''g''(''x'') de dos polinomis ''a''(''x'') i ''b''(''x'') es defineix com el producte dels seus polinomis irreductibles compartits, que es poden identificar utilitzant l'algorisme euclidià.<ref name="Lang_1984" >{{ref-llibre|autor = [[Serge Lang|Lang S]] |any = 1984 |títol = Algebra |edició =2a ed.|editorial = Addison–Wesley |lloc = Menlo de localitzacions, Ca|isbn = 0-201-05487-6 |pàgines = 190–194}}</ref> El procediment bàsic és similar al cas dels enters. A cada pas ''k'', es troben un polinomi quocient ''q''<sub>''k''</sub>(''x'') i un polinomi de residu ''r''<sub>''k''</sub>(''x'') que satisfan l'equació recursiva

: <math>r_{k-2}(x)=q_k(x)\ r_{k-1}(x)+r_k(x)</math>

on ''r''<sub>−2</sub>(''x'') = ''a'' (''x'') i ''r''<sub>−1</sub>(''x'') = ''b'' (''x''). El polinomi de quocient s'escull de forma que el terme principal de ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k'' −1</sub>(''x'') sigui igual al terme principal de ''r''<sub>''k'' −2</sub>(''x''); això assegura que el grau de cada residu sigui més petit que el grau del seu predecessor deg[''r''<sub>''k''</sub>(''x'')] < deg[''r''<sub>''k'' −1</sub>(''x'')]. Com que el grau és un enter no negatiu, i com que disminueix a tots els passos, l'algorisme euclidià acaba en un nombre finit de passos. El residu diferent de zero final és el màxim comú divisor dels dos polinomis originals, ''a''(''x'') i ''b''(''x'').<ref>Cox, pàg. 37-46.</ref>

Per exemple, considerant els següents dos polinomis quàrtics, que cada un es factoriza en dos [[Polinomi quadràtic|polinomis quadràtics]]

: <math>a(x)=x^4-4x^3+4x^2-3x+14=(x^2-5x+7)(x^2+x+2)</math>

i

: <math>b(x)=x^4+8x^3+12x^2+17x+6=(x^2+7x+3)(x^2+x+2)</math>.

Dividint ''a''(''x'') entre ''b''(''x'') dona una residu ''r''<sub>0</sub>(''x'') = ''x''<sup>3</sup> + (2/3)''x''² + (5/3)''x'' − (2/3). Al següent pas ''b''(''x'') es divideix entre ''r''<sub>0</sub>(''x'') donant un residu ''r''<sub>1</sub>(''x'') = ''x''² + ''x'' + 2. Finalment, dividint ''r''<sub>0</sub>(''x'') entre ''r''<sub>1</sub>(''x'') dona un zero de residu, el que indica que ''r''<sub>1</sub>(''x'') és el polinomi màxim comú divisor de ''a''(''x'') i ''b''(''x''), coherent amb la seva factorització.

Moltes de les aplicacions descrites a dalt per a enters s'apliquen a polinomis.<ref>Schroeder, pàg. 254-259.</ref> L'algorisme euclidià es pot fer servir per resoldre equacions diofàntiques lineals i problemes de residus xinesos per a polinomis; també es poden definir fraccions contínues de polinomis.

L'algorisme euclidià polinòmic també té altres aplicacions, com el [[Teorema de Sturm]], un mètode per comptar el nombre d'arrels reals d'un polinomi dins d'un interval donat de l'eix real. Això té aplicacions en unes quantes àrees, com el [[Criteri d'estabilitat de Routh-Hurwitz]] en [[teoria del control]].

Finalment, els coeficients dels polinomis no cal que siguin enters, nombres reals o ni tan sols nombres complexos. Per exemple, els coeficients poden pertànyer a un cos general, com els cossos finits GF(''p'') descrits més amunt. Les conclusions corresponents sobre l'algorisme euclidià i les seves aplicacions es mantenen fins i tot per aquesta mena de polinomis.<ref name="Lang_1984"/>

==== Exemple d'aplicació a trobar arrels múltiples ====
Siga <math> P=X^3-6X^2-63X+392 \quad </math> un polinomi que té una arrel doble.

Com que resoldre una [[equació de tercer grau]] no és evident, per a trobar l'arrel múltiple emprem la propietat que diu les arrels múltiples són les comunes entre el polinomi i el seu polinomi [[funció derivada|derivat]].

Per a simplificar les divisions, ens permetem multiplicar-los per factors constants no nuls. Això no suposa cap pèrdua de generalitat, ja que el ''mcd'' de dos polinomis està definit mòdul un factor multiplicador, de manera que esta manipulació no altera el resultat.

El polinomi derivat de P és <math> P' = 3X^2 - 12X - 63 \quad </math> que es pot simplificar per 3, segons el que s'ha dit anteriorment.

Prenguem llavors <math> Q = \frac {P'} 3 = X^2 - 4X - 21</math> i efectuem l'algorisme amb P i Q.

<math>P = (X-2)Q -50X + 350 \quad </math>. La resta es factoritza en <math>\quad -50(X - 7) </math>: prenguem llavors <math>\quad R = X - 7 </math>

<math>Q = (X+3)R + 0 \quad </math> el que implica que el '''mcd''' buscat és <math>X-7 \quad </math> llavors '''7''' és l'arrel doble de '''P'''.

En efecte: <math> P = (X - 7)^2(X + 8) \quad</math> i addicionalment <math> P' = 3(X - 7)(X + 3) \quad</math>

=== Enters de Gauss ===
[[Fitxer:Gaussian primes.svg|miniatura|alt="Un conjunt de punts que són dins d'una circumferència. El patró dels punts té simetria quàdruple, és a dir, les rotacions de 90 graus deixen inalterat el dibuix. El dibuix també es pot reflectir sobre quatre línies que passen a través del centre del cercle: els eixos verticals i horitzontals, i les dues línies diagonals a ±45 graus."|Distribució de nombres primers de Gauss ''u'' + ''vi'' al pla complex, amb normes ''u''² + ''v''² menors de 500]]

Els [[enters de Gauss]] són [[nombre complex|nombres complexos]] de la forma α = ''u'' + ''vi'', on ''u'' i ''v'' són [[nombre enter|enters]] ordinaris i ''i'' és la [[unitat imaginària]].<ref name="Stillwell_2003"/> Definint un anàleg de l'algorisme euclidià, es pot demostrar que els enters gaussians són factoritzables de forma única, per la [[Identitat de Bézout]].<ref name="Gauss_1832">{{ref-publicació|enllaçautor = Carl Friedrich Gauss |autor=Gauss CF | data = 1832 | article = Theoria residuorum biquadraticorum | publicació = Comm. Soc. Reg. Sci. Gött. Rec. | volum = 4}} Vegeu també ''Werke'', '''2''':67-148.</ref> Aquesta factorització única és útil en moltes aplicacions, com trobar totes les [[Terna pitagòrica|ternes pitagòriques]] o en la demostració del [[teorema de la suma de dos quadrats]].<ref name="Stillwell_2003">{{ref-llibre|autor = [[John Stillwell|Stillwell J]] |any = 2003 |títol = Elements of Number Theory |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-95587-9 |pàgines = 101–116}}</ref> En general, l'algorisme euclidià és convenient en tals aplicacions, però no essencial; per exemple, els teoremes sovint es poden demostrar amb altres arguments.

L'algorisme euclidià desenvolupat per a dos enters gaussians α i β és gairebé el mateix que per a enters normals, però difereix en dos aspectes. Com abans, la tasca a cada pas ''k'' és identificar un quocient ''q''<sub>''k''</sub> i una residu ''r''<sub>''k''</sub> tals que

: <math>r_k=r_{k-2}-q_k\ r_{k-1}</math>

on ''r''<sub>''k'' −2</sub> = α, ''r''<sub>''k'' −1</sub> = β, i tots els residus són estrictament més petits que els seus predecessors, |''r''<sub>''k''</sub>| < |''r''<sub>''k'' −1</sub>|. La primera diferència és que els quocients i residus són ells mateixos enters gaussians, i així són [[nombre complex|nombres complexos]]. Els quocients ''q''<sub>''k''</sub> es troben en general arrodonint les parts real i complexa del quocient exacte (com el nombre complex α/β) als enters més propers. La segona diferència és la necessitat de definir com pot ser un residu complex "més petit" que un altre. Per fer això, es defineix una [[norma (matemàtiques)|funció norma]] ''f'' (''u'' + ''v'' i) = ''u''² + ''v''², que converteix cada enter gaussià ''u'' + ''vi'' a un enter normal. Després de cada pas ''k'' de l'algorisme euclidià, la norma del residu ''f'' (''r''<sub>''k''</sub>) és més petita que la norma del residu anterior, ''f''(''r''<sub>''k'' −1</sub>). Ja que la norma és un enter no negatiu i disminueix amb tots els passos, l'algorisme euclidià per a enters gaussians acaba en un nombre finit de passos. La resta diferent de zero final és el MCD(α,β), l'enter gaussià de norma més gran que divideixi els dos α i β; és únic tret d'una multiplicació per una unitat, ±1 o ±''i''.

Moltes de les altres aplicacions de l'algorisme euclidià es passen als enters gaussians. Per exemple, es pot utilitzar per resoldre equacions diofàntiques lineals i problemes de residus xinesos per a enters gaussians; també es poden definir fraccions contínues d'enters gaussians.

=== Dominis euclidians ===
Un conjunt d'elements amb dues [[operació binària|operacions binàries]], + i ·, s'anomenen un [[anell euclidià]] si forma un [[anell commutatiu]] ''R'' i, a grans trets, si s'hi pot aplicar un algorisme euclidià generalitzat.<ref>Stark, pàg. 290.</ref><ref>. Cohn, pàg. 104-105.</ref> Les dues operacions de tal anell no necessiten ser l'addició i multiplicació de l'aritmètica corrent; poden ser, més aviat, més generals, com les operacions d'un [[grup (matemàtiques)|grup matemàtic]] o [[monoide]]. No obstant això, aquestes operacions generals han de respectar moltes de les lleis que governen l'aritmètica corrent, com la [[propietat commutativa]], la [[propietat associativa]] i la [[propietat distributiva]].

L'algorisme euclidià generalitzat requereix una ''funció euclidiana'', és a dir, una funció ''f'' de ''R'' al conjunt d'enters no negatius tal que, per a dos elements diferents de zero qualssevol ''a'' i ''b'' en ''R'', existeix ''q'' i ''r'' en ''R'' tals que ''a'' = ''qb'' + ''r'' i ''f''(''r'') < ''f''(''b''). Un exemple d'aquesta funció és la funció norma utilitzada amb els [[Enter de Gauss|entersde Gauss]] a la secció anterior. La funció ''f'' pot ser la magnitud del nombre, o el [[grau d'un polinomi]]. El principi bàsic és que es redueix a cada pas de l'algorisme; per això, si ''f'' es pot reduir només un nombre finit de vegades, l'algorisme s'ha d'aturar en un nombre finit de passos. Aquest principi depèn fortament de l'ordre natural dels enters no negatius; a grans trets, això exigeix que tots els conjunts d'enters no negatius tinguin un membre més petit que tots els altres.

El [[teorema fonamental de l'aritmètica]] s'aplica a qualsevol anell euclidià: Qualsevol nombre d'un anell euclidià es pot factoritzar de manera única amb [[elements irreductibles]]. Qualsevol anell euclidià és un [[domini de factorització única]] (UFD), encara que el contrari no és cert. Els anells euclidians són una subclasse dels [[anells de MCD]], anells en els quals sempre existeix un màxim comú divisor de dos nombres. En altres paraules, un màxim comú divisor pot existir (per a tots els elements en un anell), encara que pot no ser possible trobar-lo utilitzant un algorisme euclidià. Un anell euclidià és sempre un [[anell d'ideals principals]], un [[anell íntegre]] en el qual tots els [[ideal (matemàtiques)|ideals]] són un [[ideal principal]]. Una altra vegada, el contrari no és cert: no tots els anells ideal principal són un anell euclidià.

La factorització única d'anells euclidians és útil en moltes aplicacions. Per exemple, la factorització única dels enters gaussians és convenient permetent obtenir fórmules per totes les [[Terna pitagòrica|ternes pitagòriques]] i demostrar el [[teorema de la suma de dos quadrats]].<ref name="Stillwell_2003"/> La factorització única era també un element clau en un intent de demostració del [[darrer teorema de Fermat]] publicat el 1847 per Gabriel Lamé, el mateix matemàtic que analitzava l'eficiència de l'algorisme d'Euclides, basat en un suggeriment de [[Joseph Liouville]].<ref>{{ref-publicació|autor = Lamé G | any = 1847 | article = Mémoire sur la résolution, en nombres complexes, de l'équation A<sup>n</sup> + B<sup>n</sup> + C<sup>n</sup> = 0 | publicació = J. Math. Pures Appl. | volum = 12 | pàgines = 172–184}}</ref> l'aproximació de Lamé exigia la factorització única de nombres de la forma ''x'' + ω''y'', on ''x'' i ''y'' són enters, i ω = ''e''<sup>2''i'' π/''n''</sup> és una ''n'' arrel d'1, és a dir ω<sup>''n''</sup> = 1. Encara que aquesta aproximació té èxit per a alguns valors de ''n'' (com ''n'' =3, els [[Enter d'Eisenstein|Enters d'Eisenstein)]], en general tals nombres ''no'' es factoritzen únicament. Aquest fracàs de factorització única en alguns [[anells ciclotòmics]] portava [[Ernst Kummer]] al concepte de [[nombre ideal|nombres ideals]] i, més tard, a [[Richard Dedekind]] al d'[[ideal (matemàtiques)|ideals]].<ref>{{en}} Leo Corry, ''[http://books.google.cat/books?id=WdGbeyehoCoC&pg=PA81&dq=euclid+Dedekind+ideal&hl=ca&ei=_UpFTeT0Lcnysgap78m9Dg&sa=X&oi=book_result&ct=result&resnum=3&ved=0CDAQ6AEwAg#v=onepage&q=euclid%20Dedekind%20ideal&f=false Modern algebra and the rise of mathematical structures]'', p.81</ref>

==== Factorització única d'enters quadràtics ====
[[Fitxer:Eisenstein primes.svg|miniatura|alt="Un conjunt de punts que són dins d'una circumferència. El dibuix de punts té simetria tal que les rotacions de 60 graus deixen inalterat el dibuix. El dibuix també es pot reflectir sobre sis línies que passen a través del centre de la circumferència: els eixos verticals i horitzontals, i les quatre línies diagonals a ±30 i ±60 graus."|Distribució de nombres primers d'Eisenstein ''u'' + ''v''ω al pla complex, amb normes menors de 500. El nombre ω és igual a l'[[arrels de la unitat|arrel cúbica de 1]].]]

Els [[anell d'enters quadràtics|anells d'enters quadràtics]] són útils per il·lustrar anells euclidians. Els enters quadràtics són generalizations dels enters gaussians en què la [[unitat imaginària]] ''i'' és reemplaçada per un nombre ω. Així, tenen la forma ''u'' + ''v'' ω, on ''u'' i ''v'' són enters i ω té una de dues formes, depenent d'un paràmetre ''D''. Si ''D'' no és igual a un múltiple de quatre més un, llavors

: ω = √D.

Tanmateix, si ''D'' és igual a un múltiple de quatre més u, llavors

: ω = (1 + √D)/2.

Si la funció ''f'' correspon a una funció norma, tal com l'emprada per ordenar els [[Enters de Gauss]] més amunt, llavors l'anell es coneix com normat amb una ''norma euclidiana''. Els anells amb norma euclidiana d'enters quadràtics són exactament aquells on ''D'' = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 o 73.<ref name="Cohn_1962"/> Els enters quadràtics amb ''D'' = −1 i −3 es coneixen com els [[Enter de Gauss|Enters gaussians]] i [[Enter d'Eisenstein|enters d'Eisenstein]], respectivament.

Si és permet que ''f'' sigui qualsevol funció euclidiana, llavors la llista de possibles valors ''D'' per als quals l'anell és euclidià encara no es coneix.<ref name="Clark_1994">{{ref-publicació | autor = Clark DA | any = 1994 | url = http://www.springerlink.com/content/6t9u2440402n1346/ | article = A quadratic field which is Euclidean but not norm-Euclidean | publicació = Manuscripta mathematica | volum = 83 | pàgines = 327–330 | doi = 10.1007/BF02567617}}{{Enllaç no actiu|bot=InternetArchiveBot |data=2021}}</ref> El primer exemple d'un anell euclidià que no era de norma euclidiana (amb ''D'' =69) era publicat el 1994.<ref name="Clark_1994"/> El 1973, Weinberger demostrava que un anell d'enters quadràtics amb ''D'' > 0 és euclidià si, i només si, és un [[anell d'ideals principals]], a condició que es compleixi la [[hipòtesi de Riemann generalitzada]].<ref>{{ref-publicació|autor = Weinberger P | article = On Euclidean rings of algebraic integers | publicació = Proc. Sympos. Pure Math. | volum = 24 | pàgines = 321–332}}</ref>

=== Anells no commutatius ===
També és possible aplicar l'algorisme euclidià a anells no commutatius com el conjunt de [[quaternions de Hurwitz]].<ref>{{ref-llibre|autor = [[John Stillwell|Stillwell J]] |any = 2003 |títol = Elements of Number Theory |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-95587-9 |pàgines = 151–152}}</ref> Siguin α i β dos elements de tal anell. Tenen un comú bé divisor δ si α = ξδ i β = ηδ per a alguna elecció de ξ i η a l'anell. De manera similar, tenen un divisor per l'esquerra comú si α = δξ i β = δη per a alguna elecció de ξ i η a l'anell. com que la multiplicació no és commutativa, hi ha dues versions de l'algorisme euclidià, una per a divisors per la dreta i una per a divisors per l'esquerra. Escollint els divisors per la dreta, el primer pas per trobar el MCD(α, β) amb l'algorisme euclidià es pot escriure

: ρ<sub>0</sub> = α − ψ<sub>0</sub>β = (ξ − ψ<sub>0</sub>η)δ

on ψ<sub>0</sub> representa el quocient i ρ<sub>0</sub> el residu. Aquesta equació mostra que qualsevol divisor comú de α i β és de la mateixa manera un comú divisor del residu ρ<sub>0</sub>. L'equació anàloga per als divisors per l'esquerra seria

: ρ<sub>0</sub> = α − βψ<sub>0</sub> = δ(ξ − ηψ<sub>0</sub>)

Amb qualsevol elecció, el procés es repeteix com a dalt fins que el màxim comú divisor per la dreta o per l'esquerra s'identifiqui. Com en l'anell euclidià, la "mida" del residu ρ<sub>0</sub> ha de ser estrictament més petita que β, i hi ha d'haver només un nombre finit de mides possibles per a ρ<sub>0</sub>, de manera que es garanteixi que l'algorisme s'acaba.

La majoria dels resultats per al MCD passen a nombres no commutatius. Per exemple, la [[identitat de Bézout]] estableix que el MCD(α, β) per la dreta es pot expressar com a combinació lineal de α i β. En altres paraules, hi ha nombres σ i τ tals que

: Γ<sub>dreta</sub> = σα + τβ

La identitat anàloga per al MCD per l'esquerra és gairebé la mateixa

: Γ<sub>esquerra</sub> = ασ + βτ

La identitat de Bézout es pot fer servir per resoldre equacions diofàntiques.

== Generalitzacions a altres estructures matemàtiques ==
[[Fitxer:TorusKnot3D.png|miniatura|alt="Un cordó enrotllat set vegades al voltant d'un torus i reconnectat al seu començament, formant un bucle tancat. En el procés, el cordó completa tres circuits del torus, conformant un (3, 7) nus de torus."|L'algorisme euclidià es pot aplicar en la [[teoria de nusos]].<ref>{{citar ref |autor = Yamada Y | any = 2007 | arxiv = 0708.2316v1 |article=Generalized rational blow-down, torus knots, and Euclidean algorithm}}</ref>]]

L'algorisme euclidià té tres trets generals que junts asseguren que no continuarà indefinidament. Primer, es pot escriure com a seqüència d'equacions recursives

: <math>r_k=r_{k-2}-q_k\ r_{k-1}</math>

on cada residu és estrictament més petit que el seu predecessor, |''r''<sub>''k''</sub>| < |''r''<sub>''k'' −1</sub>|. Segon, la mida de cada residu té un límit inferior estricte, com |''r''<sub>''k''</sub>| ≥ 0. Tercer, hi ha només un nombre finit de mides més petites que un residu donat |''r''<sub>''k''</sub>|. Les generalitzacions de l'algorisme d'Euclides amb aquests trets bàsics s'han aplicat a altres estructures matemàtiques, com [[Teoria de nusos|nusos]]<ref>{{ref-llibre|nom = John Horton|cognom = Conway|enllaçautor = John Horton Conway|capítol = An enumeration of knots and links, and some of their algebraic properties|editorial = Pergamon|any = 1970|pàgines = 329–358|títol = Computational Problems in Abstract Algebra |lloc=Oxford|data= 1967)}}</ref> i a [[nombre ordinal|nombres ordinals]] [[nombre transfinit|transfinits]].<ref>{{citar ref |autor = Jategaonkar AV | any = 1969 | url = http://projecteuclid.org/euclid.bams/1183530557 |article =Rings with transfinite left division algorithm | publicació = Bull. Amer. Math. Soc. | volum = 75 | pàgines = 559–561 | doi = 10.1090/S0002-9904-1969-12242-1}}</ref>

Una generalització important de l'algorisme euclidià és el concepte d'una [[base de Gröbner]] en [[geometria algebraica]]. Com s'ha mostrat més amunt, el MCD ''g'' de dos enters ''a'' i ''b'' és el generador del seu [[ideal (matemàtiques)|ideal]]. En altres paraules, per a qualsevol elecció dels enters ''s'' i ''t'', hi ha un altre enter ''m'' tal que

: <math>sa+tb=mg</math>.

Encara que això roman cert quan ''s'', ''t'', ''m'', ''a'' i ''b'' representen polinomis d'una única variable, ''no'' és cert per a anells de més d'una variable.<ref>Cox, pàg. 65.</ref> En aquest cas, es pot definir un conjunt finit de polinomis generadors ''g''<sub>1</sub>, ''g''₂, etc. tal que qualsevol combinació lineal de dos polinomis multivariables ''a'' i ''b'' pot ser expressat com múltiples dels generadors

: <math>sa+tb=\Sigma_k\ m_k\ g_k</math>

on ''s'', ''t'' i ''m''<sub>''k''</sub> són polinomis multivariables.<ref>Cox, pàg. 73-79.</ref> Qualsevol polinomi multivariable ''f'' es pot expressar com tal suma de polinomis generadors més un polinomi residu únic ''r'', a vegades anomenat la ''forma normal'' del polinomi ''f''

: <math>f=r+\Sigma_k\ q_k\ g_k</math>

encara que els polinomis quocient ''q''<sub>''k''</sub> poden no ser únics.<ref>Cox, pàg. 79-86.</ref> El conjunt d'aquests polinomis generadors es coneix com a ''base de Gröbner''.<ref>Cox, pàg. 74.</ref>

== Notes ==
{{refbegin}}
* '''a.''' {{Note_label|a|a|none}} Alguns llibres de text àmpliament utilitzats, com [[I. N. Herstein]] ''Topics in Algebra'' i [[Serge Lang]] ''Algebra'', fan servir el terme "Algorisme euclidià" per referir-se a la [[divisió euclidiana|algorisme de divisió amb residu]]. Tanmateix, l'algorisme de divisió és un teorema, no un algorisme.
{{refend}}

== Referències ==
{{Referències}}

== Bibliografia ==
* {{ref-llibre|autor = Cohen H. |any = 1993 |títol = A Course in Computational Algebraic Number Theory |url = http://books.google.cat/books?id=hXGr-9l1DXcC |editorial = Springer-Verlag |lloc = Nova York|isbn = 0-387-55640-0}}
* {{ref-llibre|autor = Cohn H |any = 1962 |títol = Advanced Number Theory |url = http://books.google.cat/books?id=yMGeElJ8M0wC |editorial = Dover |lloc = Nova York|isbn = 0-486-64023-X}}
* {{ref-llibre|autor = [[Thomas H. Cormen|Cormen TH]], [[Charles E. Leiserson|Leiserson CE]], [[Ronald L. Rivest|Rivest RL]], [[Clifford Stein|Stein C]] |any = 2001|títol = Introduction to Algorithms |url = http://books.google.cat/books?id=NLngYyWFl_YC |edició =2a ed.|editorial = MIT Press and McGraw–Hill|isbn = 0262032937}}
* {{ref-llibre|autor = Cox D, Little J, and O'Shea D |any = 1997 |títol = Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra |url = http://books.google.cat/books?id=7eLkq0wQytAC |edició =2a ed.|editorial = Springer-Verlag |isbn = 0-387-94680-2}}
* {{ref-llibre|autor = [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet PGL]]|any = 1894 |títol = Vorlesungen über Zahlentheorie|editor = [[Richard Dedekind]]|editorial = Vieweg|lloc = Braunschweig}}
* {{ref-llibre|autor = [[G. H. Hardy|Hardy GH]], [[E. M. Wright|Wright EM]] [revised by D.R. Heath-Brown and J.H. Silverman]. |data = 2008|url = http://books.google.cat/books?id=rey9wfSaJ9EC |títol = An Introduction to the Theory of Numbers|edició =6a ed.|editorial = Clarendon Press|lloc = Oxford}}
* {{ref-llibre|autor = [[Donald Knuth|Knuth D]]|any = 1997|títol = [[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms|edició =3a ed.|editorial = Addison–Wesley|isbn = 0201896842}}
* {{ref-llibre|autor = [[William J. LeVeque|LeVeque WJ]] |any = 1977 |títol = Fundamentals of Number Theory |editorial = Dover |lloc = Nova York|isbn = 0-486-68906-9}}
* {{ref-llibre|autor = Mollin RA |any = 2008 |títol = Fundamental Number Theory with Applications |edició =2a ed.|editorial = Chapman & Hall/CRC|lloc = Boca Raton|isbn = 9781420066593}}
* {{ref-llibre|autor = [[Øystein Ore|Ore Ø]] |data = 1948 |títol = Number Theory and Its History |editorial = McGraw–Hill |lloc = Nova York}}
* {{ref-llibre|autor = Rosen KH |any = 2000 |títol = Elementary Number Theory and its Applications |edició =4a ed.|editorial = Addison–Wesley |lloc = Reading, Ma|isbn = 0201870738}}
* {{ref-llibre|autor = [[Manfred R. Schroeder|Schroeder MR]] |any = 2005 |títol = Number Theory in Science and Communication |edició =4a ed.|editorial = Springer-Verlag|isbn = 0387158006}}
* {{ref-publicació|nom=Jeffrey|cognom=Shallit|article=Origins of the analysis of the Euclidean algorithm|url=http://www.sciencedirect.com/science/article/pii/S0315086084710317|publicació=Historia Mathematica|volum=Vol 21|exemplar=Num 4|any=1994|pàgines=401-419|doi=10.1006/hmat.1994.1031|issn=0315-0860}}
* {{ref-llibre|autor = [[Harold Stark|Stark H]] |any = 1978 |títol = An Introduction to Number Theory |editorial = MIT Press |isbn = 0-262-69060-8}}
* {{ref-llibre|autor = [[John Stillwell|Stillwell J]] |any = 1997 |títol = Numbers and Geometry |editorial = Springer-Verlag |lloc = d'editor localització = Nova York|isbn = 0-387-98289-2}}
* {{ref-llibre|autor = Tattersall JJ |any = 2005 |títol = Elementary number theory in nine chapters |editorial = [[Cambridge University Press]] |lloc = Cambridge|isbn = 9780521850148}}
* {{ref-llibre|autor = Uspensky JV, Heaslet MA |any = 1939 |títol = Elementary Number Theory |editorial = McGraw–Hill |lloc = Nova York}}

== Enllaços externs ==
{{Commonscat}}
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Demostracions de l'algorisme d'Euclides]. David Sumner
* [http://www.cut-the-knot.org/blue/Euclid.shtml l'Algorisme d'Euclides] a [[cut-the-knot]]
* {{MathWorld | urlname=EuclideanAlgorithm | title=Euclidean Algorithm}}

{{Autoritat}}

{{ORDENA:Algorisme D'Euclides}}
[[Categoria:Teoria de nombres]]
[[Categoria:Algorismes|Euclides]]