Algoritmul lui Euclid

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.

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 sub formă de 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), 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. Această proprietate nu depinde de primalitatea lui a și a lui b. 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.

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.

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. 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. Factorizarea numerelor întregi mari este considerată a fi o problemă atât de dificilă încât multe sisteme criptografice moderne se bazează pe ea.

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, care poate fi calculat luând CMMDC pe perechi de numere. 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 este utilizată adesea pentru a demonstra o teoremă pentru toate numerele naturale n. 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ții este proprietatea ei de a lega numerele ce formează un șir a₁, a₂, a₃, etc. Al n-lea termen al șirului, a_n, este adesea exprimat în funcție de alți termeni ai șirului, cum ar fi a_n−1. De exemplu, numerele Fibonacci sunt definite recursiv; fiecare termen este suma celor doi termeni precedenți: F_n = F_n−1   F_n−2. Mai multe ecuații asociate cu algoritmul lui Euclid sunt recursive. În fine, în coborârea infinită, 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. 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 r_k−1 și r_k−2. Întrucât algoritmul asigură că resturile scad la fiecare pas, r_k−1 este mai mic decât predecesorul sau r_k−2. Scopul pasului k este găsirea câtului q_k și a restului r_k astfel încât să fie satisfăcută ecuația:

r_k−2 = q_k r_k−1 r_k

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

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

a = q₀ b r₀

b = q₁ r₀ r₁

r₀ = q₂ r₁ r₂

r₁ = q₃ r₂ r₃

…

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 q₀ este zero, iar restul r₀ este a. Astfel, r_k este mai mic decât predecesorul său r_k−1 pentru orice k ≥ 0.

Întrucât resturile scad la fiecare pas dar nu pot fi niciodată negative, un rest r_N trebuie în cele din urmă să fie zero, moment în care algoritmul se oprește. Ultimul rest nenul r_N−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 r₀ ș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 r_N−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 r_N−1; deci, g trebuie să fie mai mic sau egal cu r_N−1. Aceste două concluzii sunt inconsistente doar dacă r_N−1 nu este egal cu g.

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

r_N−2 = q_N r_N−1

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

r_N−3 = q_N−1 r_N−2 r_N−1

deoarece el divide ambii termeni ai părții drepte a ecuației. Iterând același argument, r_N−1 divide toate celelalte resturi, inclusiv pe a și pe b. Niciunul din resturile anterioare r_N−2, r_N−3, etc. nu divid pe a și pe b, deoarece toate lasă un rest nenul. Cum r_N−1 este un divizor comun al lui a și b, r_N−1 ≤ 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_k. Prin definiție, a și b pot fi scrise ca multipli de c: a = mc și b = nc, unde m și n sunt numere naturale. Deci c divide restul inițial r₀, întrucât r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c. O demonstrație analogă arată că c divide și celelalte resturi r₁, r₂, etc. Deci cel mai mare divizor comun g divide r_N−1, de unde rezultă că g ≤ r_N−1. Întrucât în prima parte a demonstrației s-a arătat că (r_N−1 ≤ g), rezultă că g = r_N−1. Deci g este cel mai mare divizor comun al tuturor perechilor succesive:

g = CMMDC(a, b) = CMMDC(b, r₀) = CMMDC(r₀, r₁) = … = CMMDC(r_N−2, r_N−1) = r_N−1

Exemplu

Animație a algoritmului. Dreptunghiul verde inițial are dimensiunile a = 1071 și b = 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 = 1071 și b = 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₀ = 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₁ = 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₂ = 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:

Numărul pasului	Ecuația	Cât și rest
0	1071 = q0 462 r0	q0 = 2 and r0 = 147
1	462 = q1 147 r1	q1 = 3 and r1 = 21
2	147 = q2 21 r2	q2 = 7 and r2 = 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. 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₀-pe-b neacoperit, unde r₀<b. Atunci se încearcă împărțirea dreptunghiului rezidual cu pătrate r₀-pe-r₀. Rămâne un al doilea dreptunghi rezidual r₁-pe-r₀, pe care se încearcă să fie acoperit cu pătrate r₁-pe-r₁, ș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_k și un rest r_k ale două numere r_k−1 și r_k−2

r_k−2 = q_k r_k−1 r_k

