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 celui mai mare divizor comun (CMMDC). El este denumit după matematicianul grec Euclid, care l-a descris în Cărțile VII și X din Elementele.Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

CMMDC a două numere este cel mai mare număr care le 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 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 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 prin suma celor două numere inițiale, fiecare înmulțite cu un întreg pozitiv sau negativ, de exemplu: 21 = 5 × 105 + (−2) × 252. 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 polinoamele de o variabilă. Aceasta a dus la noțiuni moderne de algebră abstractă, cum ar fi inelele euclidiene. Algoritmul lui Euclid s-a generalizat și pentru alte structuri matematice, cum ar fi 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țiile diofantice, cum ar fi calcularea numerelor care satisfac mai multe congruențe (teorema chinezească a resturilor) sau inversul multiplicativ al unui corp. Algoritmul lui Euclid poate fi utilizat pentru a construi fracții continue, în metoda lanțului Sturm pentru găsirea rădăcinilor reale ale unui polinom, și în mai mulți algoritmi moderni de factorizare a întregilor. Este utilizat și la demonstrarea unor teoreme din 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 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ă 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, b) sau, mai simplu, ca (a, b),Stark, p. 16. 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, b) = 1, atunci a și b sunt prime între ele.Stark, p. 21. Această proprietate nu depinde de primalitatea lui a și a lui b.LeVeque, p. 32. De exemplu, numerele 6 și 35 nu sunt numere prime, deoarece ambele au doi factori: 6 = 2 × 3 și 35 = 5 × 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.

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, b). Cum a și b sunt multipli ai lui g, ele pot fi scrise sub forma a = mg și b = ng, și nu există niciun număr mai mare G > 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.Leveque, p. 31.

CMMDC poate fi vizualizat geometric după cum urmează. 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 = 2) și cinci pătrate pe cealaltă (60/12 = 5).

CMMDC a două numere a și b se poate defini ca produsul factorilor primi comuni ai celor două numere.Schroeder, pp. 21–22. De exemplu, întrucât 462 se factorizează în 2 × 3 × 7 × 11 și 1071 se factorizează în 3 × 3 × 7 × 17, cel mai mare divizor comun al lui 462 și 1071 este egal cu 21 = 3 × 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.Schroeder, p. 19. Factorizarea numerelor întregi mari este considerată a fi o problemă atât de dificilă încât multe sisteme criptografice moderne se bazează pe ea.Schroeder, pp. 216–219.

O definiție mai subtilă a CMMDC este utilă în matematica avansată, în particular în teoria inelelor. Cel mai mare divizor comun g  al două numere a și b este și cel mai mic multiplu întreg al lor, adică cel mai mic număr de forma ua + 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 + vb) este aceeași cu mulțimea multiplilor întregi ai lui g (mg, unde m este întreg). În limbajul matematic modern, Idealul format de a și b este ideal principal generat de 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,Stark, p. 25. care poate fi calculat luând CMMDC pe perechi de numere.Ore, pp. 47–48. De exemplu,

CMMDC(a, b, c) = CMMDC(a, CMMDC(b, c)) = CMMDC(CMMDC(a, b), c) = CMMDC(CMMDC(a, c), 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ția, recursivitatea și coborârea infinită. Inducția (Secțiunea 1.2.1: Mathematical Induction, pp. 11–21.) este utilizată adesea pentru a demonstra o teoremă pentru toate numerele naturale n.Rosen, pp. 18–21. Această abordare începe prin a arăta că, dacă teorema este valabilă pentru n, ea este valabilă și pentru n + 1. Astfel, dacă teorema este valabilă pentru un singur caz (de regulă, n = 1), ea este valabilă pentru toate numerele mai mari (n = 2, 3, etc.). Recursivitatea unei ecuațiiRosen, pp. 21–24. este proprietatea ei de a lega numerele ce formează un șir a1, a2, a3, etc. Al n-lea termen al șirului, an, este adesea exprimat în funcție de alți termeni ai șirului, cum ar fi an−1. De exemplu, numerele Fibonacci sunt definite recursiv; fiecare termen este suma celor doi termeni precedenți: Fn = Fn−1 + Fn−2. Mai multe ecuații asociate cu algoritmul lui Euclid sunt recursive. În fine, în coborârea infinită,Rosen, p. 492. o soluție dată în numere naturale este utilizată pentru a construi o soluție cu numere naturale mai mici. 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.

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.Stark, pp. 16–20. Fie k un întreg care numără pașii algoritmului, începând cu zero. Astfel, pasul inițial corespunde lui k = 0, pasul următor corespunde lui k = 1, și așa mai departe.

Fiecare pas începe cu două resturi nenegative rk−1 și rk−2. Întrucât algoritmul asigură că resturile scad la fiecare pas, rk−1 este mai mic decât predecesorul sau rk−2. Scopul pasului k este găsirea câtului qk și a restului rk astfel încât să fie satisfăcută ecuația:

rk−2 = qk rk−1 + rk

unde rk < rk−1. Cu alte cuvinte, multiplii celui mai mic număr rk−1 sunt scăzuți din numărul mai mare rk−2 până când restul este mai mic decât rk−1.

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

a = q0 b + r0 b = q1 r0 + r1 r0 = q2 r1 + r2 r1 = q3 r2 + r3 …

Dacă a este mai mic decât b, primul pas al algoritmului schimbă numerele între ele. De exemplu, dacă a < b, câtul inițial q0 este zero, iar restul r0 este a. Astfel, rk este mai mic decât predecesorul său rk−1 pentru orice k ≥ 0.

Întrucât resturile scad la fiecare pas dar nu pot fi niciodată negative, un rest rN trebuie în cele din urmă să fie zero, moment în care algoritmul se oprește.Stark, p. 18. Ultimul rest nenul rN−1 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 r0 și zero.

Demonstrația corectitudinii Corectitudinea algoritmului lui Euclid se poate demonstra în doi pași. La primul pas, se arată că ultimul rest nenul rN−1 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 rN−1; deci, g trebuie să fie mai mic sau egal cu rN−1. Aceste două concluzii sunt inconsistente doar dacă rN−1 nu este egal cu g.

Pentru a demonstra că rN−1 divide și pe a și pe b (primul pas), rN−1 divide predecesorul său rN−2

rN−2 = qN rN−1

întrucât ultimul rest rN este zero. rN−1 divide și pe următorul său predecesor rN−3

rN−3 = qN−1 rN−2 + rN−1

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