Wikipedia

Algoritmul lui Euclid

Î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.[1]

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.

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 modificare

Cel mai mare divizor comun modificare

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),[2] 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.[3] Această proprietate nu depinde de primalitatea lui a și a lui b.[4] 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.[5]

CMMDC poate fi vizualizat geometric după cum urmează.[6] 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.[7] 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.[8][9] Factorizarea numerelor întregi mari este considerată a fi o problemă atât de dificilă încât multe sisteme criptografice moderne se bazează pe ea.[10]

O definiție mai subtilă a CMMDC este utilă în matematica avansată, în particular în teoria inelelor.[11] 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,[12] care poate fi calculat luând CMMDC pe perechi de numere.[13] 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ă modificare

Trei metode matematice sunt utilizate mai jos: inducția, recursivitatea și coborârea infinită. Inducția[14] este utilizată adesea pentru a demonstra o teoremă pentru toate numerele naturale n.[15] 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[16] este proprietatea ei de a lega numerele ce formează un șir a1, a2, a3, etc.[17] 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ă,[18] o soluție dată în numere naturale este utilizată pentru a construi o soluție cu numere naturale mai mici.[19] 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.[20]

Descriere modificare

Procedură modificare

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.[21] 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.[20] 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 modificare

Corectitudinea algoritmului lui Euclid se poate demonstra în doi pași.[21] 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.

Î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 rk. 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 r0, întrucât r0 = a − q0b = mc − q0nc = (m − q0n)c. O demonstrație analogă arată că c divide și celelalte resturi r1, r2, etc. Deci cel mai mare divizor comun g divide rN−1, de unde rezultă că g ≤ rN−1. Întrucât în prima parte a demonstrației s-a arătat că (rN−1 ≤ g), rezultă că g = rN−1. Deci g este cel mai mare divizor comun al tuturor perechilor succesive:[22][23]

g = CMMDC(a, b) = CMMDC(b, r0) = CMMDC(r0, r1) = … = CMMDC(rN−2, rN−1) = rN−1