unde modulul lui r_k este strict mai mic decât cel al lui r_k−1. 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_k și r_k sunt unice, dar unicitatea lor nu este necesară pentru algoritmul lui Euclid.

În versiunea originală dată de Euclid pentru acest algoritm, câtul și restul se găsesc prin scădere repetată; adică r_k−1 este scăzut din r_k−2 repetat până când restul r_k este mai mic decât r_k−1. 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_k ≡ r_k−2 mod r_k−1

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 programată ca

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_k−1, iar variabila a deține predecesorul acesteia, r_k−2. Pasul b := a mod b este echivalent cu formula recursivă de mai sus r_k ≡ r_k−2 mod r_k−1. Variabila t reține valoarea lui r_k−1 în timp ce se calculează următorul rest r_k. La sfârșitul acestei bucle de iterații, variabila b va păstra restul r_k, iar variabila a va reține predecesorul, r_k−1.

În versiunea pe bază de scădere, definită de Euclid, calculul restului (b = a mod b) este înlocuit cu scăderea repetată.

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_k−1 și r_k−2. Se presupune că a este mai mare ca b la începutul unei iterații; atunci a este egal cu r_k−2, fiindcă r_k−2 > r_k−1. 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_k. 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_{k 1}, și așa mai departe.

Versiunea recursivă se bazează pe egalitatea CMMDC al resturilor succesive și pe condiția de oprire CMMDC(r_N−1, 0) = r_N−1.

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

Pentru ilustrare, se calculează CMMDC(1071, 462) din CMMDC(462, 1071 mod 462) = CMMDC(462, 147). Acest al doilea CMMDC se calculează din CMMDC(147, 462 mod 147) = CMMDC(147, 21), care la rândul său se calculează din CMMDC(21, 147 mod 21) = CMMDC(21, 0) = 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. Anterior, ecuația

r_k−2 = q_k r_k−1 r_k

presupunea că r_k−1 > r_k > 0. Se poate, însa, calcula și un alt rest negativ e_k

r_k−2 = (q_k 1) r_k−1 e_k

unde r_k−1 este presupus pozitiv. Dacă |e_k| < |r_k|, atunci r_k este înlocuit de e_k. După cum a arătat Leopold Kronecker, această versiune necesită cel mai mic număr de pași dintre toate versiunile algoritmului lui Euclid.

Istoric

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. El apare în 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 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 g.

Algoritmul nu a fost, probabil, descoperit de Euclid, care doar a compilat rezultate ale matematicienilor dinaintea sa în lucrarea Elemente. Matematicianul și istoricul B. L. van der Waerden sugerează că Cartea VII derivă dintr-un manual de teoria numerelor scris de matematicieni ai școlii lui Pitagora. Algoritmul a fost probabil cunoscut lui Eudoxus din Cnidus (circa 375 î.e.n.) Algoritmul ar putea fi dinainte chiar și de Eudoxus, judecând după utilizarea termenului tehnic ἀνθυφαίρεσις (anthyphairesis, scădere reciprocă) din lucrările lui Euclid și Aristotel.

După mai multe secole, algoritmul lui Euclid a fost descoperit independent în India și în China, ș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”, poate din cauza eficienței sale în rezolvarea de ecuațiilor diofantice. Deși un caz special al teoremei chinezești a resturilor fusese deja descris de matematicianul și astronomul chinez Sun Tzu, soluția generală a fost publicată de Qin Jiushao în cartea sa din 1247 intitulată Shushu Jiuzhang (數書九章 „Tratat matematic în nouă secțiuni”). Algoritmul lui Euclid a fost descris în Europa pentru prima dată în a doua ediție a lucrării lui Bachet Problèmes plaisants et délectables (Probleme plăcute și delectabile, 1624). În Europa, a fost folosit tot pentru rezolvarea de ecuații diofantice, dar și la construcția 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.

Î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 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. Gauss a menționat algoritmul în Disquisitiones Arithmeticae (publicat la 1801), dar numai ca metodă pentru fracțiile continue. Peter Dirichlet pare a fi fost primul care a descris algoritmul lui Euclid ca bază pentru teoria numerelor. 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. 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 celor două pătrate a lui Fermat folosind factorizarea unică a întregilor gaussieni. 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.

