Î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]
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.
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),[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.
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ă
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]
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.[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
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
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
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
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
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
Î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]
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]
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.[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
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
Î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ă
Î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
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
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
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
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
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
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 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
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
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
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
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
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]
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.[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
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
Î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
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
Î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
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.
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]
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