Exemplu modificare

 
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 (q0 = 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 (q1 = 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 (q2 = 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 modificare

Algoritmul lui Euclid poate fi vizualizat în termenii analogiei pătratelor dată mai sus pentru cel mai mare divizor comun.[24] 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 r0-pe-b neacoperit, unde r0<b. Atunci se încearcă împărțirea dreptunghiului rezidual cu pătrate r0-pe-r0. Rămâne un al doilea dreptunghi rezidual r1-pe-r0, pe care se încearcă să fie acoperit cu pătrate r1-pe-r1, ș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 modificare

La fiecare pas k, algoritmul lui Euclid calculează un cât qk și un rest rk ale două numere rk−1 și rk−2

rk−2 = qk rk−1 + rk

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

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

rk ≡ rk−2 mod rk−1

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

Implementări modificare

Implementările algoritmului se pot exprima în pseudocod. De exemplu, versiunea bazată pe împărțire trebuie să fie programată ca[26]

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

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

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 rk−1 și rk−2. Se presupune că a este mai mare ca b la începutul unei iterații; atunci a este egal cu rk−2, fiindcă rk−2 > rk−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 rk. Atunci b este redus cu multipli ai lui a până când este mai mic decât a, dând următorul rest rk+1, și așa mai departe.

Versiunea recursivă[28] se bazează pe egalitatea CMMDC al resturilor succesive și pe condiția de oprire CMMDC(rN−1, 0) = rN−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 modificare

Î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.[29][30] Anterior, ecuația

rk−2 = qk rk−1 + rk

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

rk−2 = (qk + 1) rk−1 + ek

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

Istoric modificare

 
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.[31] 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.[32][33] 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.[34] Algoritmul a fost probabil cunoscut lui Eudoxus din Cnidus (circa 375 î.e.n.)[31][35] Algoritmul ar putea fi dinainte chiar și de Eudoxus,[36][37] judecând după utilizarea termenului tehnic ἀνθυφαίρεσις (anthyphairesis, scădere reciprocă) din lucrările lui Euclid și Aristotel.[38]

După mai multe secole, algoritmul lui Euclid a fost descoperit independent în India și în China,[39] ș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”,[40] poate din cauza eficienței sale în rezolvarea de ecuațiilor diofantice.[41] Deși un caz special al teoremei chinezești a resturilor fusese deja descris de matematicianul și astronomul chinez Sun Tzu,[42] soluția generală a fost publicată de Qin Jiushao în cartea sa din 1247 intitulată Shushu Jiuzhang (數書九章 „Tratat matematic în nouă secțiuni”).[43] 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).[40] Î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.[44]

Î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.[45] Gauss a menționat algoritmul în Disquisitiones Arithmeticae (publicat la 1801), dar numai ca metodă pentru fracțiile continue.[39] Peter Dirichlet pare a fi fost primul care a descris algoritmul lui Euclid ca bază pentru teoria numerelor.[46] 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.[47] 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.[48] 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.[49]

„[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.[50]

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,[51] și algoritmii asociați, algoritmul LLL, algoritmul HJLS și algoritmul PSLQ.[52][53]

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

Aplicații matematice modificare

Identitatea lui Bézout modificare

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

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

g = rN−1 = rN−3 − qN−1 rN−2

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

rN−2 = rN−4 − qN−2 rN−3
rN−3 = rN−5 − qN−3 rN−4

Înlocuind aceste formule pentru rN−2 și rN−3 în prima ecuație rezultă g sub formă de combinație liniară a resturilor rN−4 și rN−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

r2 = r0 − q2 r1
r1 = b − q1 r0
r0 = a − q0 b

După ce toate resturile r0, r1 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 modificare

Identitatea lui Bézout dă o altă definiție a celui mai mare divizor comun g al două numere a și b.[11] 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.[62] 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 modificare

Î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[63]

sk = sk−2 − qk−1sk−1
tk = tk−2 − qk−1tk−1

cu valorile de început

s−2 = 1, t−2 = 0
s−1 = 0, t−1 = 1

Cu ajutorul acestei relații de recurență, întregii lui Bézout s și t sunt dați de s = sN și t = tN, unde N este pasul la care algoritmul se termină cu rN = 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ă

rj = sj a + tj b

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

rk = rk−2 − qk−1rk−1

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

rk = (sk−2 a + tk−2 b) − qk−1(sk−1 a + tk−1 b)

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

rk = sk a + tk b = (sk−2 − qk−1sk−1) a + (tk−2 − qk−1tk−1) b

Metoda matricială modificare

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

a = q0 b + r0
b = q1 r0 + r1
…
rN−2 = qN rN−1 + 0

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

 

Fie M produsul tuturor matricelor–cât

 

Aceasta simplifică algoritmul lui Euclid la forma

 

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.[64][65] 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

 

Deoarece ecuația de sus dă

g = (−1)N+1 ( m22 a − m12 b)

cei doi întregi ai identității lui Bézout sunt s = (−1)N+1m22 și t = (−1)Nm12. 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 modificare

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.[66] 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:[67] 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 a1, a2, …, an, atunci w este prim și cu produsul lor, a1 × a2 × … × an.[67]

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

L = p1p2…pm = q1q2…qn

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

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

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

În general, o ecuație diofantică liniară fie nu are soluție, fie are un număr infinit de soluții.[72] Pentru a demonstra cel de-al doilea caz, se consideră două soluții, (x1, y1) și (x2, y2)

ax1 + by1 = c = ax2 + by2

sau echivalent

a(x1 − x2) = b(y2 − y1).

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 = x1 − bt/g
y = y1 + 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ă (x1, y1). 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;[73] 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 modificare

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−1 astfel încât aa−1 = a−1a ≡ 1 mod m. Acest invers se poate găsi rezolvând ecuația ax ≡ 1 mod m,[74] sau ecuația diofantică liniară echivalentă[75]

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.[76] 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.[77]

Teorema chinezească a resturilor modificare

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

x1 ≡ x mod m1
x2 ≡ x mod m2
…
xN ≡ x mod mN

Scopul este determinarea lui x din cele N resturi xi. 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 mi, și definind Mi

Mi = M / mi

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

Mihi ≡ 1 mod mi

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

x ≡ (x1M1h1 + x2M2h2 + … + xNMNhN ) mod M

Deoarece aceste numere hi sunt inversele multiplicative ale numerelor Mi, ele se pot găsi folosind algoritmul lui Euclid așa cum s-a arătat în subsecțiunea anterioară.

Fracții continue modificare

Algoritmul luo Euclid este în strânsă relație cu noțiunea de fracție continuă.[80] Șirul de ecuații poate fi scris sub forma

a/b = q0 + r0/b
b/r0 = q1 + r1/r0
r0/r1 = q2 + r2/r1
…
rk−2/rk−1 = qk + rk/rk−1
…
rN−2/rN−1 = qN

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 = q0 + 1/(q1 + r1/r0)

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

a/b = q0 + 1/(q1 + 1/(q2 + r2/r1))

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

a/b = q0 + 1/(q1 + 1/(q2 + 1/(… + 1/qN))…) = [q0; q1, q2, …, qN]

În exemplul de mai sus, s-a calculat CMMDC(1071, 462), iar câturile qk 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 modificare

Calculul celui mai mare divizor comun este un pas esențial în mai mulți algoritmi de factorizare a întregilor,[81] cum ar fi Pollard's rho algorithm,[82] algoritmul lui Shor,[83] metoda de factorizare a lui Dixon[84] și factorizarea Lenstra cu curbe eliptice.[85] 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.[86]

Eficiența algoritmului modificare

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

Numărul de pași modificare

Numărul de pași necesari pentru calculul CMMDC a două numere naturale, a și b, se poate nota cu T(a, b).[91] 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.[92] 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, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1

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

Numărul maxim de pași modificare

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 FN+2 respectiv FN+1.[93] Aceasta se poate arăta prin inducție.[94] 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 F2 și respectiv F3. 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 = q0b + r0, iar al doilea pas este b = q1r0 + r1. Algoritmul fiind recursiv, el a rulat M−1 pași pentru a găsi CMMDC(b, r0) iar valorile lor cele mai mici sunt FM+1 și FM. Cea mai mică valoare a lui a este deci cea cu q0 = 1, de unde a = b + r0 = FM+1 + FM = FM+2. Această demonstrație, publicată de Gabriel Lamé în 1844, reprezintă începuturile teoriei complexității computaționale,[95] fiind și prima aplicație practică a șirului lui Fibonacci.[93]

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).[96] Dacă algoritmul rulează în N pași, atunci b este mai mare sau egal cu FN+1 care este mai mare sau egal cu φN, unde φ este raportul de aur. Cum b > φN, atunci N < logφb. Întrucât log10φ > 1/5, N/5 < log10φ logφb = log10b. Astfel, N < 5 log10b. 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 modificare

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[91]

 

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

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

 

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[98][99]

τ(a) = (12/π2) 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/π2)( 4γ − 24π2ζ '(2) + 3 ln 2 − 2) ≈ 1.467

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

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

 

ea poate fi aproximată prin formula[105]

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

unde Λ(d) este funcția Mangoldt.[106]

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[105]

 

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

Y(n) ≈ (12/π2) ln 2 ln n + 0.06.

Costul computațional al unui pas modificare

La fiecare pas k al algoritmului lui Euclid, se calculează câtul qk și restul rk pentru o pereche dată de întregi rk−2 și rk−1

rk−2 = qk rk−1 + rk.

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

rk = rk−2 − qk rk−1.

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

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)2.[109] 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,[110] algoritmul lui Euclid bazat pe scăderi este competitiv cu cel bazat pe împărțiri.[111] Acest aspect este exploatat de versiunea binară a algoritmului lui Euclid.[112]

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ă (h2) în funcție de numărul de cifre h al celor două numere inițiale a și b. Fie h0, h1, …, hN−1 numărul de cifre ale resturilor succesive r0, r1, …, rN−1. Cum numărul de pași N crește liniar cu h, timpul de execuție este limitat de

 

Eficiența unor metode alternative modificare

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.[7] Metodele actuale de factorizare sunt și ele ineficiente; multe alte sisteme criptografice se bazează tocmai pe această ineficiență.[10]

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.[113][114] 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.[115] Eficiența se poate îmbunătăți examinând doar primele cifre ale numerelor a și b.[116][117] Algoritmul binar poate fi extins la alte baze (algoritmi k-ari)[118], cu creșteri ale vitezei de până la cinci ori.[119]

O abordare recursivă pentru numere întregi foarte mari (cu peste 25.000 de cifre) conduce la algoritmi CMMDC subcuadratici,[120] cum ar fi cel al lui Schönhage[121][122] și cel al lui Stehlé și Zimmermann.[123] 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)2 (log log h)).[115][124]