„[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.”

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd edition (1981), p. 318.

În secolul al XIX-lea au fost dezvoltate și alte aplicații ale algoritmului lui Euclid. În 1829, Charles Sturm a arătat că algoritmul este util în metoda lanțurilor Sturm de numărare a rădăcinilor reale dintr-un interval dat ale polinoamelor.

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, și algoritmii asociați, algoritmul LLL, algoritmul HJLS și algoritmul PSLQ.

În 1969, Cole și Davie au dezvoltat un joc în doi pe baza algoritmului lui Euclid, joc intitulat Jocul lui Euclid, care are o strategie optimă. 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.

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. Cu alte cuvinte, întotdeauna există două numere întregi s și t astfel încât g = sa   tb.

Întregii s și t pot fi calculați pe baza câturilor q₀, q₁ etc. inversând ordinea ecuațiilor din algoritmul lui Euclid. Începând cu penultima ecuație, g poate fi exprimat în termeni de câtul q_N−1 și de cele două resturi anterioare, r_N−2 și r_N−3.

g = r_N−1 = r_N−3 − q_N−1 r_N−2

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

r_N−2 = r_N−4 − q_N−2 r_N−3

r_N−3 = r_N−5 − q_N−3 r_N−4

Înlocuind aceste formule pentru r_N−2 și r_N−3 în prima ecuație rezultă g sub formă de combinație liniară a resturilor r_N−4 și r_N−5. 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₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b

După ce toate resturile r₀, r₁ etc. au fost substituite, ultima ecuație îl exprimă pe g sub forma unei combinații liniare de a și b: g = sa   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. Fie mulțimea tuturor numerelor de forma ua   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 = s și v = 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 = ms și v = 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   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. 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   vb. Aceste volume sunt toate multipli ai lui g = CMMDC(a, 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

s_k = s_k−2 − q_k−1s_k−1

t_k = t_k−2 − q_k−1t_k−1

cu valorile de început

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1

Cu ajutorul acestei relații de recurență, întregii lui Bézout s și t sunt dați de s = s_N și t = t_N, unde N este pasul la care algoritmul se termină cu r_N = 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_j = s_j a t_j b

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

r_k = r_k−2 − q_k−1r_k−1

Întrucât formula de recurență este considerată corectă pentru r_k−2 și r_k−1, ele pot fi exprimate în funcție de variabilele corespunzătoare s și t

r_k = (s_k−2 a t_k−2 b) − q_k−1(s_k−1 a t_k−1 b)

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

r_k = s_k a t_k b = (s_k−2 − q_k−1s_k−1) a (t_k−2 − q_k−1t_k−1) b

Metoda matricială

Întregii s și t pot fi găsiți și folosind o metodă echivalentă bazată pe matrice. Secvența de ecuații a algoritmului lui Euclid

a = q₀ b r₀

b = q₁ r₀ r₁

…

r_N−2 = q_N r_N−1 0

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

${\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}}$

Fie M produsul tuturor matricelor–cât

$\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}}$

Aceasta simplifică algoritmul lui Euclid la forma

${\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}$

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 inversa matricei M. Determinantul lui M este egal cu (−1)^{N 1}, 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

${\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}}$

Deoarece ecuația de sus dă

g = (−1)^{N 1} ( m₂₂ a − m₁₂ b)

cei doi întregi ai identității lui Bézout sunt s = (−1)^{N 1}m₂₂ și t = (−1)^Nm₁₂. 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. Pentru a ilustra aceasta, se presupune că un număr L poate fi scris ca produs de doi factori u și v, adică L = 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: 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₁, a₂, …, a_n, atunci w este prim și cu produsul lor, a₁ × a₂ × … × a_n.

Lema lui Euclid este suficientă pentru a demonstra că toate numerele au o unică descompunere în factori primi. Dacă se presupune contrariul, și anume că există două factorizări independente ale lui L în m respectiv n factori primi

L = p₁p₂…p_m = q₁q₂…q_n

Î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 = 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

Graficul unei ecuații diofantice, 9x   12y = 483. Soluțiile sunt arătate ca cercuri albastre.

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. O ecuație diofantică liniară tipică în variabilele întregi x și y are forma

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   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. Aceasta mai dă o soluție a ecuației diofantice, x₁ = s (c/g) și y₁ = t (c/g).

