Vizualizare sursă pentru „Algoritmul lui Euclid”

[[Fișier:Euclidean algorithm 252 105 animation flipped.gif|thumb|Animație ce prezintă algoritmul lui Euclid pentru numerele 252 și 105. Barele reprezintă unitățile de 21, cel mai mare divizor comun (CMMDC). La fiecare pas, numărul mai mic este scăzut din cel mai mare, până când unul dintre numere ajunge să fie zero. Celălalt este CMMDC.]]

În [[matematică]], '''algoritmul lui Euclid''' este o metodă eficientă de calcul al [[Cel mai mare divizor comun|celui mai mare divizor comun]] (CMMDC). El este denumit după matematicianul grec [[Euclid]], care l-a descris în Cărțile&nbsp;VII și X din ''[[Elementele]]''.<ref>[[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref>

CMMDC a două numere este cel mai mare număr care le [[divizor|divide]] pe ambele. Algoritmul lui Euclid exploatează observația că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare. De exemplu, 21 este CMMDC al numerelor 252 și 105 (252&nbsp;=&nbsp;21&nbsp;×&nbsp;12; 105&nbsp;=&nbsp;21&nbsp;×&nbsp;5); întrucât 252&nbsp;−&nbsp;105&nbsp;=&nbsp;147, CMMDC al lui 147 și 105 este tot 21. Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul. Inversând pașii algoritmului lui Euclid, CMMDC se poate exprima sub formă de [[Combinație liniară|suma]] celor două numere inițiale, fiecare înmulțite cu un întreg pozitiv sau negativ, de exemplu: {{nowrap begin}}21 = 5 × 105 + (−2) × 252.{{nowrap end}} Această proprietate importantă se numește [[identitatea lui Bézout]].

Prima descriere rămasă a algoritmului lui Euclid este lucrarea lui Euclid intitulată ''Elementele'' (c. 300 î.e.n.), fiind unul dintre cei mai vechi algoritmi numerici încă utilizați. Algoritmul original a fost descris doar pentru numere naturale și lungimi geometrice (numere reale), dar algoritmul a fost generalizat în secolul al XIX-lea și la alte tipuri de numere, cum ar fi [[întregii gaussieni]] și [[Polinom|polinoamele]] de o variabilă. Aceasta a dus la noțiuni moderne de [[algebră abstractă]], cum ar fi [[Inel euclidian|inelele euclidiene]]. Algoritmul lui Euclid s-a generalizat și pentru alte structuri matematice, cum ar fi [[Nod (matematică)|nodurile]] și polinoamele multivariabilă.

Algoritmul lui Euclid are numeroase aplicații practice și teoretice. Este un element cheie al algoritmului [[RSA]], o metodă de [[criptare cu chei publice]] des folosită în comerțul electronic. Este utilizat pentru a rezolva [[Ecuație diofantică|ecuațiile diofantice]], cum ar fi calcularea numerelor care satisfac mai multe congruențe ([[Teorema chinezească a resturilor]]) sau inversul multiplicativ al unui [[corp (matematică)|corp]]. Algoritmul lui Euclid poate fi utilizat pentru a construi [[Fracție continuă|fracții continue]], în metoda [[Lanț Sturm|lanțului Sturm]] pentru găsirea rădăcinilor reale ale unui polinom, și în mai mulți algoritmi moderni de [[Factorizarea întregilor|factorizare a întregilor]]. Este utilizat și la demonstrarea unor teoreme din [[Teoria numerelor|teoria modernă a numerelor]], cum ar fi [[teorema celor patru pătrate a lui Lagrange]] și [[teorema fundamentală a aritmeticii]] (factorizarea unică).

Algoritmul lui Euclid calculează eficient CMMDC a două numere oricât de mari sunt, deoarece nu necesită niciodată un număr de pași mai mare decât de cinci ori numărul de cifre (în bază 10) al celui mai mic întreg. [[Gabriel Lamé]] a demonstrat aceasta în 1844, marcând începutul [[Teoria complexității|teoriei complexității computaționale]]. În secolul al XX-lea s-au dezvoltat metode de îmbunătățire ale eficienței algoritmului.

== Noțiuni implicate ==
=== Cel mai mare divizor comun ===
Algoritmul lui Euclid calculează cel mai mare divizor comun (CMMDC) a două [[Număr natural|numere naturale]] ''a'' și ''b''. Cel mai mare divizor comun ''g'' este cel mai mare număr natural care îi divide pe ''a'' și pe ''b''. Cel mai mare divizor comun este adesea scris ca CMMDC(''a'',&nbsp;''b'') sau, mai simplu, ca (''a'',&nbsp;''b''),<ref>Stark, p. 16.</ref> deși a doua [[notație matematică]] este utilizată și pentru alte concepte matematice, cum ar fi vectorii bidimensionali sau intervalele deschise.

Dacă CMMDC(''a'',&nbsp;''b'')&nbsp;=&nbsp;1, atunci ''a'' și ''b'' sunt [[prime între ele]].<ref>Stark, p. 21.</ref> Această proprietate nu depinde de [[Numere prime|primalitatea]] lui ''a'' și a lui ''b''.<ref>LeVeque, p. 32.</ref> De exemplu, numerele 6 și 35 nu sunt numere prime, deoarece ambele au doi factori: 6&nbsp;=&nbsp;2&nbsp;×&nbsp;3 și 35&nbsp;=&nbsp;5&nbsp;×&nbsp;7. Cu toate acestea, 6 și 35 sunt prime între ele. Niciun alt număr natural în afară de 1 nu divide și pe 6 și pe 35, deoarece ele nu au niciun factor prim în comun.

[[Fișier:Square tiling 24x60.svg|thumb|Un dreptunghi 24-pe-60 acoperit cu zece pătrate 12-pe-12, în care 12 este CMMDC al numerelor 24 și 60. Mai general, un dreptunghi de ''a''-pe-''b'' poate fi acoperit din pătrate cu latura de ''c'' doar dacă ''c'' este divizor comun al lui ''a'' și ''b''.]]

Fie ''g'' = CMMDC(''a'',&nbsp;''b''). Cum ''a'' și ''b'' sunt [[multiplu|multipli]] ai lui ''g'', ele pot fi scrise sub forma ''a''&nbsp;=&nbsp;''mg'' și ''b''&nbsp;=&nbsp;''ng'', și nu există niciun număr mai mare ''G''&nbsp;>&nbsp;''g'' pentru care aceasta să fie adevărată. Numerele naturale ''m'' și ''n'' trebuie să fie prime între ele, deoarece orice factor comun poate fi scos din ''m'' și ''n'' pentru a-l face pe ''g'' mai mare. Astfel, orice alt număr ''c'' care divide și pe ''a'' și pe ''b'' trebuie să-l dividă și pe ''g''. Cel mai mare divizor comun ''g'' al lui ''a'' și ''b'' poate fi definit ca divizorul comun care este divizibil cu orice alt divizor comun ''c''.<ref>Leveque, p. 31.</ref>

CMMDC poate fi vizualizat geometric după cum urmează.<ref>{{citat carte | author = Grossman JW | year = 1990 | title = Discrete Mathematics | publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = 213}}</ref> Fie o suprafață dreptunghiulară ''a'' pe ''b'', și orice divizor comun ''c'' care divide pe ''a'' și pe ''b''. Laturile dreptunghiului pot fi divizate în segmente de lungime ''c'', ceea ce împarte dreptunghiul în pătrate de latură ''c''. Cel mai mare divizor comun ''g'' este cea mai mare valoare a lui ''c'' pentru care acest lucru este posibil. Pentru ilustrare, o suprafață dreptunghiulară de 24-pe-60 se poate diviza în pătrate de: 1-pe-1, 2-pe-2, 3-pe-3, 6-pe-6 sau 12-pe-12. Deci 12 este cel mai mare divizor comun al lui 24 și 60. O suprafață dreptunghiulară 24-pe-60 poate fi împărțită într-un grid de 12-pe-12 pătrate, cu două pătrate pe o latură (24/12&nbsp;=&nbsp;2) și cinci pătrate pe cealaltă (60/12&nbsp;=&nbsp;5).

CMMDC a două numere ''a'' și ''b'' se poate defini ca produsul factorilor primi comuni ai celor două numere.<ref name="Schroeder_21" >Schroeder, pp. 21–22.</ref> De exemplu, întrucât 462 se factorizează în 2&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;11 și 1071 se factorizează în 3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;17, cel mai mare divizor comun al lui 462 și 1071 este egal cu 21&nbsp;=&nbsp;3&nbsp;×&nbsp;7, produsul factorilor lor primi comuni. Dacă două numere nu au factori primi în comun, cel mai mare divizor comun al lor este 1—ele sunt prime între ele. Un avantaj important al algoritmului lui Euclid este că el poate găsi CMMDC eficient fără să trebuiască să calculeze factorii primi.<ref>Schroeder, p. 19.</ref><ref>{{citat carte | author = Ogilvy CS, Anderson JT | year = 1966 | title = Excursions in number theory | publisher = [[Oxford University Press]] | location = New York | id = {{LCCN|66|0|14484}} | pages = 27–29}}</ref> [[Factorizarea întregilor|Factorizarea]] numerelor întregi mari este considerată a fi o problemă atât de dificilă încât multe sisteme criptografice moderne se bazează pe ea.<ref name="Schroeder_216" >Schroeder, pp. 216–219.</ref>

O definiție mai subtilă a CMMDC este utilă în matematica avansată, în particular în [[teoria inelelor]].<ref name="Leveque_p33" /> Cel mai mare divizor comun ''g''&nbsp; al două numere ''a'' și ''b'' este și cel mai mic [[multiplu|multiplu întreg]] al lor, adică cel mai mic număr de forma ''ua''&nbsp;+&nbsp;''vb'' unde ''u'' și ''v'' sunt numere întregi. Rezultă că mulțimea multiplilor întregi ai lui ''a'' și ''b'' (mulțimea numerelor de forma ''ua''&nbsp;+&nbsp;''vb'') este aceeași cu mulțimea multiplilor întregi ai lui ''g'' (''mg'', unde ''m'' este întreg). În limbajul matematic modern, [[Ideal (teoria inelelor)|Idealul]] format de ''a'' și ''b'' este [[ideal principal]] generat de&nbsp;''g''. Echivalența acestei definiții a CMMDC cu celelalte definiții este descrisă mai jos.

CMMDC a trei sau mai multe numere este egal cu produsul factorilor primi comuni ai tuturor celor trei numere,<ref>Stark, p. 25.</ref> care poate fi calculat luând CMMDC pe perechi de numere.<ref>Ore, pp. 47–48.</ref> De exemplu,

: CMMDC(''a'',&nbsp;''b'',&nbsp;''c'') = CMMDC(''a'',&nbsp;CMMDC(''b'',&nbsp;''c'')) = CMMDC(CMMDC(''a'',&nbsp;''b''),&nbsp;''c'') = CMMDC(CMMDC(''a'',&nbsp;''c''),&nbsp;''b'').

Astfel, algoritmul lui Euclid care calculează CMMDC al doi întregi este suficient pentru a calcula CMMDC al oricât de mulți întregi.

=== Inducție, recursivitate și coborâre infinită ===
Trei metode matematice sunt utilizate mai jos: [[Inducție matematică|inducția]], [[recursivitate]]a și [[Coborâre infinită|coborârea infinită]]. Inducția<ref>{{citat carte|first=Donald E.|last=Knuth|authorlink=Donald Knuth|year=1997|title=The Art of Computer Programming, Volume 1: Fundamental Algorithms|edition=3rd|publisher=Addison-Wesley|isbn=0-201-89683-4}} (Secțiunea 1.2.1: Mathematical Induction, pp. 11–21.)</ref> este utilizată adesea pentru a demonstra o teoremă pentru toate [[Număr natural|numerele naturale]] ''n''.<ref>Rosen, pp. 18–21.</ref> Această abordare începe prin a arăta că, dacă teorema este valabilă pentru ''n'', ea este valabilă și pentru ''n''&nbsp;+&nbsp;1. Astfel, dacă teorema este valabilă pentru un singur caz (de regulă, ''n''&nbsp;=&nbsp;1), ea este valabilă pentru toate numerele mai mari (''n''&nbsp;=&nbsp;2,&nbsp;3,&nbsp;etc.). Recursivitatea unei ecuații<ref>Rosen, pp. 21–24.</ref> este proprietatea ei de a lega numerele ce formează un [[Șir (matematică)|șir]] ''a''<sub>1</sub>,&nbsp;''a''<sub>2</sub>,&nbsp;''a''<sub>3</sub>,&nbsp;etc.<ref>{{citat carte | author = Anderson JA | year = 2001 | title = Discrete Mathematics with Combinatorics | publisher = Prentice Hall | location = Upper Saddle River, NJ | isbn = 0-13-086998-8 | pages = 165–223}}</ref> Al ''n''-lea termen al șirului, ''a''<sub>''n''</sub>, este adesea exprimat în funcție de alți termeni ai șirului, cum ar fi ''a''<sub>''n''−1</sub>. De exemplu, [[Șirul lui Fibonacci|numerele Fibonacci]] sunt definite recursiv; fiecare termen este suma celor doi termeni precedenți: ''F''<sub>''n''</sub>&nbsp;=&nbsp;''F''<sub>''n''−1</sub>&nbsp;+&nbsp;''F''<sub>''n''−2</sub>. Mai multe ecuații asociate cu algoritmul lui Euclid sunt recursive. În fine, în coborârea infinită,<ref>Rosen, p. 492.</ref> o soluție dată în numere naturale este utilizată pentru a construi o soluție cu numere naturale mai mici.<ref>{{citat carte | author = Anderson JA | year = 2001 | title = Discrete Mathematics with Combinatorics | publisher = Prentice Hall | location = Upper Saddle River, NJ | isbn = 0-13-086998-8 | pages = 109–119}}</ref> Soluțiile, însă, nu se pot micșora nelimitat, deoarece există un număr finit de numere naturale mai mici ca numerele naturale inițiale. Astfel, fie soluția originală era imposibilă, fie construcția unor soluții mai mici trebuie să se termine. Acest din urmă argument este folosit pentru a arăta că algoritmul lui Euclid pentru numere naturale trebuie să se termine într-un număr finit de pași.<ref name="Stark_p18" />

== Descriere ==
=== Procedură ===
Algoritmul lui Euclid este iterativ, adică răspunsul se găsește după un număr de pași; rezultatul fiecărui pas este utilizat ca punct de început pentru pasul următor.<ref name="Stark, pp. 16–20">Stark, pp. 16–20.</ref> Fie ''k'' un întreg care numără pașii algoritmului, începând cu zero. Astfel, pasul inițial corespunde lui ''k''&nbsp;=&nbsp;0, pasul următor corespunde lui ''k''&nbsp;=&nbsp;1, și așa mai departe.

Fiecare pas începe cu două resturi nenegative ''r''<sub>''k''−1</sub> și ''r''<sub>''k''−2</sub>. Întrucât algoritmul asigură că resturile scad la fiecare pas, ''r''<sub>''k''−1</sub> este mai mic decât predecesorul sau ''r''<sub>''k''−2</sub>. Scopul pasului ''k'' este găsirea [[cât]]ului ''q''<sub>''k''</sub> și a [[rest]]ului ''r''<sub>''k''</sub> astfel încât să fie satisfăcută ecuația:

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

unde ''r''<sub>''k''</sub>&nbsp;<&nbsp;''r''<sub>''k''−1</sub>. Cu alte cuvinte, multiplii celui mai mic număr ''r''<sub>''k''−1</sub> sunt scăzuți din numărul mai mare ''r''<sub>''k''−2</sub> până când restul este mai mic decât ''r''<sub>''k''−1</sub>.

În pasul inițial (''k''&nbsp;=&nbsp;0), resturile ''r''<sub>−2</sub> și ''r''<sub>−1</sub> sunt chiar ''a'' și ''b'', numerele al căror CMMDC este căutat. În pasul următor (''k''&nbsp;=&nbsp;1), resturile sunt ''b'' și restul ''r''<sub>0</sub> al pasului inițial, și așa mai departe. Astfel, algoritmul poate fi scris ca o secvență de ecuații

: ''a'' = ''q''<sub>0</sub> ''b'' + ''r''<sub>0</sub>
: ''b'' = ''q''<sub>1</sub> ''r''<sub>0</sub> + ''r''<sub>1</sub>
: ''r''<sub>0</sub> = ''q''<sub>2</sub> ''r''<sub>1</sub> + ''r''<sub>2</sub>
: ''r''<sub>1</sub> = ''q''<sub>3</sub> ''r''<sub>2</sub> + ''r''<sub>3</sub>
: …

Dacă ''a'' este mai mic decât ''b'', primul pas al algoritmului schimbă numerele între ele. De exemplu, dacă ''a''&nbsp;<&nbsp;''b'', câtul inițial ''q''<sub>0</sub> este zero, iar restul ''r''<sub>0</sub> este ''a''. Astfel, ''r''<sub>''k''</sub> este mai mic decât predecesorul său ''r''<sub>''k''−1</sub> pentru orice ''k''&nbsp;≥&nbsp;0.

Întrucât resturile scad la fiecare pas dar nu pot fi niciodată negative, un rest ''r''<sub>''N''</sub> trebuie în cele din urmă să fie zero, moment în care algoritmul se oprește.<ref name="Stark_p18" >Stark, p. 18.</ref> Ultimul rest nenul ''r''<sub>''N''−1</sub> este cel mai mare divizor comun al lui ''a'' și ''b''. Numărul ''N'' nu poate fi infinit deoarece există doar un număr finit de numere nenegative întregi între restul inițial ''r''<sub>0</sub> și zero.

=== Demonstrația corectitudinii ===
Corectitudinea algoritmului lui Euclid se poate demonstra în doi pași.<ref name="Stark, pp. 16–20"/> La primul pas, se arată că ultimul rest nenul ''r''<sub>''N''−1</sub> divide atât pe ''a'' cât și pe ''b''. Cum este divizor comun, el trebuie să fie mai mic sau egal cu cel mai mare divizor comun ''g''. În al doilea pas, se arată că orice divizor comun al lui ''a'' și ''b'', inclusiv ''g'', trebuie să-l dividă pe ''r''<sub>''N''−1</sub>; deci, ''g'' trebuie să fie mai mic sau egal cu ''r''<sub>''N''−1</sub>. Aceste două concluzii sunt inconsistente doar dacă ''r''<sub>''N''−1</sub>&nbsp;nu este egal cu&nbsp;''g''.

Pentru a demonstra că ''r''<sub>''N''−1</sub> divide și pe ''a'' și pe ''b'' (primul pas), ''r''<sub>''N''−1</sub> divide predecesorul său ''r''<sub>''N''−2</sub>

: ''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub>

întrucât ultimul rest ''r''<sub>''N''</sub> este zero. ''r''<sub>''N''−1</sub> divide și pe următorul său predecesor ''r''<sub>''N''−3</sub>

: ''r''<sub>''N''−3</sub> = ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub> + ''r''<sub>''N''−1</sub>

deoarece el divide ambii termeni ai părții drepte a ecuației. Iterând același argument, ''r''<sub>''N''−1</sub> divide toate celelalte resturi, inclusiv pe ''a'' și pe ''b''. Niciunul din resturile anterioare ''r''<sub>''N''−2</sub>, ''r''<sub>''N''−3</sub>, etc. nu divid pe ''a'' și pe ''b'', deoarece toate lasă un rest nenul. Cum ''r''<sub>''N''−1</sub> este un divizor comun al lui ''a'' și ''b'', ''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g''.

În al doilea pas, orice număr natural ''c'' care divide pe ''a'' și pe ''b'' (cu alte cuvinte, orice divizor comun al lui ''a'' și ''b'') divide resturile ''r''<sub>''k''</sub>. Prin definiție, ''a'' și ''b'' pot fi scrise ca multipli de ''c'': ''a''&nbsp;=&nbsp;''mc'' și ''b''&nbsp;=&nbsp;''nc'', unde ''m'' și ''n'' sunt numere naturale. Deci ''c'' divide restul inițial ''r''<sub>0</sub>, întrucât ''r''<sub>0</sub>&nbsp;=&nbsp;''a''&nbsp;−&nbsp;''q''<sub>0</sub>''b''&nbsp;=&nbsp;''mc''&nbsp;−&nbsp;''q''<sub>0</sub>''nc''&nbsp;=&nbsp;(''m''&nbsp;−&nbsp;''q''<sub>0</sub>''n'')''c''. O demonstrație analogă arată că ''c'' divide și celelalte resturi ''r''<sub>1</sub>, ''r''<sub>2</sub>, etc. Deci cel mai mare divizor comun ''g'' divide ''r''<sub>''N''−1</sub>, de unde rezultă că ''g''&nbsp;≤&nbsp;''r''<sub>''N''−1</sub>. Întrucât în prima parte a demonstrației s-a arătat că (''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g''), rezultă că ''g''&nbsp;=&nbsp;''r''<sub>''N''−1</sub>. Deci ''g'' este cel mai mare divizor comun al tuturor perechilor succesive:<ref>Knuth, p. 320.</ref><ref name="Lovasz_2003">{{citat carte | author = Lovász L, Pelikán J, Vesztergombi K | year = 2003 | title = Discrete Mathematics: Elementary and Beyond | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-95584-4 | pages = 100–101}}</ref>

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

=== Exemplu ===
[[Fișier:Euclidean algorithm 1071 462.gif|right|thumb|Animație a algoritmului. Dreptunghiul verde inițial are dimensiunile ''a''&nbsp;=&nbsp;1071 și ''b''&nbsp;=&nbsp;462. El se împarte în pătrate de dimensiune 462×462 până rămâne un dreptunghi 462×147. Acesta e împărțit mai departe în pătrate 147×147 până rămâne un dreptunghi 21×147. Acest al treilea dreptunghi este împărțit în pătrate 21×21, și nu rămâne niciun rest. Deci 21 este cel mai mare divizor comun al lui 1071 și 462.]]

Pentru ilustrare, algoritmul lui Euclid se poate utiliza pentru a găsi cel mai mare divizor comun al lui ''a''&nbsp;=&nbsp;1071 și ''b''&nbsp;=&nbsp;462. Pentru început, multiplii lui 462 sunt scăzuți din 1071 până rămâne un rest mai mic decât 462. Se pot scădea doi astfel de multipli (''q''<sub>0</sub>&nbsp;=&nbsp;2), lăsând numărul 147

: 1071 = 2 × 462 + 147.

Apoi multiplii lui 147 sunt scăzuți din 462 până când restul este mai mic decât 147. Trei multipli se pot scădea (''q''<sub>1</sub>&nbsp;=&nbsp;3) și rămâne restul 21

: 462 = 3 × 147 + 21.

Apoi se scad multiplii lui 21 din 147 până când restul este mai mic decât 21. Se pot scădea șapte multipli (''q''<sub>2</sub>&nbsp;=&nbsp;7) și nu rămâne niciun rest

: 147 = 7 × 21 + 0.

Cum ultimul rest este zero, algoritmul se termină cu 21 ca cel mai mare divizor comun al lui 1071 și 462. Rezultatul este în concordanță cu CMMDC(1071, 462) găsit prin factorizarea efectuată mai sus. În formă tabelară, pașii sunt:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
!Numărul pasului!!Ecuația!!Cât și rest
|-
| 0 || 1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub> || ''q''<sub>0</sub> = 2 and ''r''<sub>0</sub> = 147
|-
| 1 || 462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub> || ''q''<sub>1</sub> = 3 and ''r''<sub>1</sub> = 21
|-
| 2 || 147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub> || ''q''<sub>2</sub> = 7 and ''r''<sub>2</sub> = 0; algoritmul ia sfârșit
|}

=== Vizualizare ===
Algoritmul lui Euclid poate fi vizualizat în termenii analogiei pătratelor dată mai sus pentru cel mai mare divizor comun.<ref name="Kimberling_1983">{{cite journal | author = Kimberling C | year = 1983 | title = A Visual Euclidean Algorithm | journal = Mathematics Teacher | volume = 76 | pages = 108–109}}</ref> Se presupune că se dorește acoperirea unui dreptunghi ''a''-pe-''b'' cu pătrate care să-l acopere exact, unde ''a'' este cel mai mare dintre cele două numere. Întâi, se încearcă împărțirea dreptunghiului în pătrate ''b''-pe-''b''; aceasta lasă, însă, un dreptunghi rezidual ''r''<sub>0</sub>-pe-''b'' neacoperit, unde ''r''<sub>0</sub><''b''. Atunci se încearcă împărțirea dreptunghiului rezidual cu pătrate ''r''<sub>0</sub>-pe-''r''<sub>0</sub>. Rămâne un al doilea dreptunghi rezidual ''r''<sub>1</sub>-pe-''r''<sub>0</sub>, pe care se încearcă să fie acoperit cu pătrate ''r''<sub>1</sub>-pe-''r''<sub>1</sub>, și așa mai departe. Șirul acesta se termină atunci când nu mai rămâne niciun dreptunghi rezidual, adică atunci când pătratele acoperă exact dreptunghiul rezidual. Lungimea laturilor celui mai mic pătrat este CMMDC al dimensiunilor dreptunghiului original. De exemplu, cel mai mic pătrat din figura alăturată este 21-pe-21 (cu roșu), iar 21 este CMMDC de 1071 și 462, dimensiunile dreptunghiului original (verde).

=== Calculul câturilor și resturilor ===

La fiecare pas ''k'', algoritmul lui Euclid calculează un cât ''q''<sub>''k''</sub> și un rest ''r''<sub>''k''</sub> ale două numere ''r''<sub>''k''−1</sub> și ''r''<sub>''k''−2</sub>

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

unde [[Valoare absolută|modulul]] lui ''r''<sub>''k''</sub> este strict mai mic decât cel al lui ''r''<sub>''k''−1</sub>. Teorema împărțirii cu rest asigură că există întotdeauna acest cât și acest rest. Teorema împărțirii cu rest a numerelor naturale spune și că ''q''<sub>''k''</sub> și ''r''<sub>''k''</sub> sunt unice, dar unicitatea lor nu este necesară pentru algoritmul lui Euclid.<ref name="Cohn_1962">Cohn, pp. 104–110.</ref>

În versiunea originală dată de Euclid pentru acest algoritm, câtul și restul se găsesc prin scădere repetată; adică ''r''<sub>''k''−1</sub> este scăzut din ''r''<sub>''k''−2</sub> repetat până când restul ''r''<sub>''k''</sub> este mai mic decât ''r''<sub>''k''−1</sub>. O abordare mai eficientă utilizează împărțirea numerelor întregi și [[operația modulo]] pentru a calcula respectiv câtul și restul. Operația modulo dă restul împărțirii a două numere; astfel,

:''r''<sub>''k''</sub> [[Aritmetică modulară|≡]] ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>

Restul este echivalent cu clasa de congruență din [[aritmetica modulară]].

=== Implementări ===
Implementările algoritmului se pot exprima în [[pseudocod]]. De exemplu, versiunea bazată pe împărțire trebuie să fie [[Programarea calculatoarelor|programată]] ca<ref>Knuth, pp. 319–320.</ref>

 '''function''' CMMDC(a, b)
     '''while''' b ≠ 0
        t := b
        b := a '''mod''' b
        a := t
     '''return''' a

La începutul iterației ''k'', variabila ''b'' deține ultimul rest ''r''<sub>''k''−1</sub>, iar variabila ''a'' deține predecesorul acesteia, ''r''<sub>''k''−2</sub>. Pasul ''b'' := ''a'' mod ''b'' este echivalent cu formula recursivă de mai sus ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>. Variabila ''t'' reține valoarea lui ''r''<sub>''k''−1</sub> în timp ce se calculează următorul rest ''r''<sub>''k''</sub>. La sfârșitul acestei bucle de iterații, variabila ''b'' va păstra restul ''r''<sub>''k''</sub>, iar variabila ''a'' va reține predecesorul, ''r''<sub>''k''−1</sub>.

În versiunea pe bază de scădere, definită de Euclid, calculul restului (''b''&nbsp;=&nbsp;''a'' mod ''b'') este înlocuit cu scăderea repetată.<ref>Knuth, pp. 318–319.</ref>

 '''function''' CMMDC(a, b)
     '''if''' a = 0
        '''return''' b
     '''while''' b ≠ 0
         '''if''' a > b
            a := a − b
         '''else'''
            b := b − a
     '''return''' a

Variabilele ''a'' și ''b'' rețin alternativ resturile anterioare ''r''<sub>''k''−1</sub> și ''r''<sub>''k''−2</sub>. Se presupune că ''a'' este mai mare ca ''b'' la începutul unei iterații; atunci ''a'' este egal cu ''r''<sub>''k''−2</sub>, fiindcă ''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>. Pe parcursul acestei bucle, ''a'' este redus cu multipli ai restului anterior ''b'' până când ''a'' este mai mic ca ''b''. Atunci ''a'' este următorul rest ''r''<sub>''k''</sub>. Atunci ''b'' este redus cu multipli ai lui ''a'' până când este mai mic decât ''a'', dând următorul rest ''r''<sub>''k''+1</sub>, și așa mai departe.

Versiunea recursivă<ref>Stillwell, p. 14.</ref> se bazează pe egalitatea CMMDC al resturilor succesive și pe condiția de oprire CMMDC(''r''<sub>''N''−1</sub>,&nbsp;0)&nbsp;=&nbsp;''r''<sub>''N''−1</sub>.

 '''function''' CMMDC(a, b)
     '''if''' b = 0
        '''return''' a
     '''else'''
        '''return''' CMMDC(b, a '''mod''' b)

Pentru ilustrare, se calculează CMMDC(1071,&nbsp;462) din CMMDC(462,&nbsp;1071&nbsp;mod&nbsp;462)&nbsp;=&nbsp;CMMDC(462,&nbsp;147). Acest al doilea CMMDC se calculează din CMMDC(147,&nbsp;462&nbsp;mod&nbsp;147)&nbsp;=&nbsp;CMMDC(147,&nbsp;21), care la rândul său se calculează din CMMDC(21,&nbsp;147&nbsp;mod&nbsp;21)&nbsp;=&nbsp;CMMDC(21,&nbsp;0)&nbsp;=&nbsp;21.

=== Metoda celor mai mici resturi absolute ===
Într-o altă versiune a algoritmului lui Euclid, câtul de la fiecare pas este crescut cu unu dacă restul negativ rezultat este mai mic în modul decât restul pozitiv tipic.<ref name="Ore_least_abs_remainders" >Ore, p. 43.</ref><ref name="Stewart_1964">{{citat carte | author = Stewart BM | year = 1964 | title = Theory of Numbers | edition = 2nd | publisher = Macmillan | location = New York | id = {{LCCN|64|0|10964}} | pages = 43–44}}</ref> Anterior, ecuația

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

presupunea că ''r''<sub>''k''−1</sub>&nbsp;>&nbsp;''r''<sub>''k''</sub>&nbsp;>&nbsp;0. Se poate, însa, calcula și un alt rest negativ ''e''<sub>''k''</sub>

: ''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>

unde ''r''<sub>''k''−1</sub> este presupus pozitiv. Dacă |''e''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''</sub>|, atunci ''r''<sub>''k''</sub> este înlocuit de ''e''<sub>''k''</sub>. După cum a arătat [[Leopold Kronecker]], această versiune necesită cel mai mic număr de pași dintre toate versiunile algoritmului lui Euclid.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" />

== Istoric ==
[[Fișier:Euklid.jpg|thumb|Algoritmul lui Euclid a fost probabil inventat cu câteva secole înaintea lui [[Euclid]] (în imagine)]]

Algoritmul lui Euclid este unul dintre cei mai vechi algoritmi încă în uz.<ref name="Knuth, p. 318">Knuth, p. 318.</ref> El apare în [[Elementele lui Euclid|''Elemente'']] (c. [[300 î.e.n.]]), anume în Cartea 7 (Propunerile 1–2) și în Cartea 10 (Propunerile 2–3). În Cartea 7, algoritmul este formulat pentru întregi, pe când în Cartea 10, el este formulat pentru lungimi de segmente de dreaptă. (în uz modern, s-ar spune că a fost formulat pentru [[Număr real|numere reale]]. Dar lungimile, ariile și volumele, reprezentate ca numere reale în uz modern, nu se măsoară în aceleași unități și nu există o unitate naturală de lungime, arie sau volum, iar conceptul de numere reale nu era cunoscut la acea vreme.) Al doilea algoritm este geometric. CMMDC al două lungimi ''a'' și ''b'' corespunde celei mai mari lungimi ''g'' care măsoară ''a'' și ''b'' exact; cu alte cuvinte, lungimile ''a'' și ''b'' sunt ambele multipli întregi ai lungimii&nbsp;''g''.

Algoritmul nu a fost, probabil, descoperit de [[Euclid]], care doar a compilat rezultate ale matematicienilor dinaintea sa în lucrarea ''Elemente''.<ref name="Weil_1983">{{citat carte | author = [[André Weil|Weil A]] | year = 1983 | title = Number Theory | publisher = Birkhäuser | location = Boston | isbn = 0-8176-3141-0 | pages = 4–6}}</ref><ref name="Jones_1994">{{citat carte | author = Jones A | year = 1994 | chapter = Greek mathematics to AD 300 | title = Companion encyclopedia of the history and philosophy of the mathematical sciences | publisher = Routledge | location = New York | isbn = 0-415-09238-8 | pages = 46–48}}</ref> Matematicianul și istoricul [[Bartel Leendert van der Waerden|B. L. van der Waerden]] sugerează că Cartea VII derivă dintr-un manual de [[teoria numerelor]] scris de matematicieni ai școlii lui [[Pitagora]].<ref name="van_der_Waerden_1954">{{citat carte | author = [[Bartel Leendert van der Waerden|van der Waerden BL]] | year = 1954 | title = Science Awakening | series = translated by Arnold Dresden | publisher = P. Noordhoff Ltd | location = Groningen | pages = 114–115}}</ref> Algoritmul a fost probabil cunoscut lui [[Eudoxus din Cnidus]] (circa 375 î.e.n.)<ref name="Knuth, p. 318"/><ref>{{cite journal | author = von Fritz K | date = 1945 | title = The Discovery of Incommensurability by Hippasus of Metapontum | journal = Ann. Math. | volume = 46 | pages = 242–264 | doi = 10.2307/1969021}}</ref> Algoritmul ar putea fi dinainte chiar și de Eudoxus,<ref>{{citat carte | author = [[T. L. Heath|Heath TL]] | year = 1949 | title = Mathematics in Aristotle | publisher = Oxford Press | pages = 80–83}}</ref><ref>{{citat carte | author = [[David Fowler (mathematician)|Fowler DH]] | year = 1987 | title = The Mathematics of Plato's Academy: A New Reconstruction | publisher = Oxford University Press | location = Oxford | isbn = 0-19-853912-6 | pages = 31–66}}</ref> judecând după utilizarea termenului tehnic ἀνθυφαίρεσις (''anthyphairesis'', scădere reciprocă) din lucrările lui Euclid și Aristotel.<ref>{{cite journal | author = Becker O | year = 1933 | title = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | journal = Quellen und Studien zur Geschichte der Mathematik B | volume = 2 | pages = 311–333}}</ref>

După mai multe secole, algoritmul lui Euclid a fost descoperit independent în India și în China,<ref name="Stillwell, p. 31">Stillwell, p. 31.</ref> și a fost utilizat mai ales pentru rezolvarea de ecuații diofantice care apar în astronomie și la realizarea de calendare precise. Spre sfârșitul secolului al V-lea, matematicianul și astronomul indian [[Aryabhata]] a descris algoritmul sub numele de „pulverizatorul”,<ref name="Tattersall, p. 70">Tattersall, p. 70.</ref> poate din cauza eficienței sale în rezolvarea de [[Ecuație diofantică|ecuațiilor diofantice]].<ref>Rosen, pp. 86–87.</ref> Deși un caz special al [[Teorema chinezească a resturilor|teoremei chinezești a resturilor]] fusese deja descris de matematicianul și astronomul chinez [[Sun Tzu (matematician)|Sun Tzu]],<ref>Ore, pp. 247–248.</ref> soluția generală a fost publicată de [[Qin Jiushao]] în cartea sa din 1247 intitulată ''Shushu Jiuzhang'' (數書九章 „Tratat matematic în nouă secțiuni”).<ref>Tattersall, pp. 72, 184–185.</ref> Algoritmul lui Euclid a fost descris în Europa pentru prima dată în a doua ediție a lucrării lui [[Claude Gaspard Bachet de Méziriac|Bachet]] ''Problèmes plaisants et délectables'' (''Probleme plăcute și delectabile'', 1624).<ref name="Tattersall, p. 70"/> În Europa, a fost folosit tot pentru rezolvarea de ecuații diofantice, dar și la construcția [[Fracție continuă|fracțiilor continue]]. Algoritmul lui Euclid extins a fost publicat de matematicianul englez [[Nicholas Saunderson]], care i l-a atribuit lui [[Roger Cotes]] ca metodă de calcul eficient a fracțiilor continue.<ref>Tattersall, pp. 72–76.</ref>

În secolul al XIX-lea, algoritmul lui Euclid a dus la dezvoltarea unor noi sisteme de numere, cum ar fi [[întregii gaussieni]] și [[întregii eisensteinieni]]. În 1815, [[Carl Friedrich Gauss|Carl Gauss]] a utilizat algoritmul lui Euclid pentru a demonstra factorizarea unică a întregilor gaussieni, deși lucrarea sa a fost publicată pentru prima oară în 1832.<ref name="Gauss_1832" /> Gauss a menționat algoritmul în ''[[Disquisitiones Arithmeticae]]'' (publicat la 1801), dar numai ca metodă pentru fracțiile continue.<ref name="Stillwell, p. 31"/> [[Johann Peter Gustav Lejeune Dirichlet|Peter Dirichlet]] pare a fi fost primul care a descris algoritmul lui Euclid ca bază pentru teoria numerelor.<ref>Stillwell, pp. 31–32.</ref> Dirichlet a observat că multe din rezultatele teoriei numerelor, cum ar fi unicitatea factorizării, sunt adevărate pentru toate celelalte sisteme de numere în care se poate aplica algoritmul lui Euclid.<ref>Dirichlet, pp. 29–31.</ref> Cursurile lui Dirichlet pe tema teoriei numerelor au fost editate și extinse de [[Richard Dedekind]], care a utilizat algoritmul lui Euclid pentru a studia întregii algebrici, un tip general de numere. De exemplu, Dedekind a fost primul care a demonstrat [[Teorema lui Fermat despre suma a două pătrate|teorema celor două pătrate a lui Fermat]] folosind factorizarea unică a întregilor gaussieni.<ref>{{citat carte | author = [[Richard Dedekind|Dedekind R]] | year = 1894 | chapter = Supplement XI | title = Vorlesungen über Zahlentheorie | editor = PGL Dirichlet }}</ref> Dedekind a definit și conceptul de [[domeniu euclidian]], un sistem numeric în care se poate defini o versiune generalizată a algoritmului lui Euclid. În ultimele decenii ale secolului al XIX-lea, însă, algoritmul lui Euclid a fost treptat eclipsat de teoria mai generală a lui Dedekind despre ideale.<ref>{{citat carte | author = [[John Stillwell|Stillwell J]] | year = 2003 | title = Elements of Number Theory | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-95587-9 | pages = 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;" |
„[Algoritmul lui Euclid] este străbunicul tuturor algoritmilor, deoarece este cel mai vechi algoritm netrivial care a supraviețuit până în ziua de azi.”
|-
| style="text-align: left;" | [[Donald Knuth]], ''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', 2nd edition (1981), p.&nbsp;318.
|}

În secolul al XIX-lea au fost dezvoltate și alte aplicații ale algoritmului lui Euclid. În 1829, [[Jacques Charles François Sturm|Charles Sturm]] a arătat că algoritmul este util în metoda [[Teorema lui Sturm|lanțurilor Sturm]] de numărare a rădăcinilor reale dintr-un interval dat ale polinoamelor.<ref>{{cite journal | author = Sturm C | year = 1829 | title = Mémoire sur la résolution des équations numériques | journal = Bull. des sciences de Férussac | volume = 11 | pages = 419–422}}</ref>

Algoritmul lui Euclid a fost prima metodă de descoperire a relațiilor între numere întregi de același ordin de mărime. În ultimii ani, s-au mai dezvoltat câțiva alți algoritmi noi legați de relațiile între întregi, ca de exemplu [[algoritmul Ferguson–Forcade]] (1979) al lui [[Helaman Ferguson]] și R.W. Forcade,<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> și algoritmii asociați, [[algoritmul de reducere Lenstra–Lenstra–Lovász|algoritmul LLL]], [[algoritmul HJLS]] și [[algoritmul PSLQ]].<ref>{{cite journal | author = Peterson I | date = 12 august 2002 | title = [http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm Jazzing Up Euclid's Algorithm] | journal = ScienceNews }}</ref><ref>{{cite journal | author = Cipra BA | title = [http://amath.colorado.edu/resources/archive/topten.pdf The Best of the 20th Century: Editors Name Top 10 Algorithms] | journal = SIAM News | volume = 33 | number = 4 | date = 16 mai 2000 | publisher = [[Society for Industrial and Applied Mathematics]]}}</ref>

În 1969, Cole și Davie au dezvoltat un joc în doi pe baza algoritmului lui Euclid, joc intitulat ''Jocul lui Euclid'',<ref>{{en}}{{cite journal | author = Cole AJ, Davie AJT | year = 1969 | title = A game based on the Euclidean algorithm and a winning strategy for it | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461}}</ref> care are o strategie optimă.<ref>{{cite journal | author = Spitznagel EL | year = 1973 | title = Properties of a game based on Euclid's algorithm | journal = Math. Mag. | volume = 46 | pages = 87–92}}</ref> Jucătorii încep cu două grămezi de pietre ''a'' și ''b''. Jucătorii elimină pe rând ''m'' multipli ai celei mai mici grămezi din cea mai mare. Astfel, daca cele două grămezi au ''x'' respectiv ''y'' pietre, unde ''x'' este mai mare ca ''y'', următorul jucător poate reduce grămada mai mare de la ''x'' pietre la ''x'' − ''my'' pietre, atâta vreme cât al doilea este un număr nenegativ. Câștigă primul jucător care reduce una dintre grămezi la zero pietre.<ref>Rosen, p. 95.</ref><ref>{{citat carte | author = Roberts J | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-0 | pages = 1–8}}</ref>

== Aplicații matematice ==
=== Identitatea lui Bézout ===
[[Identitatea lui Bézout]] spune că cel mai mare divizor comun ''g'' al două numere întregi ''a'' și ''b'' se poate reprezenta sub formă de combinație liniară a primelor două numere ''a'' și ''b''.<ref>{{citat carte | author = Jones GA, Jones JM | year = 1998 | chapter = Bezout's Identity | title = Elementary Number Theory | publisher = [[Springer-Verlag]] | location = New York | pages = 7–11}}</ref> Cu alte cuvinte, întotdeauna există două numere întregi ''s'' și ''t'' astfel încât ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''.<ref>Rosen, p. 81.</ref><ref>Cohn, p. 104.</ref>

Întregii ''s'' și ''t'' pot fi calculați pe baza câturilor ''q''<sub>0</sub>, ''q''<sub>1</sub> etc. inversând ordinea ecuațiilor din algoritmul lui Euclid.<ref>Rosen, p. 91.</ref> Începând cu penultima ecuație, ''g'' poate fi exprimat în termeni de câtul ''q''<sub>''N''−1</sub> și de cele două resturi anterioare, ''r''<sub>''N''−2</sub> și ''r''<sub>''N''−3</sub>.

: ''g'' = ''r''<sub>''N''−1</sub> = ''r''<sub>''N''−3</sub> − ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub>

Acele două resturi pot fi, de asemenea, exprimate în termeni de câturile corespunzătoare lor și de resturile anterioare,

: ''r''<sub>''N''−2</sub> = ''r''<sub>''N''−4</sub> − ''q''<sub>''N''−2</sub> ''r''<sub>''N''−3</sub>
: ''r''<sub>''N''−3</sub> = ''r''<sub>''N''−5</sub> − ''q''<sub>''N''−3</sub> ''r''<sub>''N''−4</sub>

Înlocuind aceste formule pentru ''r''<sub>''N''−2</sub> și ''r''<sub>''N''−3</sub> în prima ecuație rezultă ''g'' sub formă de combinație liniară a resturilor ''r''<sub>''N''−4</sub> și ''r''<sub>''N''−5</sub>. Procesul de substituție a resturilor din formulele ce implică predecesoarele lor se poate continua până când se ajunge la numerele originale ''a'' și ''b''

: ''r''<sub>2</sub> = ''r''<sub>0</sub> − ''q''<sub>2</sub> ''r''<sub>1</sub>
: ''r''<sub>1</sub> = ''b'' − ''q''<sub>1</sub> ''r''<sub>0</sub>
: ''r''<sub>0</sub> = ''a'' − ''q''<sub>0</sub> ''b''

După ce toate resturile ''r''<sub>0</sub>, ''r''<sub>1</sub> etc. au fost substituite, ultima ecuație îl exprimă pe ''g'' sub forma unei combinații liniare de ''a'' și ''b'': ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''. [[Identitatea lui Bézout]], și deci și algoritmul anterior, poate fi generalizată la contextul domeniilor euclidiene.

=== Ideale principale ===
Identitatea lui Bézout dă o altă definiție a celui mai mare divizor comun ''g'' al două numere ''a'' și ''b''.<ref name="Leveque_p33" >Leveque, p. 33.</ref> Fie mulțimea tuturor numerelor de forma ''ua''&nbsp;+&nbsp;''vb'', unde ''u'' și ''v'' sunt orice două numere întregi. Cum ''a'' și ''b'' sunt ambele divizibile cu ''g'', toate numerele din mulțime sunt divizibile cu ''g''. Cu alte cuvinte, toate numerele din această mulțime sunt multipli întregi ai lui ''g''. Acest lucru este adevărat pentru orice divizor comun al lui ''a'' și ''b''. Spre deosebire de alți divizori comuni, însă, cel mai mare divizor comun este și el membru al mulțimii; din identitatea lui Bézout, alegând ''u''&nbsp;=&nbsp;''s'' și ''v''&nbsp;=&nbsp;''t'' rezultă ''g''. Un divizor comun mai mic nu poate fi membru al mulțimii, deoarece toate elementele mulțimii trebuie să fie divizibile cu ''g''. Invers, orice multiplu ''m'' al lui ''g'' poate fi obținut alegând ''u''&nbsp;=&nbsp;''ms'' și ''v''&nbsp;=&nbsp;''mt'', unde ''s'' și ''t'' sunt întregii din identitatea lui Bézout. Aceasta se poate vedea înmulțind identitatea lui Bézout cu ''m''

: ''mg'' = ''msa'' + ''mtb''

Astfel, mulțimea tuturor numerelor ''ua''&nbsp;+&nbsp;''vb'' este echivalentă cu mulțimea multiplilor ''m'' ai lui ''g''. Cu alte cuvinte, mulțimea tuturor sumelor posibile de multipli întregi ai două numere (''a'' și ''b'') este echivalentă cu mulțimea multiplilor lui CMMDC(''a'', ''b''). CMMDC se spune că este generator al idealului lui ''a'' și ''b''. Aceaată definiție pentru CMMDC a dus la unele concepte moderne din [[algebra abstractă]], cum ar fi cel de [[ideal principal]] (un ideal generat de un singur element) și de domeniu de ideal principal (un domeniu în care toate idealele sunt principale).

Unele probleme se pot rezolva cu acest rezultat.<ref>Schroeder, p. 23.</ref> De exemplu, fie două cești de măsurare de volum ''a'' respectiv ''b''. Adăugând sau scăzând ''u'' multipli ai primei cești și ''v'' multipli ai celei de-a doua cești, poate fi măsurat orice volum ''ua''&nbsp;+&nbsp;''vb''. Aceste volume sunt toate multipli ai lui ''g''&nbsp;=&nbsp;CMMDC(''a'',&nbsp;''b'').

=== Algoritmul lui Euclid extins ===
Întregii ''s'' și ''t'' din identitatea lui Bézout se pot calcula eficient utilizând [[algoritmul lui Euclid extins]]. Această extensie adaugă algoritmului lui Euclid două ecuații recursive<ref>Rosen, pp. 90–93.</ref>

: ''s''<sub>''k''</sub> = ''s''<sub>''k''−2</sub> − ''q''<sub>''k''−1</sub>''s''<sub>''k''−1</sub>
: ''t''<sub>''k''</sub> = ''t''<sub>''k''−2</sub> − ''q''<sub>''k''−1</sub>''t''<sub>''k''−1</sub>

cu valorile de început

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

Cu ajutorul acestei relații de recurență, întregii lui Bézout ''s'' și ''t'' sunt dați de ''s''&nbsp;=&nbsp;''s''<sub>''N''</sub> și ''t''&nbsp;=&nbsp;''t''<sub>''N''</sub>, unde ''N'' este pasul la care algoritmul se termină cu ''r''<sub>''N''</sub>&nbsp;=&nbsp;0.

Validitatea acestei abordări se poate demonstra prin inducție. Se presupune că formula recursivă este corectă până la pasul ''k''−1 al algoritmului, cu alte cuvinte, se presupune că

: ''r''<sub>''j''</sub> = ''s''<sub>''j''</sub> ''a'' + ''t''<sub>''j''</sub> ''b''

pentru orice ''j'' mai mic decât ''k''. Al ''k''-lea pas al algoritmului dă ecuația

: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''−1</sub>''r''<sub>''k''−1</sub>

Întrucât formula de recurență este considerată corectă pentru ''r''<sub>''k''−2</sub> și ''r''<sub>''k''−1</sub>, ele pot fi exprimate în funcție de variabilele corespunzătoare ''s'' și ''t''

: ''r''<sub>''k''</sub> = (''s''<sub>''k''−2</sub> ''a'' + ''t''<sub>''k''−2</sub> ''b'') − ''q''<sub>''k''−1</sub>(''s''<sub>''k''−1</sub> ''a'' + ''t''<sub>''k''−1</sub> ''b'')

Rearanjând această ecuație, rezultă formula de recurență pentru pasul ''k''

: ''r''<sub>''k''</sub> = ''s''<sub>''k''</sub> ''a'' + ''t''<sub>''k''</sub> ''b'' = (''s''<sub>''k''−2</sub> − ''q''<sub>''k''−1</sub>''s''<sub>''k''−1</sub>) ''a'' + (''t''<sub>''k''−2</sub> − ''q''<sub>''k''−1</sub>''t''<sub>''k''−1</sub>) ''b''

=== Metoda matricială ===

Întregii ''s'' și ''t'' pot fi găsiți și folosind o metodă echivalentă bazată pe [[matrice]].<ref name="Koshy_2002">{{citat carte | author = Koshy T | year = 2002 | title = Elementary Number Theory with Applications | publisher = Harcourt/Academic Press | location = Burlington, MA | isbn = 0-12-421171-2 | pages = 167–169}}</ref> Secvența de ecuații a algoritmului lui Euclid

: ''a'' = ''q''<sub>0</sub> ''b'' + ''r''<sub>0</sub>
: ''b'' = ''q''<sub>1</sub> ''r''<sub>0</sub> + ''r''<sub>1</sub>
: …
: ''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub> + 0

se poate scrie ca [[înmulțirea matricilor |produs al matricilor]] câturilor 2-pe-2 înmulțite cu un vector bidimensional al resturilor

:<math>
\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>

Fie '''M''' produsul tuturor matricelor–cât

:<math>
\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>

Aceasta simplifică algoritmul lui Euclid la forma

:<math>
\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>

Pentru a exprima pe ''g'' sub formă de combinație liniară de ''a'' și ''b'', ambele părți ale acestei ecuații pot fi înmulțite cu [[matrice inversabilă|inversa]] matricei '''M'''.<ref name="Koshy_2002" /><ref name="Bach_1996">{{citat carte | author = Bach E, Shallit J | year = 1996 | title = Algorithmic number theory | publisher = MIT Press | location = Cambridge, MA | isbn = 0-262-02405-5 | pages = 70–73}}</ref> [[Determinant]]ul lui '''M''' este egal cu (−1)<sup>''N''+1</sup>, deoarece este egal cu produsul determinanților matricelor–cât, care sunt egale cu minus unu. Întrucât determinantul lui '''M''' nu este niciodată zero, vectorul final de resturi se poate rezolva găsind inversa lui '''M'''

:<math>
\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>

Deoarece ecuația de sus dă

:''g'' = (−1)<sup>''N''+1</sup> ( ''m''<sub>22</sub> ''a'' − ''m''<sub>12</sub> ''b'')

cei doi întregi ai identității lui Bézout sunt ''s''&nbsp;=&nbsp;(−1)<sup>''N''+1</sup>''m''<sub>22</sub> și ''t''&nbsp;=&nbsp;(−1)<sup>''N''</sup>''m''<sub>12</sub>. Metoda matricei este la fel de eficientă ca și cea a formulei de recurență, cu două înmulțiri și două adunări la fiecare pas al algoritmului lui Euclid.

=== Lema lui Euclid și unicitatea factorizării ===
Identitatea lui Bézout este esențială pentru multe aplicații ale algoritmului lui Euclid, cum ar fi demonstrarea unicității descompunerii numerelor în factori primi.<ref>Stark, pp. 26–36.</ref> Pentru a ilustra aceasta, se presupune că un număr ''L'' poate fi scris ca produs de doi factori ''u'' și ''v'', adică ''L''&nbsp;=&nbsp;''uv''. Dacă un alt număr ''w'' îl divide și el pe ''L'' dar este prim cu ''u'', atunci înseamnă că ''w'' îl divide pe ''v'', pentru că, dacă cel mai mare divizor comun al lui ''u'' și ''w'' este 1, atunci se pot găsi doi întregi ''s'' și ''t'' astfel încât

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

conform identității lui Bézout. Înmulțind ambele părți ale ecuației cu ''v'' rezultă relația

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

Cum ''w'' divide ambii termeni din partea dreaptă, înseamnă că el divide și termenul din stânga, ''v''. Acest rezultat este cunoscut sub numele de [[lema lui Euclid]]:<ref name="Ore, p. 44">Ore, p. 44.</ref> Dacă un număr prim divide pe ''L'', atunci el divide cel puțin unul dintre factorii lui ''L''. La fel, dacă un număr ''w'' este prim cu mai multe numere ''a''<sub>1</sub>, ''a''<sub>2</sub>, …, ''a''<sub>''n''</sub>, atunci ''w'' este prim și cu produsul lor, ''a''<sub>1</sub>&nbsp;×&nbsp;''a''<sub>2</sub>&nbsp;×&nbsp;…&nbsp;×&nbsp;''a''<sub>''n''</sub>.<ref name="Ore, p. 44"/>

Lema lui Euclid este suficientă pentru a demonstra că toate numerele au o unică descompunere în factori primi.<ref>Stark, pp. 281–292.</ref> Dacă se presupune contrariul, și anume că există două factorizări independente ale lui ''L'' în ''m'' respectiv ''n'' factori primi

: ''L'' = ''p''<sub>1</sub>''p''<sub>2</sub>…''p''<sub>''m''</sub> = ''q''<sub>1</sub>''q''<sub>2</sub>…''q''<sub>''n''</sub>

Întrucât toate numerele prime ''p'' divid pe ''L'' conform presupunerii, atunci fiecare dintre ele divide unul dintre factorii ''q''; întrucât fiecare ''q'' este și el prim, atunci înseamnă că ''p''&nbsp;=&nbsp;''q''. Împărțind iterativ la factorii ''p'' rezultă că fiecare ''p'' are un corespondent ''q''; cele două descompuneri în factori primi sunt identice cu excepția ordinii factorilor. Factorizarea unică a numerelor în factori primi are mai multe aplicații în demonstrațiile matematice.

=== Ecuațiile liniare diofantice ===
[[Fișier:Diophante Bezout.svg|thumb|Graficul unei [[Ecuaţie diofantică|ecuații diofantice]], 9''x''&nbsp;+&nbsp;12''y''&nbsp;=&nbsp;483. Soluțiile sunt arătate ca cercuri albastre.]]

[[Ecuație diofantică|Ecuațiile diofantice]] sunt ecuații ale căror soluții sunt neapărat numere întregi; ele își trag numele de la matematicianul alexandrin din secolul al III-lea [[Diophantus]].<ref>Rosen, pp. 119–125.</ref> O ecuație diofantică liniară tipică în variabilele întregi ''x'' și ''y'' are forma<ref>Schroeder, pp. 106–107.</ref>

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

unde ''a'', ''b'' și ''c'' sunt numere întregi date. Aceasta se poate scrie ca o ecuație în ''x'' de forma:

: ''ax'' ≡ ''c'' mod ''b''.

Fie ''g'' cel mai mare divizor comun al lui ''a'' și ''b''. Ambii termeni din ecuația ''ax''&nbsp;+&nbsp;''by'' sunt divizibili cu ''g''; deci, fie ''c'' este divizibil cu ''g'', fie ecuația nu are soluții. Împărțind ambele părți ale ecuației la ''c''/''g'', ea poate fi redusă la identitatea lui Bezout

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

unde ''s'' și ''t'' se pot găsi prin algoritmul lui Euclid extins.<ref>Schroeder, pp. 108–109.</ref> Aceasta mai dă o soluție a ecuației diofantice, ''x''<sub>1</sub>&nbsp;=&nbsp;''s'' (''c''/''g'') și ''y''<sub>1</sub>&nbsp;=&nbsp;''t'' (''c''/''g'').

În general, o ecuație diofantică liniară fie nu are soluție, fie are un număr infinit de soluții.<ref>Rosen, pp. 120–121.</ref> Pentru a demonstra cel de-al doilea caz, se consideră două soluții, (''x''<sub>1</sub>,&nbsp;''y''<sub>1</sub>) și (''x''<sub>2</sub>,&nbsp;''y''<sub>2</sub>)

: ''ax''<sub>1</sub> + ''by''<sub>1</sub> = ''c'' = ''ax''<sub>2</sub> + ''by''<sub>2</sub>

sau echivalent

: ''a''(''x''<sub>1</sub> − ''x''<sub>2</sub>) = ''b''(''y''<sub>2</sub> − ''y''<sub>1</sub>).

Astfel, cea mai mică diferență între două soluții ''x'' este ''b''/''g'', pe când cea mai mică diferență între două soluții ''y'' este ''a''/''g''. Astfel, soluțiile pot fi exprimate ca

:''x'' = ''x''<sub>1</sub> − ''bt''/''g''
:''y'' = ''y''<sub>1</sub> + ''at''/''g''.

Permițând lui ''t'' să varieze pe toată mulțimea numerelor întregi, se poate genera o familie infinită de soluții dintr-una singură (''x''<sub>1</sub>,&nbsp;''y''<sub>1</sub>). Dacă soluțiile trebuie să fie întregi pozitivi (''x''&nbsp;>&nbsp;0,&nbsp;''y''&nbsp;>&nbsp;0), este posibil să existe doar un număr finit de soluții. Această [[restricție (matematică)|restricție]] asupra soluțiilor acceptabile permite rezolvarea de sisteme de ecuații diofantice cu un număr de ecuații mai mare decât cel de necunoscute;<ref>Stark, p. 47.</ref> aceasta este imposibilă pentru un [[sistem de ecuații liniare]] ale cărui soluții pot fi orice [[număr real]].

=== Inversul multiplicativ și algoritmul RSA ===
Un [[corp finit]] este o mulțime de numere cu patru operații generice. Aceste operații se numesc adunare, scădere, înmulțire și împărțire și au proprietățile obișnuite, cum ar fi [[comutativitate]]a, [[asociativitate]]a și [[distributivitate]]a. Un exemplu de corp finit este mulțimea de 13 numere {0,&nbsp;1,&nbsp;2,&nbsp;…,&nbsp;12} cu aritmetica modulară. În acest corp, rezultatele oricărei operații matematice (adunare/scădere/înmulțire/împărțire) se reduce [[Operația modulo|modulo]] 13; adică din rezultat se scad multipli ai lui 13 până când rezultatul ajunge să fie între 0–12. De exemplu, rezultatul operației 5&nbsp;×&nbsp;7&nbsp;=&nbsp;35&nbsp;mod&nbsp;13&nbsp;=&nbsp;9. Asemenea corpuri finite pot fi definite pentru orice număr prim ''p''; utilizând definiții mai sofisticate, se pot defini pentru orice putere ''m'' a unui număr prim ''p''<sup>&nbsp;''m''</sup>. Corpurile finite sunt adesea numite corpuri [[Évariste Galois|Galois]] și sunt notate cu GF(''p'') sau GF(''p''<sup>&nbsp;''m''</sup>).

Într-un astfel de corp cu ''m'' numere, fiecare element nenul ''a'' are un invers multiplicativ unic modulo m, ''a''<sup>−1</sup> astfel încât ''aa''<sup>−1</sup>&nbsp;=&nbsp;''a''<sup>−1</sup>''a''&nbsp;≡&nbsp;1&nbsp;mod&nbsp;''m''. Acest invers se poate găsi rezolvând ecuația ''ax''&nbsp;≡&nbsp;1&nbsp;mod&nbsp;''m'',<ref>Schroeder, pp. 107–109.</ref> sau ecuația diofantică liniară echivalentă<ref>Stillwell, pp. 186–187.</ref>

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

Această ecuație se poate rezolva cu ajutorul algoritmului lui Euclid, după cum s-a arătat mai sus. Găsirea inversului multiplicativ este un pas esențial în algoritmul [[RSA]], folosit pe scară largă în comerțul electronic; anume, ecuația determină întregul utilizat pentru a decripta mesajul.<ref>Schroeder, p. 134.</ref> Deși algoritmul RSA utilizează [[Inel (matematică)|inele]] și nu corpuri, se poate folosi algoritmul lui Euclid pentru găsirea inversului multiplicativ acolo unde el există. Algoritmul lui Euclid are și alte aplicații în [[Coduri corectoare de erori|codurile corectoare de erori]]; de exemplu, el se poate folosi ca alternativă la [[algoritmul Berlekamp–Massey]] pentru decodificarea codurilor [[Cod BCH|BCH]] și [[Cod Reed–Solomon|Reed–Solomon]], coduri bazate pe corpuri Galois.<ref>"Error correction coding: mathematical methods and algorithms", pagina 266, Todd K. Moon, John Wiley and Sons, 2005, ISBN 0-471-64800-0</ref>

=== Teorema chinezească a resturilor ===
Algoritmul lui Euclid se poate folosi pentru a rezolva și mai multe ecuații liniare diofantice.<ref>Rosen, pp. 143–170.</ref> Astfel de ecuații apar în [[teorema chinezească a resturilor]], care descrie o metodă nouă de reprezentare a unui întreg ''x''. În loc de a reprezenta un număr întreg prin cifrele sale, el se poate reprezenta prin resturile ''x''<sub>''i''</sub> ale împărțirii lui modulo o mulțime de ''N'' numere prime între ele ''m''<sub>''i''</sub>.<ref>Schroeder, pp. 194–195.</ref>

: ''x''<sub>1</sub> ≡ ''x'' mod ''m''<sub>1</sub>
: ''x''<sub>2</sub> ≡ ''x'' mod ''m''<sub>2</sub>
:…
: ''x''<sub>''N''</sub> ≡ ''x'' mod ''m''<sub>''N''</sub>

Scopul este determinarea lui ''x'' din cele ''N'' resturi ''x''<sub>''i''</sub>. Soluția se obține combinând mai multe ecuații într-o singură ecuație diofantică cu un modul ''M'' mult mai mare care este produsul tuturor modulelor individuale ''m''<sub>''i''</sub>, și definind ''M''<sub>''i''</sub>

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

Astfel, fiecare ''M''<sub>''i''</sub> este produsul tuturor modulelor ''cu excepția'' lui ''m''<sub>''i''</sub>. Soluția depinde de găsirea a ''N'' noi numere ''h''<sub>''i''</sub> astfel încât

:''M''<sub>''i''</sub>''h''<sub>''i''</sub> ≡ 1 mod ''m''<sub>''i''</sub>

Cu aceste numere ''h''<sub>''i''</sub>, orice întreg ''x'' se poate reconstitui din resturile ''x''<sub>''i''</sub> prin ecuația

: x ≡ (''x''<sub>1</sub>''M''<sub>1</sub>''h''<sub>1</sub> + ''x''<sub>2</sub>''M''<sub>2</sub>''h''<sub>2</sub> + … + ''x''<sub>''N''</sub>''M''<sub>''N''</sub>''h''<sub>''N''</sub> ) mod ''M''

Deoarece aceste numere ''h''<sub>''i''</sub> sunt inversele multiplicative ale numerelor ''M''<sub>''i''</sub>, ele se pot găsi folosind algoritmul lui Euclid așa cum s-a arătat în subsecțiunea anterioară.

=== Fracții continue ===
Algoritmul luo Euclid este în strânsă relație cu noțiunea de [[fracție continuă]].<ref name="Vinogradov_1954">{{citat carte | author = [[Ivan Matveyevich Vinogradov|Vinogradov IM]] | year = 1954 | title = Elements of Number Theory | publisher = Dover | location = New York | pages = 3–13}}</ref> Șirul de ecuații poate fi scris sub forma

:''a/b'' = ''q''<sub>0</sub> + ''r''<sub>0</sub>/''b''
:''b''/''r''<sub>0</sub> = ''q''<sub>1</sub> + ''r''<sub>1</sub>/''r''<sub>0</sub>
:''r''<sub>0</sub>/''r''<sub>1</sub> = ''q''<sub>2</sub> + ''r''<sub>2</sub>/''r''<sub>1</sub>
:…
:''r''<sub>''k''−2</sub>/''r''<sub>''k''−1</sub> = ''q''<sub>''k''</sub> + ''r''<sub>''k''</sub>/''r''<sub>''k''−1</sub>
:…
:''r''<sub>''N''−2</sub>/''r''<sub>''N''−1</sub> = ''q''<sub>''N''</sub>

Ultimul termen din partea dreaptă este întotdeauna egal cu inversul părții stângi din ecuația următoare. Astfel, primele două ecuații pot fi combinate formând

: ''a/b'' = ''q''<sub>0</sub> + 1/(''q''<sub>1</sub> + ''r''<sub>1</sub>/''r''<sub>0</sub>)

A treia ecuație poate fi folosită pentru a substitui termenul de la numitor ''r''<sub>1</sub>/''r''<sub>0</sub>, dând

: ''a/b'' = ''q''<sub>0</sub> + 1/(''q''<sub>1</sub> + 1/(''q''<sub>2</sub> + ''r''<sub>2</sub>/''r''<sub>1</sub>))

Raportul final al resturilor ''r''<sub>''k''</sub>/''r''<sub>''k''−1</sub> poate fi oricând înlocuit folosind următoarea ecuație din serie, până la ultima. Rezultatul este fracția continuă

:''a/b'' = ''q''<sub>0</sub> + 1/(''q''<sub>1</sub> + 1/(''q''<sub>2</sub> + 1/(… + 1/''q''<sub>N</sub>))…) = [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''N''</sub>]

În exemplul de mai sus, s-a calculat CMMDC(1071, 462), iar câturile ''q''<sub>''k''</sub> erau 2, 3 și respectiv 7. Deci fracția 1071/462 poate fi scrisă sub forma

: 1071/462 = 2 + 1/(3 + 1/7) = [2; 3, 7]

după cum confirmă și calculele.

=== Algoritmii de factorizare ===
Calculul celui mai mare divizor comun este un pas esențial în mai mulți algoritmi de [[Factorizarea întregilor|factorizare a întregilor]],<ref>{{citat carte | author = Crandall R, Pomerance C | year = 2001 | title = Prime Numbers: A Computational Perspective | edition = 1st | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-94777-9 | pages = 225–349}}</ref> cum ar fi [[Pollard's rho algorithm]],<ref>Knuth, pp. 369–371.</ref> [[algoritmul lui Shor]],<ref>{{cite journal | author = [[Peter Shor|Shor PW]] | year = 1997 | title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | journal = SIAM J. Sci. Statist. Comput. | volume = 26 | pages = 1484}}</ref> [[metoda de factorizare a lui Dixon]]<ref>{{cite journal | author = Dixon JD | year = 1981 | title = Asymptotically fast factorization of integers | journal = Math. Comput. | volume = 36 | pages = 255–260 | doi = 10.2307/2007743}}</ref> și [[factorizarea Lenstra cu curbe eliptice]].<ref>{{cite journal | author = [[Hendrik Lenstra|Lenstra Jr. HW]] | year = 1987 | title = Factoring integers with elliptic curves | journal = Annals of Mathematics | volume = 126 | pages = 649–673 | doi = 10.2307/1971363}}</ref> Algoritmul lui Euclid poate fi utilizat eficient pentru găsirea CMMDC în aceste cazuri. [[Factorizarea cu fracții continue]] utilizează fracțiile continue, determinate folosind algoritmul lui Euclid.<ref>Knuth, pp. 380–384.</ref>

== Eficiența algoritmului ==
[[Fișier:Euclidean algorithm running time X Y.png|thumb|Numărul de pași din algoritmul lui Euclid pentru CMMDC(x,y). Punctele roșii indică pași relativ puțini (viteză mare), iar punctele galbene, verzi și albastre indică un număr din ce în ce mai mare de pași (viteză scăzută).]]

Eficiența computațională a algoritmului lui Euclid a fost mult studiată.<ref>Knuth, pp. 339–364.</ref> Această eficiență poate fi descrisă de numărul de pași ai algoritmului înmulțit cu costul computațional al fiecărui pas. După cum a arătat [[Gabriel Lamé]] pentru prima oară în 1844,<ref>{{cite journal | author = [[Gabriel Lamé|Lamé G]] | year = 1844 | title = Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers | journal = Comptes Rendus Acad. Sci. | volume = 19 | pages = 867–870}}</ref> numărul de pași necesar pentru terminarea calculului nu este niciodată mai mare decât numărul ''h'' de cifre (în baza 10) al celui mai mic număr.<ref>{{cite journal | author = Grossman H | year = 1924 | title = On the Number of Divisions in Finding a G.C.D. | journal = The American Mathematical Monthly | volume = 31 | page = 443 | doi = 10.2307/2298146}}</ref><ref>{{citat carte | author = Honsberger R | year = 1976 | title = Mathematical Gems II | publisher = The [[Mathematical Association of America]] | isbn = 0-88385-302-7 | pages = 54–57}}</ref> Întrucât costul computațional al fiecărui pas este și el de ordinul lui ''h'', costul total crește ca&nbsp;''h''<sup>2</sup>.

=== Numărul de pași ===
Numărul de pași necesari pentru calculul CMMDC a două numere naturale, ''a'' și ''b'', se poate nota cu ''T''(''a'',&nbsp;''b'').<ref name="Knuth, p. 344">Knuth, p. 344.</ref> Dacă ''g'' este CMMDC al lui ''a'' și ''b'', atunci ''a''&nbsp;=&nbsp;''mg'' și ''b''&nbsp;=&nbsp;''ng'' pentru două numere ''m'' și ''n'' prime între ele. Atunci

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

după cum se poate vedea împărțind toți pașii din algoritmul lui Euclid la ''g''.<ref>Ore, p. 45.</ref> După același argument, numărul de pași rămâne același dacă ''a'' și ''b'' sunt înmulțiți cu un factor comun ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb''). De aceea, numărul ''T'' de pași poate varia dramatic între perechi foarte apropiate de numere, cum ar fi T(''a'', ''b'') și T(''a'',&nbsp;''b''&nbsp;+&nbsp;1), în funcție de cât de mare este CMMDC în fiecare caz.

Natura recursivă a algoritmului lui Euclid dă o altă ecuație:

: ''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

unde se presupune că ''T''(''x'', 0)&nbsp;=&nbsp;0.<ref name="Knuth, p. 344"/>

==== Numărul maxim de pași ====
Dacă algoritmul lui Euclid se execută în ''N'' pași pentru două numere naturale ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0, cele mai mici valori ale lui ''a'' și ''b'' pentru care acest lucru este adevărat sunt numerele Fibonacci ''F''<sub>''N''+2</sub> respectiv ''F''<sub>''N''+1</sub>.<ref name="Knuth, p. 343">Knuth, p. 343.</ref> Aceasta se poate arăta prin [[Inducție matematică|inducție]].<ref>Mollin, p. 21.</ref> Dacă ''N''&nbsp;=&nbsp;1, ''b'' divide ''a''; cele mai mici numere naturale pentru care acest lucru este adevărat sunt ''b''&nbsp;=&nbsp;1 și ''a''&nbsp;=&nbsp;2, care sunt ''F''<sub>2</sub> și respectiv ''F''<sub>3</sub>. Se presupune că rezultatul este valabil pentru toate valorile lui ''N'' până la ''M'' − 1. Primul pas al algoritmului de ''M'' pași este ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>, iar al doilea pas este ''b''&nbsp;=&nbsp;''q''<sub>1</sub>''r''<sub>0</sub>&nbsp;+&nbsp;''r''<sub>1</sub>. Algoritmul fiind recursiv, el a rulat ''M''−1 pași pentru a găsi CMMDC(''b'',&nbsp;''r''<sub>0</sub>) iar valorile lor cele mai mici sunt ''F''<sub>''M''+1</sub> și ''F''<sub>''M''</sub>. Cea mai mică valoare a lui ''a'' este deci cea cu ''q''<sub>0</sub>&nbsp;=&nbsp;1, de unde ''a''&nbsp;=&nbsp;''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;=&nbsp;''F''<sub>''M''+1</sub>&nbsp;+&nbsp;''F''<sub>''M''</sub>&nbsp;=&nbsp;''F''<sub>''M''+2</sub>. Această demonstrație, publicată de Gabriel Lamé în 1844, reprezintă începuturile [[Teoria complexității|teoriei complexității computaționale]],<ref>LeVeque, p. 35.</ref> fiind și prima aplicație practică a șirului lui Fibonacci.<ref name="Knuth, p. 343"/>

Acest rezultat este suficient pentru a arăta că numărul de pași din algoritmul lui Euclid nu poate fi niciodată mai mare decât de cinci ori numărul cifrelor sale (în bază 10).<ref>Mollin, pp. 21–22.</ref> Dacă algoritmul rulează în ''N'' pași, atunci ''b'' este mai mare sau egal cu ''F''<sub>''N''+1</sub> care este mai mare sau egal cu ''φ''<sup>''N''</sup>, unde ''φ'' este [[raportul de aur]]. Cum ''b''&nbsp;>&nbsp;''φ''<sup>''N''</sup>, atunci ''N''&nbsp;<&nbsp;log<sub>''φ''</sub>''b''. Întrucât log<sub>10</sub>''φ''&nbsp;>&nbsp;1/5, ''N''/5&nbsp;<&nbsp;log<sub>10</sub>''φ''&nbsp;log<sub>''φ''</sub>''b''&nbsp;=&nbsp;log<sub>10</sub>''b''. Astfel, ''N''&nbsp;<&nbsp;5&nbsp;log<sub>10</sub>''b''. Deci, algoritmul lui Euclid are nevoie întotdeauna de mai puțin decât [[Notația Big O|''O''(''h'')]] împărțiri, unde ''h'' este numărul de cifre al celui mai mic număr ''b''.

==== Numărul mediu de pași ====
Numărul mediu de pași al algoritmului lui Euclid a fost definit în trei moduri diferite. Prima definiție este timpul mediu ''T''(''a'') necesar pentru a calcula CMMDC al unui număr ''a'' și al unui număr mai mic ''b'' ales cu probabilitate egală dintre întregii dintre 0 și ''a''&nbsp;−&nbsp;1<ref name="Knuth, p. 344"/>

:<math>
T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b).
</math>

Deoarece ''T''(''a'',&nbsp;''b'') fluctuează dramatic cu CMMDC a celor două numere, însă, funcția ''T''(''a'') este afectată de „zgomote”.<ref>Knuth, p. 353.</ref>

Pentru a reduce aceste zgomote, se face o a doua medie τ(''a'') peste toate numerele prime cu ''a''

:<math>
\tau(a) = \frac{1}{\varphi(a)} \sum_{0 \leq b<a, \mathrm{GCD}(a, b) = 1} T(a, b).
</math>

Există ''φ''(''a'') numere întregi prime cu ''a'' și mai mici decât acesta, unde ''φ'' este [[indicatorul lui Euler]]. Această medie tau crește uniform cu ''a''<ref>Knuth, p. 357.</ref><ref>{{cite journal | author = Tonkov T | year = 1974 | title = On the average length of finite continued fractions | journal = Acta arithmetica | volume = 26 | pages = 47–57}}</ref>

:τ(''a'') = (12/π<sup>2</sup>) ln 2 ln a + ''C'' + [[Notația Big O|''O''(''a''<sup>−(1/6) + ε</sup>)]]

cu eroarea reziduală de ordinul lui ''a''<sup>−(1/6) + ε</sup>, unde ε este [[infinitezimal]]. Constanta ''C'' din această formulă este egală cu

:''C'' = −(1/2) + 6 (ln 2/π<sup>2</sup>)( 4γ − 24π<sup>2</sup>ζ&nbsp;'(2) + 3 ln 2 − 2) ≈ 1.467

unde γ este [[constanta Euler–Mascheroni]] iar ζ' este [[Derivare|derivata]] [[Funcția zeta Riemann|funcției zeta Riemann]].<ref>{{cite journal | author = Porter JW | year = 1975 | title = On a Theorem of Heilbronn | journal = Mathematika | volume = 22 | pages = 20–28}}</ref><ref>{{cite journal | author = Knuth DE | year = 1976 | title = Evaluation of Porter's Constant | journal = Computers and Mathematics with Applications | volume = 2 | pages = 137–139 | doi = 10.1016/0898-1221(76)90025-0}}</ref> Coeficientul dominant (12/π<sup>2</sup>) ln 2 a fost determinat prin două metode independente.<ref>{{cite journal | author = Dixon JD | year = 1970 | title = The Number of Steps in the Euclidean Algorithm | journal = J. Number Theory | volume = 2 | pages = 414–422 | doi = 10.1016/0022-314X(70)90044-2}}</ref><ref>{{citat carte | author = Heilbronn HA | year = 1969 | chapter = On the Average Length of a Class of Finite Continued Fractions | title = Number Theory and Analysis | editor = Paul Turán | publisher = Plenum | location = New York | id = {{LCCN|68|00|8991}} | pages = 87–96}}</ref>

Întrucât prima medie se poate calcula din media tau prin sumă peste divizorii ''d'' ai lui&nbsp;''a''<ref>Knuth, p. 354.</ref>

:<math>
T(a) = \frac{1}{a} \sum_{d | a} \varphi(d) \tau(d)
</math>

ea poate fi aproximată prin formula<ref name="Norton_1990">{{cite journal | author = Norton GH | year = 1990 | title = On the Asymptotic Analysis of the Euclidean Algorithm | journal = Journal of Symbolic Computation | volume = 10 | pages = 53–58 | doi = 10.1016/S0747-7171(08)80036-3}}</ref>

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

unde Λ(''d'') este [[Funcția von Mangoldt|funcția Mangoldt]].<ref>Knuth, p. 355.</ref>

O a treia medie ''Y''(''n'') este definită ca numărul mediu de pași necesar atunci când ''a'' și ''b'' sunt ambele alese aleator (cu distribuție uniformă) între 1 și ''n''<ref name="Norton_1990" />

:<math>
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>

Înlocuind formula aproximativă pentru ''T''(''a'') în această ecuație rezultă o estimare a lui ''Y''(''n'')<ref>Knuth, p. 356.</ref>

:''Y''(''n'') ≈ (12/π<sup>2</sup>) ln 2 ln ''n'' + 0.06.

=== Costul computațional al unui pas ===
La fiecare pas ''k'' al algoritmului lui Euclid, se calculează câtul ''q''<sub>''k''</sub> și restul ''r''<sub>''k''</sub> pentru o pereche dată de întregi ''r''<sub>''k''−2</sub> și ''r''<sub>''k''−1</sub>

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>.

Costul computațional al fiecărui pas este asociat cu găsirea lui ''q''<sub>''k''</sub>, întrucât restul ''r''<sub>''k''</sub> poate fi calculat rapid din ''r''<sub>''k''−2</sub>, ''r''<sub>''k''−1</sub>, and ''q''<sub>''k''</sub>

: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>.

Costul computațional al împărțirii numerelor pe ''h'' biți scalează ca ''O''(''h''(''ℓ''+1)), unde ''ℓ'' este lungimea câtului.<ref>Knuth, pp. 257–261.</ref>

Pentru comparație, algoritmul original al lui Euclid bazat pe scăderi poate fi mult mai lent. O singura împărțire de întregi este echivalentă cu ''q'' scăderi (''q'' este câtul împărțirii). Dacă raportul ''a'' supra ''b'' este foarte mare, și câtul este mare și este nevoie de multe scăderi. Pe de altă parte, s-a arătat că sunt șanse mari ca aceste câturi să fie numere întregi mici. Probabilitatea ca un cât dat să aibă o anumită valoare ''q'' este aproximativ ln|''u''/(''u''&nbsp;−&nbsp;1)| unde ''u''&nbsp;=&nbsp;(''q''&nbsp;+&nbsp;1)<sup>2</sup>.<ref>Knuth, p. 352.</ref> Pentru ilustrare, probabilitatea ca la împărțire să rezulte câtul 1, 2, 3, sau 4 este aproximativ 41,5%, 17,0%, 9,3%, respectiv 5,9%. Întrucât operația de scădere este mai rapidă decât cea de împărțire, mai ales în cazul numerelor mari,<ref>{{citat carte | author = Wagon S | year = 1999 | title = Mathematica in Action | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-98252-3 | pages = 335–336}}</ref> algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri.<ref>Cohen, p. 14.</ref> Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid.<ref>Cohen, pp. 14–15, 17–18.</ref>

Combinarea numărului estimat de pași cu calculul computațional estimat al fiecărui pas arată că algoritmul lui Euclid are o creștere pătratică (''h''<sup>2</sup>) în funcție de numărul de cifre ''h'' al celor două numere inițiale ''a'' și ''b''. Fie ''h''<sub>0</sub>, ''h''<sub>1</sub>, …, ''h''<sub>''N''−1</sub> numărul de cifre ale resturilor succesive ''r''<sub>0</sub>,&nbsp;''r''<sub>1</sub>,&nbsp;…,&nbsp;''r''<sub>''N''−1</sub>. Cum numărul de pași ''N'' crește liniar cu ''h'', timpul de execuție este limitat de

:<math>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>

=== Eficiența unor metode alternative ===
Algoritmul lui Euclid este folosit pe scară largă în practică, mai ales pentru numere mici, datorită simplității sale. Pentru comparație, se poate determina eficiența unor alternative la algoritmul lui Euclid.

O abordare ineficientă a găsirii CMMDC a două numere naturale ''a'' și ''b'' este de a le calcula toți divizorii comuni; CMMDC este, atunci, cel mai mare dintre aceștia. Divizorii comuni se pot găsi împărțind succesiv ambele numere la numerele de la 2 la cel mai mic dintre cele două, ''b''. Numărul de pași al acestei abordări crește liniar cu ''b'', sau exponențial cu numărul de cifre. O altă abordare ineficientă este găsirea factorilor primi ai unuia sau ai ambelor numere. Așa cum se arată [[#Cel mai mare divizor comun|mai sus]], CMMDC este egal cu produsul factorilor primi comuni ai celor două numere ''a'' și ''b''.<ref name="Schroeder_21" /> Metodele actuale de [[Factorizarea întregilor|factorizare]] sunt și ele ineficiente; multe alte sisteme criptografice se bazează tocmai pe această ineficiență.<ref name="Schroeder_216" />

Algoritmul CMMDC binar este o alternativă eficientă care înlocuiește împărțirea cu operații mai rapide, exploatând reprezentările binare utilizate de calculatoare.<ref>Knuth, pp. 321–323.</ref><ref>{{cite journal | author = Stein J | year = 1967 | title = Computational problems associated with Racah algebra | journal = Journal of Computational Physics | volume = 1 | pages = 397–405 | doi = 10.1016/0021-9991(67)90047-2}}</ref> Această alternativă, însă, scalează și ea ca [[Notația Big O|''O''(''h''²)]]. Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel ca algoritmul lui Euclid.<ref name="Crandall_2001">{{citat carte | author = Crandall R, Pomerance C | year = 2001 | title = Prime Numbers: A Computational Perspective | edition = 1st | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-94777-9 | pages = 77–79, 81–85, 425–431}}</ref> Eficiența se poate îmbunătăți examinând doar primele cifre ale numerelor ''a'' și ''b''.<ref>Knuth, p. 328.</ref><ref>{{cite journal | author = Lehmer DH | year = 1938 | title = Euclid's Algorithm for Large Numbers | journal = The American Mathematical Monthly | volume = 45 | pages = 227–233 | doi = 10.2307/2302607}}</ref> Algoritmul binar poate fi extins la alte baze (algoritmi k-ari)<ref>{{cite journal | author = Sorenson J | year = 1994 | title = Two fast GCD algorithms | journal = J. Algorithms | volume = 16 | pages = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref>, cu creșteri ale vitezei de până la cinci ori.<ref>{{cite journal | author = Weber K | year = 1995 | title = The accelerated GCD algorithm | journal = ACM Trans. Math. Soft. | volume = 21 | pages = 111–122 | doi = 10.1145/200979.201042}}</ref>

O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici,<ref>{{citat carte | author = Aho A, Hopcroft J, Ullman J | year = 1974 | title = The Design and Analysis of Computer Algorithms | publisher = Addison–Wesley | location = New York | pages = 300–310}}</ref> cum ar fi cel al lui Schönhage<ref>{{cite journal | author = Schönhage A | title = Schnelle Berechnung von Kettenbruchentwicklungen | journal = Acta Informatica | volume = 1 | pages = 139–144 | doi = 10.1007/BF00289520 | year = 1971}}</ref><ref>{{citat carte | author = Cesari G | year = 1998 | chapter = Parallel implementation of Schönhage's integer GCD algorithm | title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR | editor = G. Buhler | publisher = [[Springer-Verlag]] | location = New York | pages = 64–76}} Volume 1423 in ''Lecture notes in Computer Science''.</ref> și cel al lui Stehlé și Zimmermann.<ref>{{citat carte | author = Stehlé D, Zimmermann P | year = 2005 | chapter = Gal’s accurate tables method revisited | title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) | publisher = [[IEEE Computer Society Press]] | location = Los Alamitos, CA}}</ref> Acești algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată [[#Metoda matriceală|mai sus]]. Aceste metode subcuadratice scalează în general ca {{nowrap|''O''(''h'' (log ''h'')<sup>2</sup> (log log ''h'')).}}<ref name="Crandall_2001" /><ref>{{cite journal | author = Möller N | title = [http://www.lysator.liu.se/~nisse/archive/sgcd.pdf On Schönhage's algorithm and subquadratic integer gcd computation] | journal = Mathematics of Computation | volume = 77 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008}}</ref>

== Alte sisteme de numere ==
După cum s-a descris mai sus, algoritmul lui Euclid este folosit pentru a găsi cel mai mare divizor comun a două numere naturale (numere întregi pozitive). Acesta poate fi, însă, generalizat la numere reale, și la sisteme de numere mai exotice, cum ar fi [[Polinom|polinoamele]], [[Întreg cuadratic|întregii cuadratici]] și [[cuaternionii Hurwitz]]. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare numerelor prime. Unicitatea factorizării este esențială în multe demonstrații din teoria numerelor.

=== Numere reale și raționale ===
Algoritmul lui Euclid se poate aplica și [[Număr real|numerelor reale]], așa cum arată Euclid în Cartea 10 din ''[[Elementele lui Euclid|Elementele]]''. Scopul algoritmului este identificarea unui număr real ''g'' astfel încât două numere reale, ''a'' și ''b'', sunt multipli întregi ai acestuia: ''a'' = ''mg'' și ''b'' = ''ng'', unde ''m'' și ''n'' sunt [[Număr întreg|întregi]].<ref name="Weil_1983" /> Această identificare este echivalentă cu găsirea unei relații întregi între două numere reale ''a'' și ''b''; adică, ea determină întregii ''s'' și ''t'' astfel încât ''sa'' + ''tb'' = 0. Euclid folosește acest algoritm pentru a trata chestiunea lungimilor incomensurabile.<ref>{{citat carte | author = Boyer CB, Merzbach UC | year = 1991 | title = A History of Mathematics | edition = 2nd | publisher = Wiley | location = New York | isbn = 0-471-54397-7 | pages = 116–117}}</ref><ref>{{citat carte | author = [[Florian Cajori|Cajori F]] | year = 1894 | title = A History of Mathematics | publisher = Macmillan | location = New York | page = 70}}</ref>

Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile ''r''<sub>''k''</sub> sunt numere reale, deși câturile ''q''<sub>''k''</sub> sunt, ca și mai înainte, întregi. Al doilea este că algoritmul nu este garantat că se termină într-un număr finit ''N'' de pași. Dacă se termină, atunci fracția ''a''/''b'' este un număr rațional, adică este raportul a două numere întregi

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

și poate fi scris ca fracție continuă finită [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''N''</sub>]. Dacă algoritmul nu se oprește, atunci fracția ''a''/''b'' este un [[număr irațional]] și poate fi descris de o fracție continuă infinită [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …]. Exemple de fracții continue infinite sunt [[raportul de aur]] ''φ'' = [1; 1, 1, …] și [[radical din 2|rădăcina pătrată a lui 2]], √2 = [1; 2, 2, …]. În general, algoritmul nu se oprește, întrucât aproape toate rapoartele ''a''/''b'' de două numere reale sunt iraționale.

O fracție continuă infinită poate fi trunchiată la un pas ''k'' [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''k''</sub>] pentru a da o aproximație a raportului ''a''/''b'', aproximație ce e cu atât mai bună cu cât ''k'' este mai mare. Aproximația este descrisă de convergenții ''m''<sub>''k''</sub>/''n''<sub>''k''</sub>; numărătorul și numitorul sunt prime între ele și respectă relația recursivă

:''m''<sub>''k''</sub> = ''q''<sub>''k''</sub> ''m''<sub>''k''−1</sub> + ''m''<sub>''k''−2</sub>
:''n''<sub>''k''</sub> = ''q''<sub>''k''</sub> ''n''<sub>''k''−1</sub> + ''n''<sub>''k''−2</sub>

unde ''m''<sub>−1</sub> = ''n''<sub>−2</sub> = 1 și ''m''<sub>−2</sub> = ''n''<sub>−1</sub> = 0 sunt valorile inițiale. Convergentul ''m''<sub>''k''</sub>/''n''<sub>''k''</sub> este cea mai bună aproximație rațională a lui ''a''/''b'' cu numitorul ''n''<sub>''k''</sub>:

:<math alt="Modul de diferența a două rapoarte (a supra b minus m indice k supra n indice k) este mai mică decât unu supra n indice k pătrat."> 
\left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.
</math>

=== Polinoame ===
Polinoamele de o singură variabilă ''x'' se pot aduna, înmulți și descompune în polinoame ireductibile, structuri analoage numerelor prime din mulțimea numerelor întregi. Cel mai mare divizor comun ''g''(''x'') al două polinoame ''a''(''x'') și ''b''(''x'') este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid.<ref name="Lang_1984" >{{citat carte | author = [[Serge Lang|Lang S]] | year = 1984 | title = Algebra | edition = 2nd | publisher = Addison–Wesley | location = Menlo Park, CA | isbn = 0-201-05487-6 | pages = 190–194}}</ref> Procedura de bază este similară cu cea de la întregi. La fie care pas ''k'', se calculează un polinom cât ''q''<sub>''k''</sub>(''x'') și un polinom rest ''r''<sub>''k''</sub>(''x'') care satisfac ecuația recursivă

: ''r''<sub>''k''−2</sub>(''x'') = ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k''−1</sub>(''x'') + ''r''<sub>''k''</sub>(''x'')

unde ''r''<sub>−2</sub>(''x'')&nbsp;=&nbsp;''a''(''x'') și ''r''<sub>−1</sub>(''x'')&nbsp;=&nbsp;''b''(''x''). Polinomul cât este ales astfel încât termenul dominant al lui ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k''−1</sub>(''x'') să fie egal cu termenul dominant al lui ''r''<sub>''k''−2</sub>(''x''); aceasta asigură că gradul fiecărui rest este mai mic decât gradul predecesorului său grad[''r''<sub>''k''</sub>(''x'')] < grad[''r''<sub>''k''−1</sub>(''x'')]. Întrucât gradul este un număr întreg nenegativ, și întrucât el scade la fiecare pas, algoritmul lui Euclid se încheie într-un număr finit de pași. Ultimul rest nenul este cel mai mare divizor comun al celor două polinoame inițiale, ''a''(''x'') și ''b''(''x'').<ref>Cox, pp. 37–46.</ref>

De exemplu, fie următoarele [[polinom|polinoame]] de [[gradul unui polinom|gradul]] patru, care fiecare se descompune în două polinoame de gradul doi:

: ''a''(''x'') = ''x''<sup>4</sup> − 4''x''<sup>3</sup> + 4 ''x''<sup>2</sup> − 3''x'' + 14 = (''x''<sup>2</sup> − 5''x'' + 7)(''x''<sup>2</sup> + ''x'' + 2)

și

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

Împărțind pe ''a''(''x'') la ''b''(''x'') rezultă un rest ''r''<sub>0</sub>(''x'') = ''x''<sup>3</sup> + (2/3) ''x''<sup>2</sup> + (5/3) ''x'' − (2/3). În pasul următor, ''b''(''x'') se împarte la ''r''<sub>0</sub>(''x'') rezultând restul ''r''<sub>1</sub>(''x'') = ''x''<sup>2</sup> + ''x'' + 2. Împărțind, apoi, ''r''<sub>0</sub>(''x'') la ''r''<sub>1</sub>(''x'') rezultă un rest nul, indicând că ''r''<sub>1</sub>(''x'') este cel mai mare divizor comun al lui ''a''(''x'') și ''b''(''x''), consistent cu factorizarea acestora.

Multe dintre aplicațiile descrise mai sus pentru numere întregi sunt valabile și pentru polinoame.<ref>Schroeder, pp. 254–259.</ref> Algoritmul lui Euclid se poate folosi pentru rezolvarea de ecuații liniare diofantice și de probleme chinezești ale resturilor pentru polinoame; se pot defini și fracții continue de polinoame.

Algoritmul lui Euclid polinomial are și alte aplicații proprii, cum ar fi [[lanț Sturm|lanțurile Sturm]], o tehnică de numărare a rădăcinilor reale ale polinoamelor într-un interval dat de pe [[axa numerelor|axa numerelor reale]]. Aceasta are aplicații în mai multe zone, cum ar fi [[criteriul de stabilitate Routh–Hurwitz]] din [[teoria sistemelor]].

În cele din urmă, coeficienții polinoamelor nu sunt obligatoriu numere întregi, reale, și nici măcar complexe. De exemplu, coeficienții pot fi din orice [[Corp (matematică)|corp]], cum ar fi corpurile finite GF(''p'') descrise mai sus. Concluziile corespunzătoare despre algoritmul lui Euclid și despre aplicațiile acestuia sunt valabile chiar și pentru asemenea polinoame.<ref name="Lang_1984" />

=== Întregii gaussieni ===
[[Fișier:Gaussian primes.svg|thumb|Distribuția numerelor prime gaussiene ''u''&nbsp;+&nbsp;''vi'' în planul complex, cu norma ''u''<sup>2</sup>&nbsp;+&nbsp;''v''<sup>2</sup> mai mică decât 500]]

Întregii gaussieni sunt [[Număr complex|numere complexe]] de forma α&nbsp;=&nbsp;''u''&nbsp;+&nbsp;''vi'', unde ''u'' și ''v'' sunt numere întregi obișnuite și ''i'' este unitatea imaginară.<ref name="Stillwell_2003" /> Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o factorizare unică, conform demonstrației [[#Identitatea lui Bézout|de mai sus]].<ref name="Gauss_1832">{{cite journal | author = [[Carl Friedrich Gauss|Gauss CF]] | date = 1832 | title = Theoria residuorum biquadraticorum | journal = Comm. Soc. Reg. Sci. Gött. Rec. | volume = 4}} Vezi și ''Werke'', '''2''':67–148.</ref> Unicitatea factorizării este utilă în mai multe aplicații, cum ar fi calculul tuturor [[Numere pitagoreice|tripletelor pitagoreice]] sau demonstrația [[Prima teoremă a lui Fermat a sumei a două pătrate|Primei teoreme a lui Fermat a sumei a două pătrate]].<ref name="Stillwell_2003">{{citat carte | author = [[John Stillwell|Stillwell J]] | year = 2003 | title = Elements of Number Theory | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-95587-9 | pages = 101–116}}</ref> În general, algoritmul lui Euclid este unul convenabil în asemenea aplicații, dar nu este indispensabil; de exemplu, teoremele pot fi adesea demonstrate prin alte metode.

Algoritmul lui Euclid dezvoltat pentru două numere întregi gaussiene α și β este aproape același ca și pentru numerele întregi; el se îndepărtează de acesta din urmă în două aspecte. Ca și înainte, la fiecare pas ''k'' trebuie identificat un cât ''q''<sub>''k''</sub> și un rest ''r''<sub>''k''</sub> astfel încât

: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>

unde ''r''<sub>''k''−2</sub>&nbsp;=&nbsp;α, ''r''<sub>''k''−1</sub>&nbsp;=&nbsp;β, și fiecare rest este strict mai mic decât predecesorul său, |''r''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''−1</sub>|. Prima diferență este aceea că resturile și câturile sunt și ele numere întregi gaussiene, și deci [[Număr complex|complexe]]. Câturile ''q''<sub>''k''</sub> sunt în general găsite prin rotunjirea părților reală și imaginară a raportului exact (cum ar fi numărul complex α/β) la cel mai apropiat întreg. A doua diferență constă în necesitatea definirii modului în care un rest complex poate fi considerat a fi „mai mic” decât altul. Pentru aceasta, se definește o [[normă (matematică)|funcție normă]] ''f''(''u'' + ''v''i) = ''u''<sup>2</sup> + ''v''<sup>2</sup>, care transformă fiecare întreg gaussian ''u'' + ''vi'' la un număr întreg. După fiecare pas ''k'' al algoritmului lui Euclid, norma restului ''f''(''r''<sub>''k''</sub>) este mai mică decât norma restului precedent, ''f''(''r''<sub>''k''−1</sub>). Norma fiind un întreg nenegativ și scăzând la fiecare pas, algoritmul lui Euclid pentru întregi gaussieni se termină într-un număr finit de pași. Ultimul rest nenul este CMMDC(α,β), întregul gaussian cu norma cea mai mare și care se împarte exact la α și la β; el rămâne aceleași și după înmulțirea numărului cu o unitate, ±1 sau ±''i''.

Multe dintre celelalte aplicații ale algoritmului lui Euclid sunt valabile și pentru întregii gaussieni. De exemplu, el se poate folosi pentru a rezolva ecuații liniare diofantice și probleme chinezești ale resturilor pentru aceste numere; se pot defini și fracții continue de întregi gaussieni.

=== Inele euclidiene ===
O mulțime de elemente împreună cu doi operatori binari, + și ·, se numește [[inel euclidian]] dacă formează un [[inel comutativ]] ''R'' și dacă pe această mulțime se poate executa un algoritm al lui Euclid modificat.<ref>Stark, p. 290.</ref><ref>Cohn, pp. 104–105.</ref> Cele două operații ale unui astfel de inel nu trebuie neapărat să fie adunarea și înmulțirea din aritmetica obișnuită; ele pot fi mai generale, cum sunt operațiile de pe un [[Grup (matematică)|grup]] sau de pe un [[monoid]]. Cu toate acestea, aceste operații generale trebuie să respecte multe legi ce guvernează și aritmetica obișnuită, cum ar fi de exemplu [[commutativitate]]a, [[asociativitate]]a și [[distributivitat]]e.

Algoritmul lui Euclid generalizat are nevoie de o ''funcție euclidiană'', respectiv de o transformare ''f'' de la ''R'' la mulțimea numerelor întregi nenegative cu proprietatea că, pentru două elemente nenule ''a'' și ''b'' din ''R'', există ''q'' și ''r'' în ''R'' cu proprietatea că ''a'' = ''qb'' + ''r'' și ''f''(''r'') < ''f''(''b''). Un exemplu de astfel de funcție este funcția normă utilizată pentru a ordona numerele întregi gaussiene [[#Întregii gaussieni|ca mai sus]]. Funcția ''f'' poate fi modulul numărului, sau [[gradul polinomului]]. Principiul de bază este acela că la fiecare pas al algoritmului, ''f'' se reduce; astfel, dacă ''f'' poate fi redus doar de un număr finit de ori, algoritmul trebuie să se termine într-un număr finit de pași. Acest principiu se bazează pe ordonarea naturală și pe existența unui număr natural minim.

[[Teorema fundamentală a aritmeticii]] se aplică pe orice inel euclidian: orice element dintr-un inel euclidian poate fi factorizat în mod unic în elemente ireductibile. Orice inel euclidian este un domeniu de factorizare unică, deși reciproca nu este adevărată întotdeauna. Inelele euclidiene sunt o submulțime a domeniilor CMMDC, domenii în care există întotdeauna un cel mai mic divizor comun al două elemente. Cu alte cuvinte, poate exista un cel mai mare divizor comun (pentru toate elementele dintr-un inel), deși s-ar putea ca acesta să nu poată fi găsit cu ajutorul algoritmului lui Euclid. Un inel euclidian este întotdeauna un {{ill-wd| Q1143969||domeniu cu ideale principale}}, [[domeniu de integritate]] în care fiecare [[ideal (teoria inelelor)|ideal]] este un [[ideal principal]]. Din nou, reciproca nu este adevărată: nu orice astfel de domeniu este inel euclidian.

Unicitatea factorizării în inelele euclidiene este utilă în mai multe aplicații. De exemplu, unicitatea factorizării întregilor gaussieni este convenabilă la calculul formulelor pentru toate tripletele pitagoreice și la demonstrarea teoremei lui Fermat privind suma a două pătrate.<ref name="Stillwell_2003" /> Unicitatea factorizării este și element cheie într-o tentativă de demonstrare a [[Ultima teoremă a lui Fermat|Ultimei teoreme a lui Fermat]] publicată în 1847 de Gabriel Lamé, același matematician care analizase eficiența algoritmului lui Euclid, pe baza unei sugestii a lui [[Joseph Liouville]].<ref>{{cite journal | author = Lamé G | year = 1847 | title = 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 | journal = J. Math. Pures Appl. | volume = 12 | pages = 172–184}}</ref> Abordarea lui Lamé impunea unicitatea factorizării numerelor de forma ''x'' + ω''y'', unde ω = ''e''<sup>2''i''π/''n''</sup> este rădăcina de ordin ''n'' a lui 1, adică, ω<sup>''n''</sup> = 1. Deși această abordare are succes pentru anumite valori ale lui ''n'' (cum ar fi ''n''=3, [[întregii Eisenstein]]), în general, asemenea numere ''nu'' au o factorizare unică. Această neunicitate a factorizărilor din unele corpuri ciclotomice l-a condus pe [[Ernst Kummer]] la conceptul de [[număr ideal]] și, mai apoi, pe [[Richard Dedekind]] la cel de [[ideal (teoria inelelor)|ideal]].

==== Unicitatea factorizării întregilor cuadratici ====

[[Fișier:Eisenstein primes.svg|thumb|Distribuția numerelor prime Eisenstein ''u''&nbsp;+&nbsp;''v''ω în planul complex, cu norma mai mică decât 500. Numărul ω este o rădăcină cubică a unității.]]

Întregii cuadratici pot fi un exemplu de inel euclidian. Întregii cuadratici sunt o generalizare a conceptului de întregi gaussieni în care [[unitatea imaginară]] ''i'' este înlocuită de un număr ω. Astfel, ele au forma ''u'' + ''v'' ω, unde ''u'' și ''v'' sunt numere întregi, iar ω are una dintre două forme posibile, în funcție de parametrul ''D''. Dacă ''D'' nu este egal cu un multiplu de patru plus unu (cum ar fi 5, 17, sau −19), atunci

: ω = √D.

Altfel,

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

Dacă funcția ''f'' corespunde unei funcții normă, cum ar fi cea utilizată la sortarea întregilor gaussieni, atunci inelul unor astfel de numere este euclidian doar pentru o mulțime finită de valori ale lui ''D'': ''D''&nbsp;=&nbsp;−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 sau 73.<ref name="Cohn_1962" /> Întregii cuadratici cu ''D''&nbsp;=&nbsp;−1 și −3 sunt [[întregi gaussieni]], respectiv [[întregi Eisenstein]].

Dacă ''f'' poate fi orice funcție euclidiană atunci lista de valori posibile ale lui ''D'' pentru care inelul este euclidian nu este cunoscută.<ref name="Clark_1994">{{cite journal | author = Clark DA | year = 1994 | title = [http://www.springerlink.com/content/6t9u2440402n1346/ A quadratic field which is Euclidean but not norm-Euclidean] | journal = Manuscripta mathematica | volume = 83 | pages = 327–330 | doi = 10.1007/BF02567617}}</ref> Primul exemplu de domeniu euclidian nu era cu funcție normă (''D''=69) și a fost publicat în 1994.<ref name="Clark_1994" /> În 1973, Weinberger a demonstrat că un ienl este euclidian [[dacă și numai dacă]] este [[domeniu de ideal principal]], cu condiția ca [[ipoteza Riemann generalizată]] să fie adevărată;<ref>{{cite journal | author = Weinberger P | chapter = On Euclidean rings of algebraic integers | journal = Proc. Sympos. Pure Math. | volume = 24 | pages = 321–332}}</ref> Demonstrația lui Weinberger a fost generalizată în 2004 pentru a elimina această restricție.<ref>{{cite journal | author = Harper M, Murty, MR | year = 2004 | title = [http://www.mast.queensu.ca/~murty/harper-murty.pdf Euclidean Rings of Algebraic Integers] | journal = Canadian Journal of Mathematics | volume = 56 | pages = 71–76}}</ref>

=== Inele necomutative ===
Algoritmul lui Euclid se poate aplica pe inele necomutative, ca și pe mulțimea [[cuaternion Hurwitz|cuaternionilor Hurwitz]].<ref>{{citat carte | author = [[John Stillwell|Stillwell J]] | year = 2003 | title = Elements of Number Theory | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-95587-9 | pages = 151–152}}</ref> Fie α și β două elemente ale unui inel necomutativ. Ele au un divizor comun la dreapta δ dacă α = ξδ și β = ηδ pentru două numere ξ și η din inel. Analog, ele au un divizor comun la stânga dacă α = δξ și β = δη pentru două elemente ξ și η în inel. Cum înmulțirea nu este comutativă, există două versiuni de algoritm al lui Euclid, unul pentru divizorii la stânga și alta pentru divizorii la dreapta. Dacă se aleg divizorii la dreapta, primul pas în a găsi CMMDC(α, β) prin algoritmul lui Euclid se poate scrie

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

unde ψ<sub>0</sub> reprezintă câtul, iar ρ<sub>0</sub> reprezintă restul. Această ecuație arată că orice divizor comun la dreapta al lui α și β este divizor comun și al restului ρ<sub>0</sub>. Ecuația analoagă pentru divizorii la stânga ar fi

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

În oricare variantă, procesul se repetă ca mai sus până când se identifică cel mai mare divizor comun la dreapta sau la stânga. Ca și în cazul inelelor euclidiene, „mărimea” restului ρ<sub>0</sub> trebuie să fie strict mai mică decât β, și trebuie să existe doar un număr finit de mărimi posibile pentru ρ<sub>0</sub>, pentru ca algoritmul să se termine.

Majoritatea rezultatelor pentru CMMDC sunt valabile și pentru inelele necomutative. De exemplu, [[identitatea lui Bézout]] afirmă că CMMMDC la dreapta al lui α și β se poate exprima sub formă de combinație liniară de α și β. Cu alte cuvinte, există numerele σ și τ cu proprietatea că

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

Identitatea analoagă pentru CMMDC la stânga este aproape similară:

: Γ<sub>stânga</sub> = ασ + βτ

Identitatea lui Bézout se poate utiliza pentru rezolvarea de ecuații diofantice.

== Generalizări la alte structuri matematice ==
[[Fișier:TorusKnot3D.png|thumb|Algoritmul lui Euclid se poate aplica în [[teoria nodurilor]].<ref>{{cite journal | author = Yamada Y | year = 2007 | title = [http://arxiv.org/abs/0708.2316 Generalized rational blow-down, torus knots, and Euclidean algorithm] | publisher = arXiv:0708.2316v1}}</ref>]]

Algoritmul lui Euclid are trei trăsături generale care împreună asigură faptul că nu se execută la infinit. Prima este că poate fi scris ca șir de operațiuni recursive

: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>

în care fiecare rest este strict mai mic decât predecesorul său, |''r''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''−1</sub>|. A doua, dimensiunea fiecărui rest are o limită inferioară strictă, cum ar fi |''r''<sub>''k''</sub>|&nbsp;≥&nbsp;0. A treia, există doar un număr finit de dimensiuni mai mici ca un rest dat |''r''<sub>''k''</sub>|. Generalizările algoritmului lui Euclid cu aceste trăsături de bază s-au aplicat și altor structuri matematice, cum ar fi nodurile<ref>{{citat carte|first=John|middle=Horton|last=Conway|author-link=John Horton Conway|contribution=An enumeration of knots and links, and some of their algebraic properties|publisher=Pergamon|year=1970|pages=329–358|title=Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967)}}</ref> și numerele ordinale transfinite.<ref>{{cite journal | author = Jategaonkar AV | year = 1969 | title = [http://projecteuclid.org/euclid.bams/1183530557 Rings with transfinite left division algorithm] | journal = Bull. Amer. Math. Soc. | volume = 75 | pages = 559–561 | doi = 10.1090/S0002-9904-1969-12242-1}}</ref>

O importantă generalizare a algoritmului lui Euclid este conceptul de [[bază Gröbner]] din [[Geometrie algebrică|geometria algebrică]]. Așa cum s-a arătat mai sus, CMMDC ''g'' al două numere întregi ''a'' și ''b'' este generatorul idealului lor. Cu alte cuvinte, oricare ar fi întregii ''s'' și ''t'', există un alt întreg ''m'' cu proprietatea că

: ''sa'' + ''tb'' = ''mg''.

Deși aceasta este valabilă și când ''s'', ''t'', ''m'', ''a'' și ''b'' reprezintă polinoame de o singură variabilă, ea ''nu'' este adevărată pentru inele de polinoame de mai mult de o variabilă.<ref>Cox, p. 65.</ref> În acest caz, se poate defini o mulțime finită de polinoame generatoare ''g''<sub>1</sub>, ''g''<sub>2</sub> etc. astfel încât orice combinație liniară de două polinoame de mai multe variabile ''a'' și ''b'' pot fi exprimate ca multipli ai generatoarelor

: ''sa'' + ''tb'' = Σ<sub>''k''</sub> ''m''<sub>''k''</sub>''g''<sub>''k''</sub>

unde ''s'', ''t'' și ''m''<sub>''k''</sub> sunt polinoame de mai multe variabile.<ref>Cox, pp. 73–79.</ref> Orice astfel de polinom cu mai multe variabile ''f'' poate fi exprimat ca astfel de sumă de polinoame generatoare plus un polinom rest ''r'', denumit uneori ''forma normală'' a polinomului ''f''

: ''f'' = ''r'' + Σ<sub>''k''</sub> ''q''<sub>''k''</sub>''g''<sub>''k''</sub>

deși polinoamele cât ''q''<sub>''k''</sub> pot să nu fie unice.<ref>Cox, pp. 79–86.</ref> Mulțimea acestor polinoame generatoare se numește bază Gröbner.<ref>Cox, p. 74.</ref>

== Note ==
{{listănote|3}}

== Bibliografie ==
* {{citat carte | author = [[Henri Cohen|Cohen H]] | year = 1993 | title = A Course in Computational Algebraic Number Theory | url = http://books.google.com/books?id=hXGr-9l1DXcC | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-55640-0}}
* {{citat carte | author = Cohn H | year = 1962 | title = Advanced Number Theory |url = http://books.google.com/books?id=yMGeElJ8M0wC | publisher = Dover | location = New York | isbn = 0-486-64023-X}}
* {{citat carte | author = [[Thomas H. Cormen|Cormen TH]], [[Charles E. Leiserson|Leiserson CE]], [[Ronald L. Rivest|Rivest RL]], and [[Clifford Stein|Stein C]] | year = 2001|title= Introduction to Algorithms |url=http://books.google.com/books?id=NLngYyWFl_YC |edition=2nd|publisher=MIT Press and McGraw–Hill|isbn =0262032937}}
* {{citat carte | author = Cox D, Little J, and O'Shea D | year = 1997 | title = Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra |url = http://books.google.com/books?id=7eLkq0wQytAC | edition = 2nd | publisher = [[Springer-Verlag]] | isbn = 0-387-94680-2}}
* {{citat carte | author = [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet PGL]]|year=1894 | title = Vorlesungen über Zahlentheorie|editor=[[Richard Dedekind]]|publisher=Vieweg| location=Braunschweig}}
* {{citat carte | author = [[G. H. Hardy|Hardy GH]], [[E. M. Wright|Wright EM]] [revised by D.R. Heath-Brown and J.H. Silverman]. | date = 2008|url = http://books.google.com/books?id=rey9wfSaJ9EC | title =An Introduction to the Theory of Numbers|edition = 6th|publisher=Clarendon Press|location =Oxford}}
* {{citat carte|author=[[Donald Knuth|Knuth D]]|year=1997|title=[[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley| isbn=0201896842}}
* {{citat carte | author = [[William J. LeVeque|LeVeque WJ]] | year = 1977 | title = Fundamentals of Number Theory | publisher = Dover | location = New York | isbn = 0-486-68906-9}}
* {{citat carte | author = Mollin RA | year = 2008 | title = Fundamental Number Theory with Applications | edition = 2nd|publisher=Chapman & Hall/CRC|location=Boca Raton|isbn = 9781420066593}}
* {{citat carte | author = [[Øystein Ore|Ore Ø]] | date = 1948 | title = Number Theory and Its History | publisher = McGraw–Hill | location = New York}}
* {{citat carte | author = Rosen KH | year = 2000 | title = Elementary Number Theory and its Applications | edition = 4th | publisher = Addison–Wesley | location =Reading, MA|isbn= 0201870738}}
* {{citat carte | author = [[Manfred R. Schroeder|Schroeder MR]] | year = 2005 | title = Number Theory in Science and Communication | edition = 4th | publisher = [[Springer-Verlag]]|isbn= 0387158006}}
* {{citat carte | author = [[Harold Stark|Stark H]] | year = 1978 | title = An Introduction to Number Theory | publisher = MIT Press | isbn = 0-262-69060-8}}
* {{citat carte | author = [[John Stillwell|Stillwell J]] | year = 1997 | title = Numbers and Geometry | publisher = [[Springer-Verlag]] | location = New York | isbn = 0-387-98289-2}}
* {{citat carte | author = Tattersall JJ | year = 2005 | title = Elementary number theory in nine chapters | publisher = [[Cambridge University Press]] | location = Cambridge | isbn = 9780521850148}}
* {{citat carte | author = Uspensky JV, Heaslet MA | year = 1939 | title = Elementary Number Theory | publisher = McGraw–Hill | location = New York }}

== Legături externe ==
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Demonstrații ale algoritmului lui Euclid]
* {{MathWorld | urlname=EuclideanAlgorithm | title=Euclidean Algorithm}}
* [http://www.cut-the-knot.org/blue/Euclid.shtml Algoritmul lui Euclid] la [[cut-the-knot]]
* {{PlanetMath | urlname=EuclidsAlgorithm | title=Euclid's algorithm}}
* [http://www.mathpages.com/home/kmath384.htm Algoritmul lui Euclid] la MathPages
* [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Jocul lui Euclid] la [[cut-the-knot]]
* [http://plus.maths.org/issue40/features/wardhaugh/index.html Muzica și algoritmul lui Euclid]

{{articol de calitate}}

[[Categorie:Algoritmi]]