Alte sisteme de numere modificare

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 modificare

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.[32] 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.[125][126]

Algoritmul lui Euclid pe numere reale diferă de cel pe întregi prin două aspecte. Primul este că resturile rk sunt numere reale, deși câturile qk 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ă [q0; q1, q2, …, qN]. 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ă [q0; q1, q2, …]. 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 [q0; q1, q2, …, qk] 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 mk/nk; numărătorul și numitorul sunt prime între ele și respectă relația recursivă

mk = qk mk−1 + mk−2
nk = qk nk−1 + nk−2

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

 

Polinoame modificare

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

rk−2(x) = qk(x) rk−1(x) + rk(x)

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

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

a(x) = x4 − 4x3 + 4 x2 − 3x + 14 = (x2 − 5x + 7)(x2 + x + 2)

și

b(x) = x4 + 8x3 + 12x2 + 17x + 6 = (x2 + 7x + 3)(x2 + x + 2).

Împărțind pe a(x) la b(x) rezultă un rest r0(x) = x3 + (2/3) x2 + (5/3) x − (2/3). În pasul următor, b(x) se împarte la r0(x) rezultând restul r1(x) = x2 + x + 2. Împărțind, apoi, r0(x) la r1(x) rezultă un rest nul, indicând că r1(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.[129] 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.[127]

Întregii gaussieni modificare

 
Distribuția numerelor prime gaussiene u + vi în planul complex, cu norma u2 + v2 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ă.[130] 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.[45] 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.[130] Î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 qk și un rest rk astfel încât

rk = rk−2 − qk rk−1

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

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.[131][132] 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.[130] 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.[133] Abordarea lui Lamé impunea unicitatea factorizării numerelor de forma x + ωy, unde ω = e2iπ/n este rădăcina de ordin n a lui 1, adică, ωn = 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 modificare

 
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.[25] Î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ă.[134] Primul exemplu de domeniu euclidian nu era cu funcție normă (D=69) și a fost publicat în 1994.[134] Î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ă;[135] Demonstrația lui Weinberger a fost generalizată în 2004 pentru a elimina această restricție.[136]

Inele necomutative modificare

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

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

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

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

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

 
Algoritmul lui Euclid se poate aplica în teoria nodurilor.[138]

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

rk = rk−2 − qk rk−1

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

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ă.[141] În acest caz, se poate defini o mulțime finită de polinoame generatoare g1, g2 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 mkgk

unde s, t și mk sunt polinoame de mai multe variabile.[142] 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 qkgk

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

Note modificare

  1. ^ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
  2. ^ Stark, p. 16.
  3. ^ Stark, p. 21.
  4. ^ LeVeque, p. 32.
  5. ^ Leveque, p. 31.
  6. ^ Grossman JW (). Discrete Mathematics. New York: Macmillan. p. 213. ISBN 0-02-348331-8. 
  7. ^ a b Schroeder, pp. 21–22.
  8. ^ Schroeder, p. 19.
  9. ^ Ogilvy CS, Anderson JT (). Excursions in number theory. New York: Oxford University Press. pp. 27–29. LCCN 66-14484. 
  10. ^ a b Schroeder, pp. 216–219.
  11. ^ a b Leveque, p. 33.
  12. ^ Stark, p. 25.
  13. ^ Ore, pp. 47–48.
  14. ^ Knuth, Donald E. (). The Art of Computer Programming, Volume 1: Fundamental Algorithms (ed. 3rd). Addison-Wesley. ISBN 0-201-89683-4.  (Secțiunea 1.2.1: Mathematical Induction, pp. 11–21.)
  15. ^ Rosen, pp. 18–21.
  16. ^ Rosen, pp. 21–24.
  17. ^ Anderson JA (). Discrete Mathematics with Combinatorics. Upper Saddle River, NJ: Prentice Hall. pp. 165–223. ISBN 0-13-086998-8. 
  18. ^ Rosen, p. 492.
  19. ^ Anderson JA (). Discrete Mathematics with Combinatorics. Upper Saddle River, NJ: Prentice Hall. pp. 109–119. ISBN 0-13-086998-8. 
  20. ^ a b Stark, p. 18.
  21. ^ a b Stark, pp. 16–20.
  22. ^ Knuth, p. 320.
  23. ^ Lovász L, Pelikán J, Vesztergombi K (). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. pp. 100–101. ISBN 0-387-95584-4. 
  24. ^ Kimberling C (). „A Visual Euclidean Algorithm”. Mathematics Teacher. 76: 108–109. 
  25. ^ a b Cohn, pp. 104–110.
  26. ^ Knuth, pp. 319–320.
  27. ^ Knuth, pp. 318–319.
  28. ^ Stillwell, p. 14.
  29. ^ a b Ore, p. 43.
  30. ^ a b Stewart BM (). Theory of Numbers (ed. 2nd). New York: Macmillan. pp. 43–44. LCCN 64-10964. 
  31. ^ a b Knuth, p. 318.
  32. ^ a b Weil A (). Number Theory. Boston: Birkhäuser. pp. 4–6. ISBN 0-8176-3141-0. 
  33. ^ Jones A (). „Greek mathematics to AD 300”. Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. pp. 46–48. ISBN 0-415-09238-8. 
  34. ^ van der Waerden BL (). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. pp. 114–115. 
  35. ^ von Fritz K (). „The Discovery of Incommensurability by Hippasus of Metapontum”. Ann. Math. 46: 242–264. doi:10.2307/1969021. 
  36. ^ Heath TL (). Mathematics in Aristotle. Oxford Press. pp. 80–83. 
  37. ^ Fowler DH (). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66. ISBN 0-19-853912-6. 
  38. ^ Becker O (). „Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid”. Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333. 
  39. ^ a b Stillwell, p. 31.
  40. ^ a b Tattersall, p. 70.
  41. ^ Rosen, pp. 86–87.
  42. ^ Ore, pp. 247–248.
  43. ^ Tattersall, pp. 72, 184–185.
  44. ^ Tattersall, pp. 72–76.
  45. ^ a b Gauss CF (). „Theoria residuorum biquadraticorum”. Comm. Soc. Reg. Sci. Gött. Rec. 4.  Vezi și Werke, 2:67–148.
  46. ^ Stillwell, pp. 31–32.
  47. ^ Dirichlet, pp. 29–31.
  48. ^ Dedekind R (). „Supplement XI”. În PGL Dirichlet. Vorlesungen über Zahlentheorie. 
  49. ^ Stillwell J (). Elements of Number Theory. New York: Springer-Verlag. pp. 41–42. ISBN 0-387-95587-9. 
  50. ^ Sturm C (). „Mémoire sur la résolution des équations numériques”. Bull. des sciences de Férussac. 11: 419–422. 
  51. ^ Eric W. Weisstein, Integer Relation la MathWorld.
  52. ^ Peterson I (). „Jazzing Up Euclid's Algorithm”. ScienceNews.  Legătură externa în |title= (ajutor)
  53. ^ Cipra BA (). „The Best of the 20th Century: Editors Name Top 10 Algorithms”. SIAM News. Society for Industrial and Applied Mathematics. 33 (4).  Legătură externa în |title= (ajutor)
  54. ^ engleză {{{1}}}Cole AJ, Davie AJT (). „A game based on the Euclidean algorithm and a winning strategy for it”. Math. Gaz. 53: 354–357. doi:10.2307/3612461. 
  55. ^ Spitznagel EL (). „Properties of a game based on Euclid's algorithm”. Math. Mag. 46: 87–92. 
  56. ^ Rosen, p. 95.
  57. ^ Roberts J (). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. pp. 1–8. ISBN 0-262-68028-0 Verificați valoarea |isbn=: checksum (ajutor). 
  58. ^ Jones GA, Jones JM (). „Bezout's Identity”. Elementary Number Theory. New York: Springer-Verlag. pp. 7–11. 
  59. ^ Rosen, p. 81.
  60. ^ Cohn, p. 104.
  61. ^ Rosen, p. 91.
  62. ^ Schroeder, p. 23.
  63. ^ Rosen, pp. 90–93.
  64. ^ a b Koshy T (). Elementary Number Theory with Applications. Burlington, MA: Harcourt/Academic Press. pp. 167–169. ISBN 0-12-421171-2. 
  65. ^ Bach E, Shallit J (). Algorithmic number theory. Cambridge, MA: MIT Press. pp. 70–73. ISBN 0-262-02405-5. 
  66. ^ Stark, pp. 26–36.
  67. ^ a b Ore, p. 44.
  68. ^ Stark, pp. 281–292.
  69. ^ Rosen, pp. 119–125.
  70. ^ Schroeder, pp. 106–107.
  71. ^ Schroeder, pp. 108–109.
  72. ^ Rosen, pp. 120–121.
  73. ^ Stark, p. 47.
  74. ^ Schroeder, pp. 107–109.
  75. ^ Stillwell, pp. 186–187.
  76. ^ Schroeder, p. 134.
  77. ^ "Error correction coding: mathematical methods and algorithms", pagina 266, Todd K. Moon, John Wiley and Sons, 2005, ISBN 0-471-64800-0
  78. ^ Rosen, pp. 143–170.
  79. ^ Schroeder, pp. 194–195.
  80. ^ Vinogradov IM (). Elements of Number Theory. New York: Dover. pp. 3–13. 
  81. ^ Crandall R, Pomerance C (). Prime Numbers: A Computational Perspective (ed. 1st). New York: Springer-Verlag. pp. 225–349. ISBN 0-387-94777-9. 
  82. ^ Knuth, pp. 369–371.
  83. ^ Shor PW (). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM J. Sci. Statist. Comput. 26: 1484. 
  84. ^ Dixon JD (). „Asymptotically fast factorization of integers”. Math. Comput. 36: 255–260. doi:10.2307/2007743. 
  85. ^ Lenstra Jr. HW (). „Factoring integers with elliptic curves”. Annals of Mathematics. 126: 649–673. doi:10.2307/1971363. 
  86. ^ Knuth, pp. 380–384.
  87. ^ Knuth, pp. 339–364.
  88. ^ Lamé G (). „Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers”. Comptes Rendus Acad. Sci. 19: 867–870. 
  89. ^ Grossman H (). „On the Number of Divisions in Finding a G.C.D”. The American Mathematical Monthly. 31: 443. doi:10.2307/2298146. 
  90. ^ Honsberger R (). Mathematical Gems II. The Mathematical Association of America. pp. 54–57. ISBN 0-88385-302-7. 
  91. ^ a b c Knuth, p. 344.
  92. ^ Ore, p. 45.
  93. ^ a b Knuth, p. 343.
  94. ^ Mollin, p. 21.
  95. ^ LeVeque, p. 35.
  96. ^ Mollin, pp. 21–22.
  97. ^ Knuth, p. 353.
  98. ^ Knuth, p. 357.
  99. ^ Tonkov T (). „On the average length of finite continued fractions”. Acta arithmetica. 26: 47–57. 
  100. ^ Porter JW (). „On a Theorem of Heilbronn”. Mathematika. 22: 20–28. 
  101. ^ Knuth DE (). „Evaluation of Porter's Constant”. Computers and Mathematics with Applications. 2: 137–139. doi:10.1016/0898-1221(76)90025-0. 
  102. ^ Dixon JD (). „The Number of Steps in the Euclidean Algorithm”. J. Number Theory. 2: 414–422. doi:10.1016/0022-314X(70)90044-2. 
  103. ^ Heilbronn HA (). „On the Average Length of a Class of Finite Continued Fractions”. În Paul Turán. Number Theory and Analysis. New York: Plenum. pp. 87–96. LCCN 68-8991. 
  104. ^ Knuth, p. 354.
  105. ^ a b Norton GH (). „On the Asymptotic Analysis of the Euclidean Algorithm”. Journal of Symbolic Computation. 10: 53–58. doi:10.1016/S0747-7171(08)80036-3. 
  106. ^ Knuth, p. 355.
  107. ^ Knuth, p. 356.
  108. ^ Knuth, pp. 257–261.
  109. ^ Knuth, p. 352.
  110. ^ Wagon S (). Mathematica in Action. New York: Springer-Verlag. pp. 335–336. ISBN 0-387-98252-3. 
  111. ^ Cohen, p. 14.
  112. ^ Cohen, pp. 14–15, 17–18.
  113. ^ Knuth, pp. 321–323.
  114. ^ Stein J (). „Computational problems associated with Racah algebra”. Journal of Computational Physics. 1: 397–405. doi:10.1016/0021-9991(67)90047-2. 
  115. ^ a b Crandall R, Pomerance C (). Prime Numbers: A Computational Perspective (ed. 1st). New York: Springer-Verlag. pp. 77–79, 81–85, 425–431. ISBN 0-387-94777-9. 
  116. ^ Knuth, p. 328.
  117. ^ Lehmer DH (). „Euclid's Algorithm for Large Numbers”. The American Mathematical Monthly. 45: 227–233. doi:10.2307/2302607. 
  118. ^ Sorenson J (). „Two fast GCD algorithms”. J. Algorithms. 16: 110–144. doi:10.1006/jagm.1994.1006. 
  119. ^ Weber K (). „The accelerated GCD algorithm”. ACM Trans. Math. Soft. 21: 111–122. doi:10.1145/200979.201042. 
  120. ^ Aho A, Hopcroft J, Ullman J (). The Design and Analysis of Computer Algorithms. New York: Addison–Wesley. pp. 300–310. 
  121. ^ Schönhage A (). „Schnelle Berechnung von Kettenbruchentwicklungen”. Acta Informatica. 1: 139–144. doi:10.1007/BF00289520. 
  122. ^ Cesari G (). „Parallel implementation of Schönhage's integer GCD algorithm”. În G. Buhler. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. New York: Springer-Verlag. pp. 64–76.  Volume 1423 in Lecture notes in Computer Science.
  123. ^ Stehlé D, Zimmermann P (). „Gal's accurate tables method revisited”. Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, CA: IEEE Computer Society Press. 
  124. ^ Möller N (). „On Schönhage's algorithm and subquadratic integer gcd computation”. Mathematics of Computation. 77: 589–607. doi:10.1090/S0025-5718-07-02017-0.  Legătură externa în |title= (ajutor)
  125. ^ Boyer CB, Merzbach UC (). A History of Mathematics (ed. 2nd). New York: Wiley. pp. 116–117. ISBN 0-471-54397-7. 
  126. ^ Cajori F (). A History of Mathematics. New York: Macmillan. p. 70. 
  127. ^ a b Lang S (). Algebra (ed. 2nd). Menlo Park, CA: Addison–Wesley. pp. 190–194. ISBN 0-201-05487-6. 
  128. ^ Cox, pp. 37–46.
  129. ^ Schroeder, pp. 254–259.
  130. ^ a b c Stillwell J (). Elements of Number Theory. New York: Springer-Verlag. pp. 101–116. ISBN 0-387-95587-9. 
  131. ^ Stark, p. 290.
  132. ^ Cohn, pp. 104–105.
  133. ^ Lamé G (). „Mémoire sur la résolution, en nombres complexes, de l'équation An + Bn + Cn = 0”. J. Math. Pures Appl. 12: 172–184. 
  134. ^ a b Clark DA (). „A quadratic field which is Euclidean but not norm-Euclidean”. Manuscripta mathematica. 83: 327–330. doi:10.1007/BF02567617.  Legătură externa în |title= (ajutor)
  135. ^ Weinberger P. Proc. Sympos. Pure Math. 24: 321–332.  Lipsește sau este vid: |title= (ajutor); |chapter= ignorat (ajutor)
  136. ^ Harper M, Murty, MR (). „Euclidean Rings of Algebraic Integers”. Canadian Journal of Mathematics. 56: 71–76.  Legătură externa în |title= (ajutor)
  137. ^ Stillwell J (). Elements of Number Theory. New York: Springer-Verlag. pp. 151–152. ISBN 0-387-95587-9. 
  138. ^ Yamada Y (). „Generalized rational blow-down, torus knots, and Euclidean algorithm”. arXiv:0708.2316v1.  Legătură externa în |title= (ajutor)
  139. ^ Conway, John (). „An enumeration of knots and links, and some of their algebraic properties”. Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967). Pergamon. pp. 329–358.  Parametru necunoscut |middle= ignorat (ajutor)
  140. ^ Jategaonkar AV (). „Rings with transfinite left division algorithm”. Bull. Amer. Math. Soc. 75: 559–561. doi:10.1090/S0002-9904-1969-12242-1.  Legătură externa în |title= (ajutor)
  141. ^ Cox, p. 65.
  142. ^ Cox, pp. 73–79.
  143. ^ Cox, pp. 79–86.
  144. ^ Cox, p. 74.

Bibliografie modificare

Legături externe modificare


Adus de la https://ro.wikipedia.org/w/index.php?title=Algoritmul_lui_Euclid&oldid=15973338