În general, o ecuație diofantică liniară fie nu are soluție, fie are un număr infinit de soluții. Pentru a demonstra cel de-al doilea caz, se consideră două soluții, (x₁, y₁) și (x₂, y₂)

ax₁ by₁ = c = ax₂ by₂

sau echivalent

a(x₁ − x₂) = b(y₂ − y₁).

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₁ − bt/g

y = y₁ 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₁, y₁). Dacă soluțiile trebuie să fie întregi pozitivi (x > 0, y > 0), este posibil să existe doar un număr finit de soluții. Această 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; 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 comutativitatea, asociativitatea și distributivitatea. Un exemplu de corp finit este mulțimea de 13 numere {0, 1, 2, …, 12} cu aritmetica modulară. În acest corp, rezultatele oricărei operații matematice (adunare/scădere/înmulțire/împărțire) se reduce 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 × 7 = 35 mod 13 = 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 ^m. Corpurile finite sunt adesea numite corpuri Galois și sunt notate cu GF(p) sau GF(p ^m).

Într-un astfel de corp cu m numere, fiecare element nenul a are un invers multiplicativ unic modulo m, a⁻¹ astfel încât aa⁻¹ = a⁻¹a ≡ 1 mod m. Acest invers se poate găsi rezolvând ecuația ax ≡ 1 mod m, sau ecuația diofantică liniară echivalentă

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. Deși algoritmul RSA utilizează 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 codurile corectoare de erori; de exemplu, el se poate folosi ca alternativă la algoritmul Berlekamp–Massey pentru decodificarea codurilor BCH și Reed–Solomon, coduri bazate pe corpuri Galois.

Teorema chinezească a resturilor

Algoritmul lui Euclid se poate folosi pentru a rezolva și mai multe ecuații liniare diofantice. 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_i ale împărțirii lui modulo o mulțime de N numere prime între ele m_i.

x₁ ≡ x mod m₁

x₂ ≡ x mod m₂

…

x_N ≡ x mod m_N

Scopul este determinarea lui x din cele N resturi x_i. 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_i, și definind M_i

M_i = M / m_i

Astfel, fiecare M_i este produsul tuturor modulelor cu excepția lui m_i. Soluția depinde de găsirea a N noi numere h_i astfel încât

M_ih_i ≡ 1 mod m_i

Cu aceste numere h_i, orice întreg x se poate reconstitui din resturile x_i prin ecuația

x ≡ (x₁M₁h₁ x₂M₂h₂ … x_NM_Nh_N ) mod M

Deoarece aceste numere h_i sunt inversele multiplicative ale numerelor M_i, 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ă. Șirul de ecuații poate fi scris sub forma

a/b = q₀ r₀/b

b/r₀ = q₁ r₁/r₀

r₀/r₁ = q₂ r₂/r₁

…

r_k−2/r_k−1 = q_k r_k/r_k−1

…

r_N−2/r_N−1 = q_N

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₀ 1/(q₁ r₁/r₀)

A treia ecuație poate fi folosită pentru a substitui termenul de la numitor r₁/r₀, dând

a/b = q₀ 1/(q₁ 1/(q₂ r₂/r₁))

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

a/b = q₀ 1/(q₁ 1/(q₂ 1/(… 1/q_N))…) = [q₀; q₁, q₂, …, q_N]

În exemplul de mai sus, s-a calculat CMMDC(1071, 462), iar câturile q_k 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 factorizare a întregilor, cum ar fi Pollard's rho algorithm, algoritmul lui Shor, metoda de factorizare a lui Dixon și factorizarea Lenstra cu curbe eliptice. 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.

Eficiența algoritmului

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ă. 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, 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. Întrucât costul computațional al fiecărui pas este și el de ordinul lui h, costul total crește ca h².

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, b). Dacă g este CMMDC al lui a și b, atunci a = mg și b = 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. 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, b   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₀) = 2 T(r₀, r₁) = … = N T(r_N−2, r_N−1) = N 1

unde se presupune că T(x, 0) = 0.

Numărul maxim de pași

Dacă algoritmul lui Euclid se execută în N pași pentru două numere naturale a > b > 0, cele mai mici valori ale lui a și b pentru care acest lucru este adevărat sunt numerele Fibonacci F_{N 2} respectiv F_{N 1}. Aceasta se poate arăta prin inducție. Dacă N = 1, b divide a; cele mai mici numere naturale pentru care acest lucru este adevărat sunt b = 1 și a = 2, care sunt F₂ și respectiv F₃. 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 = q₀b   r₀, iar al doilea pas este b = q₁r₀   r₁. Algoritmul fiind recursiv, el a rulat M−1 pași pentru a găsi CMMDC(b, r₀) iar valorile lor cele mai mici sunt F_{M 1} și F_M. Cea mai mică valoare a lui a este deci cea cu q₀ = 1, de unde a = b   r₀ = F_{M 1}   F_M = F_{M 2}. Această demonstrație, publicată de Gabriel Lamé în 1844, reprezintă începuturile teoriei complexității computaționale, fiind și prima aplicație practică a șirului lui Fibonacci.

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). Dacă algoritmul rulează în N pași, atunci b este mai mare sau egal cu F_{N 1} care este mai mare sau egal cu φ^N, unde φ este raportul de aur. Cum b > φ^N, atunci N < log_φb. Întrucât log₁₀φ > 1/5, N/5 < log₁₀φ log_φb = log₁₀b. Astfel, N < 5 log₁₀b. Deci, algoritmul lui Euclid are nevoie întotdeauna de mai puțin decât 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 − 1

$T(a)={\frac {1}{a}}\sum _{0\leq b<a}T(a,b).$

Deoarece T(a, b) fluctuează dramatic cu CMMDC a celor două numere, însă, funcția T(a) este afectată de „zgomote”.

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

$\tau (a)={\frac {1}{\varphi (a)}}\sum _{0\leq b<a,\mathrm {GCD} (a,b)=1}T(a,b).$

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

τ(a) = (12/π²) ln 2 ln a C O(a^{−(1/6) ε})

cu eroarea reziduală de ordinul lui a^{−(1/6) ε}, unde ε este infinitezimal. Constanta C din această formulă este egală cu

C = −(1/2) 6 (ln 2/π²)( 4γ − 24π²ζ '(2) 3 ln 2 − 2) ≈ 1.467

unde γ este constanta Euler–Mascheroni iar ζ' este derivata funcției zeta Riemann. Coeficientul dominant (12/π²) ln 2 a fost determinat prin două metode independente.

Întrucât prima medie se poate calcula din media tau prin sumă peste divizorii d ai lui a

$T(a)={\frac {1}{a}}\sum _{d|a}\varphi (d)\tau (d)$

ea poate fi aproximată prin formula

T(a) ≈ C (12/π²) ln 2 ( ln a − Σ_d|a Λ(d)/d )

unde Λ(d) este funcția Mangoldt.

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

$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).$

Înlocuind formula aproximativă pentru T(a) în această ecuație rezultă o estimare a lui Y(n)

Y(n) ≈ (12/π²) 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_k și restul r_k pentru o pereche dată de întregi r_k−2 și r_k−1

r_k−2 = q_k r_k−1 r_k.

Costul computațional al fiecărui pas este asociat cu găsirea lui q_k, întrucât restul r_k poate fi calculat rapid din r_k−2, r_k−1, and q_k

r_k = r_k−2 − q_k r_k−1.

Costul computațional al împărțirii numerelor pe h biți scalează ca O(h(ℓ 1)), unde ℓ este lungimea câtului.

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 − 1)| unde u = (q   1)². 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, algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri. Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid.

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²) în funcție de numărul de cifre h al celor două numere inițiale a și b. Fie h₀, h₁, …, h_N−1 numărul de cifre ale resturilor succesive r₀, r₁, …, r_N−1. Cum numărul de pași N crește liniar cu h, timpul de execuție este limitat de

$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}).$

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ă mai sus, CMMDC este egal cu produsul factorilor primi comuni ai celor două numere a și b. Metodele actuale de factorizare sunt și ele ineficiente; multe alte sisteme criptografice se bazează tocmai pe această ineficiență.

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. Această alternativă, însă, scalează și ea ca O(h²). Este de regulă mai rapidă pe calculatoarele reale, dar scalează la fel ca algoritmul lui Euclid. Eficiența se poate îmbunătăți examinând doar primele cifre ale numerelor a și b. Algoritmul binar poate fi extins la alte baze (algoritmi k-ari), cu creșteri ale vitezei de până la cinci ori.

O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici, cum ar fi cel al lui Schönhage și cel al lui Stehlé și Zimmermann. Acești algoritmi exploatează forma matriceală 2×2 a algoritmului lui Euclid prezentată mai sus. Aceste metode subcuadratice scalează în general ca O(h (log h)² (log log h)).

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 polinoamele, î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 numerelor reale, așa cum arată Euclid în Cartea 10 din 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 întregi. 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.

Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile r_k sunt numere reale, deși câturile q_k 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₀; q₁, q₂, …, q_N]. 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₀; q₁, q₂, …]. Exemple de fracții continue infinite sunt raportul de aur φ = [1; 1, 1, …] și 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₀; q₁, q₂, …, q_k] 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_k/n_k; numărătorul și numitorul sunt prime între ele și respectă relația recursivă

m_k = q_k m_k−1 m_k−2

n_k = q_k n_k−1 n_k−2

unde m₋₁ = n₋₂ = 1 și m₋₂ = n₋₁ = 0 sunt valorile inițiale. Convergentul m_k/n_k este cea mai bună aproximație rațională a lui a/b cu numitorul n_k:

$\left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.$

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. Procedura de bază este similară cu cea de la întregi. La fie care pas k, se calculează un polinom cât q_k(x) și un polinom rest r_k(x) care satisfac ecuația recursivă

r_k−2(x) = q_k(x) r_k−1(x) r_k(x)

unde r₋₂(x) = a(x) și r₋₁(x) = b(x). Polinomul cât este ales astfel încât termenul dominant al lui q_k(x) r_k−1(x) să fie egal cu termenul dominant al lui r_k−2(x); aceasta asigură că gradul fiecărui rest este mai mic decât gradul predecesorului său grad[r_k(x)] < grad[r_k−1(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).

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

a(x) = x⁴ − 4x³ 4 x² − 3x 14 = (x² − 5x 7)(x² x 2)

și

b(x) = x⁴ 8x³ 12x² 17x 6 = (x² 7x 3)(x² x 2).

Împărțind pe a(x) la b(x) rezultă un rest r₀(x) = x³ (2/3) x² (5/3) x − (2/3). În pasul următor, b(x) se împarte la r₀(x) rezultând restul r₁(x) = x² x 2. Împărțind, apoi, r₀(x) la r₁(x) rezultă un rest nul, indicând că r₁(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. 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țurile Sturm, o tehnică de numărare a rădăcinilor reale ale polinoamelor într-un interval dat de pe 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, 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.

Întregii gaussieni

Distribuția numerelor prime gaussiene u   vi în planul complex, cu norma u²   v² mai mică decât 500

Întregii gaussieni sunt numere complexe de forma α = u   vi, unde u și v sunt numere întregi obișnuite și i este unitatea imaginară. Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o factorizare unică, conform demonstrației de mai sus. Unicitatea factorizării este utilă în mai multe aplicații, cum ar fi calculul tuturor tripletelor pitagoreice sau demonstrația Primei teoreme a lui Fermat a sumei a două pătrate. Î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_k și un rest r_k astfel încât

r_k = r_k−2 − q_k r_k−1

unde r_k−2 = α, r_k−1 = β, și fiecare rest este strict mai mic decât predecesorul său, |r_k| < |r_k−1|. Prima diferență este aceea că resturile și câturile sunt și ele numere întregi gaussiene, și deci complexe. Câturile q_k 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 funcție normă f(u vi) = u² v², care transformă fiecare întreg gaussian u vi la un număr întreg. După fiecare pas k al algoritmului lui Euclid, norma restului f(r_k) este mai mică decât norma restului precedent, f(r_k−1). 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. 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 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 commutativitatea, asociativitatea și distributivitate.

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 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 domeniu cu ideale principale^⁠(d), domeniu de integritate în care fiecare 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. Unicitatea factorizării este și element cheie într-o tentativă de demonstrare a 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. Abordarea lui Lamé impunea unicitatea factorizării numerelor de forma x ωy, unde ω = e^2iπ/n este rădăcina de ordin n a lui 1, adică, ωⁿ = 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.

Unicitatea factorizării întregilor cuadratici

Distribuția numerelor prime Eisenstein u   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 = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 sau 73. Întregii cuadratici cu D = −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ă. Primul exemplu de domeniu euclidian nu era cu funcție normă (D=69) și a fost publicat în 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ă; Demonstrația lui Weinberger a fost generalizată în 2004 pentru a elimina această restricție.

Inele necomutative

Algoritmul lui Euclid se poate aplica pe inele necomutative, ca și pe mulțimea cuaternionilor Hurwitz. 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

ρ₀ = α − ψ₀β = (ξ − ψ₀η)δ

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

ρ₀ = α − βψ₀ = δ(ξ − ηψ₀)

Î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 ρ₀ trebuie să fie strict mai mică decât β, și trebuie să existe doar un număr finit de mărimi posibile pentru ρ₀, 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ă

Γ_dreapta = σα τβ

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

Γ_stânga = ασ βτ

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

Generalizări la alte structuri matematice

Algoritmul lui Euclid se poate aplica în teoria nodurilor.

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_k = r_k−2 − q_k r_k−1

în care fiecare rest este strict mai mic decât predecesorul său, |r_k| < |r_k−1|. A doua, dimensiunea fiecărui rest are o limită inferioară strictă, cum ar fi |r_k| ≥ 0. A treia, există doar un număr finit de dimensiuni mai mici ca un rest dat |r_k|. Generalizările algoritmului lui Euclid cu aceste trăsături de bază s-au aplicat și altor structuri matematice, cum ar fi nodurile și numerele ordinale transfinite.

O importantă generalizare a algoritmului lui Euclid este conceptul de bază Gröbner din 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ă. În acest caz, se poate defini o mulțime finită de polinoame generatoare g₁, g₂ 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 = Σ_k m_kg_k

unde s, t și m_k sunt polinoame de mai multe variabile. 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 Σ_k q_kg_k

deși polinoamele cât q_k pot să nu fie unice. Mulțimea acestor polinoame generatoare se numește bază Gröbner.

Bibliografie

• Cohen H (1993). A Course in Computational Algebraic Number Theory. New York: Springer-Verlag. ISBN 0-387-55640-0. 
• Cohn H (1962). Advanced Number Theory. New York: Dover. ISBN 0-486-64023-X. 
• Cormen TH, Leiserson CE, Rivest RL, and Stein C (2001). Introduction to Algorithms (ed. 2nd). MIT Press and McGraw–Hill. ISBN 0262032937. Mentenanță CS1: Nume multiple: lista autorilor (link)
• Cox D, Little J, and O'Shea D (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (ed. 2nd). Springer-Verlag. ISBN 0-387-94680-2. Mentenanță CS1: Nume multiple: lista autorilor (link)
• Dirichlet PGL (1894). Richard Dedekind, ed. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg. 
• Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman]. (2008). An Introduction to the Theory of Numbers (ed. 6th). Oxford: Clarendon Press. 
• Knuth D (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (ed. 3rd). Addison–Wesley. ISBN 0201896842. 
• LeVeque WJ (1977). Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9. 
• Mollin RA (2008). Fundamental Number Theory with Applications (ed. 2nd). Boca Raton: Chapman & Hall/CRC. ISBN 9781420066593. 
• Ore Ø (1948). Number Theory and Its History. New York: McGraw–Hill. 
• Rosen KH (2000). Elementary Number Theory and its Applications (ed. 4th). Reading, MA: Addison–Wesley. ISBN 0201870738. 
• Schroeder MR (2005). Number Theory in Science and Communication (ed. 4th). Springer-Verlag. ISBN 0387158006. 
• Stark H (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8. 
• Stillwell J (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 0-387-98289-2. 
• Tattersall JJ (2005). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. ISBN 9780521850148. 
• Uspensky JV, Heaslet MA (1939). Elementary Number Theory. New York: McGraw–Hill. 

Legături externe

• Demonstrații ale algoritmului lui Euclid
• Eric W. Weisstein, Euclidean Algorithm la MathWorld.
• Algoritmul lui Euclid la cut-the-knot
• Euclid's algorithm la PlanetMath
• Algoritmul lui Euclid la MathPages
• Jocul lui Euclid la cut-the-knot
• Muzica și algoritmul lui Euclid