Algorisme d'Euclides

De Viquipèdia
Dreceres ràpides: navegació, cerca

L'algorisme d'Euclides[a] és un mètode eficaç per a calcular el màxim comú divisor (mcd) entre dos nombres enters. Rep el nom del matemàtic grec Euclides el qual el va descriure en els volums VII i X del llibre Elements.[1]

L'algorisme consisteix en diverses divisions enteres successives. En la primera divisió, es pren com a dividend el major dels nombres i com a divisor l'altre. Després, el divisor i el residu serveixen respectivament de dividend i divisor de la següent divisió. El procés es para quan s'obté un residu nul. El mcd és llavors el penúltim residu de l'algorisme.
Formalment, si anomenem a, b els enters inicials, r1, rn ... rn-1 i rn = 0 els residus successius, llavors:

mcd (a, b) = mcd (b, r1), amb r1 = a - b·q (q és el quocient de a per b)

Després el menor dels divisors comuns és el mateix, i repetint l'operació:

mcd (b, r1) = mcd (r1, r2) = mcd (r2, r3) = ... = mcd (rn-1, rn) = mcd (rn-1, 0) = rn-1.

Això permet detallar l'algorisme efectiu:

  • dades d'entrada a i b   -  si fa falta, canviar-los a positius
  • l'algorisme:
mentre b ≠ 0 repetir les tres instruccions següents:
r ← residu de a per b     (donar a r el valor del residu de a per b)      
a ← b     (el nou valor de a és l'antic valor de b)
b ← r     (el nou valor de b és el valor de r)
  • el resultat és a (el seu últim valor).

Aquest algorisme dóna com a resultat 0 si a i b són nuls, mentre que en matemàtiques el major divisor de zero no existix.

Fonaments[modifica | modifica el codi]

Màxim comú divisor[modifica | modifica el codi]

L'algorisme d'Euclides calcula el màxim comú divisor (MCD) de dos nombres naturals a i b. El màxim comú divisor g és el nombre natural més gran que divideixi els dos a i b és a dir, que al dividir tant a com b entre g el residu és zero. El màxim comú divisor s'escriu sovint com MCD(a, b) o, més simplement, com (a, b),[2] encara que l'última notació també es fa servir per a altres conceptes matemàtics, com vectors bidimensionals.

Si MCD(a, b) = 1, llavors a i b s'anomenen coprimers.[3] Aquesta propietat és independent de si a i b són ells mateixos nombres primers.[4] Per exemple, ni 6 ni 35 són nombres primers, ja que els dos tenen dos factors primers: 6 = 2 × 3 i 35 = 5 × 7. No obstant això, 6 i 35 són coprimers. Cap nombre natural diferent d'1 no és divisor al mateix temps de 6 i de 35, ja que no tenen cap factor primer en comú.

"Rectangle dividit en un reixat de quadrats. El rectangle és de dos quadrats d'ample i cinc quadrats d'alt."
Un rectangle de 24-per-60 es cobreix amb deu rajoles quadrades de 12-per-12, on 12 és el MCD de 24 i 60. De forma més general, un rectangle de a -per- b pot ser cobert amb rajoles quadrades de llargada de costat c només si c és un divisor comú de a i b.

Sia g = MCD(a, b). Com que a i b són tots dos múltiples de g, es poden escriure com a = mg i b = ng, i no hi ha cap nombre més gran G > g per al qual això es compleixi. Els nombres naturals m i n han de ser coprimers, ja que qualsevol factor comú es podria treure de m i n i fer g més gran. Així, qualsevol altre nombre c que divideix els dos a i b també ha de dividir g. El màxim comú divisor g de a i b es pot definir com el comú divisor que és divisible per qualsevol altre comú divisor c .[5]

El MCD es pot visualitzar de la manera següent.[6] Es considera una àrea rectangular a per b, i qualsevol divisor comú c que divideix tant a com b exactament. Els costats del rectangle es poden dividir en segments de llargada c, que divideix el rectangle en un reixat de quadrats de llargada de costat c. El màxim comú divisor g és el valor més gran de c per al qual això és possible. Per a la il·lustració, una àrea rectangular de 24-per-60 pot ser dividida a un reixat de: quadrats d'1-per-1, quadrats de 2-per-2, quadrats de 3-per-3, quadrats de 6-per-6 o quadrats de 12-per-12. Per això, 12 és el màxim comú divisor de 24 i 60. Una àrea rectangular de 24-per-60 pot ser dividida en un reixat de quadrats de 12-per-12, amb dos quadrats al llarg d'una aresta (24/12 = 2) i cinc quadrats al llarg de l'altre (60/12 = 5).

El MCD de dos nombres a i b pot ser definit com el producte dels factors primers compartits pels dos nombres.[7] Per exemple, com que 462 es pot descompondre en factors com 2 × 3 × 7 × 11 i 1071 es pot descompondre com 3 × 3 × 7 × 17, el màxim comú divisor de 462 i 1071 és igual a 21 = 3 × 7, el producte dels seus factors primers compartits. Si dos nombres no tenen cap factor primer en comú, el seu màxim comú divisor és 1, llavors són coprimers. Un avantatge clau de l'algorisme d'Euclides és que pot trobar el MCD eficaçment sense haver de calcular els factors primers.[8][9] la factorització d'enters grans es creu que és un problema tan difícil que s'hi basen molts sistemes de criptografia moderns.[10]

Una definició més subtil del MCD és útil en matemàtiques avançades, especialment en teoria d'anells.[11] El màxim comú divisor g de dos nombres a i b és també el seu múltiple enter més petit, és a dir, el nombre més petit de la forma ua + vb on u i v són enters (cal tenir en compte que un sempre és negatiu i l'altre positiu). Se segueix que el conjunt de tots els múltiples enters de a i b (tots els nombres ua + vb ) és el mateix com el conjunt de tots els múltiples enters de g (mg, on m és un enter). En llenguatge matemàtic modern, l'ideal format per a i b és un ideal principal generat per g. L'equivalència d'aquesta definició de MCD amb les altres definicions es descriu més avall.

El MCD de tres o més nombres és igual al producte dels factors primers comuns a tots els nombres,[12] que es pot calcular prenent el MCD de cada parella de nombres.[13] Per exemple

MCD(abc) = MCD(a, MCD(bc)) = MCD(MCD(ab), c) = MCD(MCD(ac), b).

Per tant, l'algorisme d'Euclides, que calcula el MCD de dos enters, és suficient per calcular el MCD d'una quantitat arbitrària d'enters.

Inducció, recursivitat i descens infinit[modifica | modifica el codi]

Tres mètodes matemàtics relacionats s'utilitzen en els arguments següents: inducció, recursivitat i descent infinit. La inducció[14] sovint es fa servir per demostrar un teorema per a tots els nombres naturals n.[15] Aquest enfocament comença demostrant que, si el teorema es compleix per n, també es compleix per n + 1. Per això, si el teorema es compleix per a un cas (típicament n = 1), es compleix per a tots els casos més alts (n = 2, 3, etc.). Una recurrència[16] és una equació que relaciona nombres que formen una sèrie a1, a2, a3, etc.[17] El terme nèssim de la sèrie, an, sovint s'expressa en funció de termes anteriors de la sèrie, com an −1. Per exemple, els nombres de Fibonacci es defineixen recursivament; cada terme és la suma dels dos termes anteriors: Fn = Fn −1 + Fn −2. Unes quantes equacions associades amb l'algorisme euclidià són recursives. Finalment, en el descens infinit,[18] una solució donada en nombres naturals és utilitzada per construir una solució amb nombres naturals més petits.[19] Tanmateix, les solucions no es poden encongir indefinidament, ja que només hi ha un nombre finit de nombres naturals més petits que qualsevol nombre natural. Per això, la solució original era impossible, o la construcció de solucions més petites ha d'acabar. L'últim argument s'utilitza per demostrar que l'algorisme euclidià per a nombres naturals ha d'acabar en un nombre finit de passos.[20]

Descripció[modifica | modifica el codi]

Procediment[modifica | modifica el codi]

L'algorisme d'Euclides és iteratiu, això vol dir que la resposta es troba seguint una sèrie de passos repetitius; el resultat de cada pas es fa servir com a dada per al pròxim pas.[21] Sia k un enter que compta els passos de l'algorisme, començant amb zero. Així, el pas inicial es correspon a k = 0, el pròxim pas es correspon a k = 1, etcètera.

Cada pas comença amb dos residus no negatius r k −1 i r k −2. Com que l'algorisme assegura que els residus disminueixen constantment a tots els passos r k −1 és menor que el seu predecessor r k −2. L'objectiu del k èssim pas és trobar un quocient q k i un residu r k tals que satisfan l'equació

rk−2 = qk rk−1 + rk

on rk < rk −1. En altres paraules, múltiples del nombre més petit rk −1 són restats del nombre el més gran rk −2 fins que la resta sigui més petita que el rk −1.

Al pas inicial ( k = 0), els residus r−2 i r−1 són iguals a a i b, els nombres per als quals es busca el MCD. Al següent pas ( k = 1), els residus són iguals a b i el residu r 0 del pas inicial, etcètera. Així, l'algorisme es pot escriure com a seqüència d'equacions

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

Si a és més petit que b, el primer pas de l'algorisme intercanvia els nombres. Per exemple, si a < b, el quocient inicial q0 és igual a zero, i el residu r0 és a. Així rk és més petit que el seu predecessor rk −1 per a tot k ≥ 0.

Ja que els residus disminueixen amb tots els passos però mai no poden ser negatius, al final un residu rN ha de ser igual a zero, en aquest punt s'atura l'algorisme.[20] L'últim residu diferent de zero rN −1 és el màxim comú divisor de a i b. El nombre N no pot ser infinit perquè hi ha només un nombre finit d'enters no negatius entre el residu inicial r0 i zero.

Demostració de validesa[modifica | modifica el codi]

La validesa de l'algorisme d'Euclides es pot demostrar per un argument de dos passos.[21] Al primer pas, es demostra que l'últim residu diferent de zero rN −1 és un divisor dels dos a i b. Com que és divisor comú, ha de ser menor o igual que el màxim comú divisor g. Al segon pas, es demostra que qualsevol divisor comú de a i b, incloent-hi g, ha de dividir rN −1; per això g ha de ser menor que o igual a rN −1. Aquestes dues conclusions són incoherents llevat que rN −1 = g.

Per demostrar que rN −1 divideix els dos a i b (el primer pas), rN −1 divideix el seu predecessor r N −2

rN−2 = qN rN−1

com que el residu final rN és zero. r N −1 també divideix el seu pròxim predecessor r N −3

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

perquè divideix els dos termes del costat dret de l'equació. Iterant el mateix argument rN −1 divideix tots els residus anteriors, incloent-hi a i b. Cap dels residus anteriors rN −2, rN −3, etc. divideix a i b, ja que donen un residu diferent de zero. Com que rN −1 és un divisor comú de a i b, rN −1g.

Al segon pas, qualsevol nombre natural c que divideix tant a com b (en altres paraules, qualsevol comú divisor de a i b) divideix els residus rk . Per definició a i b es poden escriure com múltiples de c : a = mc i b = nc, on m i n són nombres naturals. Per això c divideix el residu inicial r0, des de r0 = aq 0b = mcq0nc = (mq0n)c. Un argument anàleg demostra que c també divideix els subsegüents residus r1, r2, etc. Per això, el màxim comú divisor g ha de dividir rN −1, el que implica que grN −1. Com que la primera part de l'argument mostrava l'invers (rN−1g), resulta que g = rN −1. Així g és el màxim comú divisor de tots els parells de la successió:.[22][23]

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

Exemple[modifica | modifica el codi]

Animació on rajoles quadrades progressivament més petites s'afegeixen per cobrir completament un rectangle.
Animació de l'algorisme. El rectangle verd inicial té dimensions a = 1071 i b = 462. S'afegeixen rajoles quadrades de 462×462 fins que romangui un rectangle de 462×147 verd. Aquest s'enrajola amb rajoles quadrades de 147×147 fins que romangui un rectangle de 21×147. Aquest tercer rectangle s'enrajola amb rajoles quadrades de 21×21, no queda cap residu. Així, 21 és el màxim comú divisor de 1071 i 462.

Per a il·lustrar-ho, l'algorisme d'Euclides es pot fer servir per trobar el màxim comú divisor de a = 1071 i b = 462. Per començar, es resten de 1071 múltiples de 462 fins que el residu sigui menor de 462. Se'n poden restar dos (q0 = 2), deixant un residu de 147

1071 = 2 × 462 + 147.

Llavors es resten de 462 múltiples de 147 fins que la resta sigui menor de 147. Se'n poden restar tres (q1 = 3), deixant un residu de 21

462 = 3 × 147 + 21.

Llavors es resten de 147 múltiples de 21 fins que la resta sigui menor de 21. Se'n poden restar set (q2 = 7), no deixa cap residu

147 = 7 × 21 + 0.

Com que l'últim residu és zero, l'algorisme acaba amb 21 com el màxim comú divisor de 1071 i 462. Això està d'acord amb el MCD(1071, 462) trobat per factorització més amunt. En forma tabular, els passos són

Pas k Equació Quocient i residu
0 1071 = q0 462 + r0 q0 = 2 i r0 = 147
1 462 = q1 147 + r1 q1 = 3 i r1 = 21
2 147 = q2 21 + r2 q2 = 7 i r2 = 0; l'algorisme s'acaba

Visualització[modifica | modifica el codi]

L'algorisme d'Euclides es pot visualitzar en termes de l'analogia d'enrajolar donada abans per al màxim comú divisor.[24] Suposant que es vol cobrir completament un rectangle de a-per-b amb rajoles quadrades, on a és el més gran dels dos nombres. Primer s'intenta enrajolar el rectangle fent servir rajoles quadrades de b-per-b; tanmateix, això deixa un rectangle residual r0-per-b sense nenrajolar, on r0<b. Llavors s'intenta enrajolar el rectangle residual amb rajoles quadrades de r0-per-r0. Això deixa un segon rectangle residual r1-per-r0, que s'intenta enrajolar emprant rajoles quadrades de r1-per-r1, etcètera. La seqüència acaba quan no hi ha cap rectangle residual, és a dir, quan les rajoles quadrades cobreixen el rectangle residual previ exactament. La llargada dels costats de la rajola quadrada més petita és el MCD de les dimensions del rectangle original. Per exemple, la rajola quadrada més petita en la figura adjacent és 21-per-21 (es mostra en vermell), i 21 és el MCD de 1071 i 462, les dimensions del rectangle original (que es mostra en verd).

Càlcul dels quocients i els residus[modifica | modifica el codi]

Vegeu també: Operació Mòdul i Divisió euclidiana

A tots els passos k, l'algorisme d'Euclides calcula un quocient qk i un residu rk de dos nombres rk −1 i rk −2

rk−2 = qk rk−1 + rk

on la magnitud de rk és estrictament menor que la de rk −1. L'algorisme de divisió assegura que sempre existeixen el quocient i el residu. L'algorisme de divisió per a nombres naturals també estableix que qk i rk són únics, però això no cal per a l'algorisme d'Euclides.[25]

En la versió original de l'algorisme d'Euclides, el quocient i el residu es troben per sostracció repetida; és a dir rk −1 es resta de rk −2 repetidament fins que la resta rk és més petita que rk −1. Un enfocament més eficient fa servir la divisió d'enters i l'operació mòdul per calcular el quocient i el residu, respectivament. L'operació mòdul dóna el residu de dos nombres després de dividir-los; així

r k r k −2 mod r k −1

El residu és equivalent a la classe de congruència en aritmètica modular.

Implementacions[modifica | modifica el codi]

Les aplicacions de l'algorisme es poden expressar en el pseudocodi. Per exemple, la versió basada en la divisió es pot programar com.[26]

funció mcd(a, b)
mentre b ≠ 0
t := b
b := a mod b
a := t
retorna a

Al començament de la iteració k èssima, la variable b conté l'últim residu rk−1, mentre que la variable a conté el seu predecessor, rk−2. El pas b := a mod b és equivalent a la fórmula de recurrència citada rkrk −2 mod rk −1. La variable auxiliar t conté el valor de rk−1 mentre el proper residu rk està sent calculat. Al final de la iteració del bucle, la variable b conté el residu rk, mentre que la variable a conté el seu predecessor, rk −1.

En la versió basada en la sostracció definida per Euclides, el càlcul del residu (b = a mod b) és reemplaçat per una sostracció repetida.[27]

funció mcd(a, b)
si a = 0
retorna b
mentre b ≠ 0
si a > b
a := a − b
altrament
b := b − a
retorna a

Les variables a i b contenen alternativament els residus previs rk −1 i rk −2. Suposant que a és més gran que b al començament d'una iteració; llavors a és igual a rk −2, com que rk −2 > rk −1. Durant la iteració del bucle a es redueix per múltiples restes de b fins que a és més petit que b. Llavors a és el pròxim residu rk. Llavors b es redueix per múltiples restes de a fins que sigui una altra vegada més petit que a, donant el pròxim residu rk +1, etcètera.

La versió recursiva[28] es basa en la igualtat de MCDs dels successius residus i la condició d'aturada MCD( rN −1, 0) = rN −1.

funció mcd(a, b)
si b = 0
retorna a
altrament
retorna mcd(b, a mod b)

Per il·lustrar-ho, el MCD(1071, 462) es calcula a partir de l'equivalent MCD(462, 1071 mod 462) = MCD(462, 147). Aquest últim MCD es calcula a partir del MCD(147, 462 mod 147) = MCD(147, 21), que al seu torn es calcula a partir de MCD(21, 147 mod 21) = MCD(21, 0) = 21.

Mètode dels residus mínims absoluts[modifica | modifica el codi]

En una altra versió de l'algorisme d'Euclides, el quocient a cada pas s'augmenta en una unitat si el residu negatiu que resulta és més petit en magnitud que el residu positiu típic.[29][30] Prèviament, l'equació

rk−2 = qk rk−1 + rk

suposa que r k −1 > r k > 0. Tanmateix, es pot calcular un residu negatiu alternatiu ek

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

on rk −1 se suposa que és positiu. Si|ek| < |rk|, llavors rk és reemplaçat per ek. Com va demostrar Leopold Kronecker, aquesta versió és la que exigeix el mínim nombre de passos de totes les versions de l'algorisme d'Euclides.[29][30]

Desenvolupament històric[modifica | modifica el codi]

"Quadre que representa Euclides com un home barbut que aguanta un parell de compassos de puntes sobre una tauleta."
L'algorisme d'Euclides es va inventar probablement segles abans d'Euclides, que es mostra aquí amb un parell de compassos de puntes a la mà.

L'algorisme d'Euclides és un dels algorismes més antics que encara es fa servir habitualment.[31] Apareix als elements d'Euclides (circa. 300 aC), específicament al Llibre 7 (Proposicions 1-2) i al Llibre 10 (Proposicions 2-3). En el Llibre 7, l'algorisme es formula per a enters, mentre que al Llibre 10, es formula per a llargades de segments de recta. (En l'ús modern, es diria que aquí es formulava per a nombres reals. Però les llargades, àrees, i volums, representats com nombres reals en l'ús modern, no es mesuren en les mateixes unitats i no hi ha cap unitat natural de llargada, àrea, o volum, i el concepte de nombres reals era desconegut en aquella època.) L'últim algorisme és geomètric. El MCD de dues llargades a i b correspon a la llargada més gran g que mesura a i b uniformement; en altres paraules, les llargades a i b són les dues múltiples enteres de la llargada g.

Probablement l'algorisme no el va descobrir Euclides, qui va compilar els resultats de matemàtics anteriors en el seu llibre Elements.[32][33] El matemàtic i l'historiador B. L. Van Der Waerden suggereix que el Llibre VII deriva d'un llibre de text sobre teoria de nombres escrit per matemàtics de l'escola de Pitàgores.[34] L'algorisme probablement era conegut per Èudox de Cnidos (sobre el 375 AC.).[31][35] L'algorisme pot fins i tot predatar Èudox,[36][37] sobre la base de l'ús del terme tècnic νθυφαίρεσις (anthyphairesis, sostracció recíproca) en treballs d'Euclides i Aristotil.[38]

Segles més tard, l'algorisme d'Euclides es descobria independentment tant a l'Índia com a la Xina,[39] principalment per resoldre equacions diofàntiques que sorgeixen en astronomia i per fer calendaris acurats. A finals del segle V, el matemàtic i l'astrònom indi Aryabhata descriu l'algorisme com el "polvoritzador",[40] potser a causa de la seva eficàcia en la solució d'equacions diofàntiques.[41] Encara que un cas especial del teorema xinès del residu ja havia estat descrit pel matemàtic i astrònom xinès Sun Tzu,[42] la solució general era publicada per Qin Jiushao al seu llibre de 1247 Shushu Jiuzhang (數書九章 Tractat Matemàtic en Nou Seccions).[43] L'algorisme euclidià es descrivia per primera vegada a Europa a la segona edició del llibre de Bachet délectables de et de plaisants Problèmes (problemes agradables i divertits, 1624).[40] A Europa, s'utilitzava igualment per resoldre equacions diofàntiques i per obtenir desenvolupaments de fraccions contínues. L'algorisme d'Euclides ampliat era publicat pel matemàtic anglès Nicholas Saunderson, que l'atribuïa a Roger Cotes com a mètode de càlcul eficient de fraccions contínues.[44]

Al segle XIX, l'algorisme euclidià portava al desenvolupament de nous sistemes de nombres, com els Enters gaussians i els enters d'Eisenstein. El 1815, Carl Gauss utilitzava l'algorisme euclidià per demostrar la factorització única dels Enters gaussians, encara que el seu treball es publicava per primera vegada el 1832.[45] Gauss esmenta l'algorisme en el seu Disquisitiones Arithmeticae (publicat el 1801), però només com a mètode per fraccions contínues.[39] Peter Dirichlet sembla haver estat el primer a descriure l'algorisme euclidià com la base de gran part de la teoria de nombres.[46] Dirichlet va observar que molts resultats de la teoria de nombres, com la factorització única, valdrien per a qualsevol altre sistema de nombres al què es pogués aplicar l'algorisme euclidià.[47] les conferències de Dirichlet sobre teoria de nombres eren editades i difoses per Richard Dedekind, que utilitzava l'algorisme d'Euclides per estudiar enters algebraics, un tipus general nou de nombres. Per exemple, Dedekind era el primer a demostrar el Teorema de la suma de dos quadrats de Fermat que utilitza la factorització única d'enters gaussians.[48] Dedekind també definia el concepte d'un domini euclidià, un sistema de nombres en el qual es pot definir una versió generalitzada de l'algorisme euclidià (com es descriu més aball). En les dècades finals del segle XIX, tanmateix, l'algorisme euclidià gradualment es veia eclipsat per la teoria més general de Dedekind d'ideals.[49]

"[L'algorisme d'Euclides] és el iaio de tots els algorismes, perquè és l'algorisme no trivial més vell que ha sobreviscut fins al dia d'avui."

Donald Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2a edició (1981), pàg. 318.

Altres aplicacions de l'algorisme d'Euclides es desenvolupaven al segle XIX. El 1829 Charles Sturm mostrava que l'algorisme era útil en el mètode la cadena de Sturm per comptar les arrels reals de polinomis en qualsevol interval donat.[50]

L'algorisme euclidià va ser el primer algorisme de relació entera, que és un mètode per trobar relacions enteres entre nombres reals proporcionals. En els darrers anys s'han desenvolupat uns quants algorismes de relació entera nous, com l'algorisme de ferguson-forcade (1979) el de Helaman Ferguson i R.W. Forcade,[51] i els seus parents, l'algorisme LLL, l'algorisme HJLS, i l'algorisme PSLQ.[52][53]

El 1969, Cole i Davie desenvolupaven un joc de dos jugadors basat en l'algorisme euclidià, anomenat El Joc d'Euclides,[54] que té una estratègia òptima.[55] Els jugadors comencen amb dues piles de a i b pedres. Els jugadors, per torns, treuen m múltiples de la pila més petita de la més gran. Així, si les dues piles consisteixen de x i y pedres, on x és més gran que y, el pròxim jugador pot reduir la pila més gran de x pedres a xmy pedres, mentre quedi un enter no negatiu. El guanyador és el primer jugador que redueixi una pila a zero pedres.[56][57]

Aplicacions matemàtiques[modifica | modifica el codi]

La identitat de Bézout[modifica | modifica el codi]

La identitat de Bézout estableix que el màxim comú divisor g de dos enters a i b es pot representar com una suma lineal dels dos nombres a i b.[58] En altres paraules, sempre és possible trobar enters s i t tals que g = sa + tb .[59][60]

Els enters s i t es poden calcular a partir dels quocients q0, q1, etc. tirant enrere l'ordre de les equacions en l'algorisme d'Euclides.[61] Començant amb l'equació més propera al final, g es pot expressar en termes del quocient qN −1 i els dos residus precedents, rN −2 i r N−3.

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

De la mateixa manera Aquests dos residus es poden expressar en termes dels seus quocients i dels residus anteriors,

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

Substituint aquestes fórmules per rN−2 i rN−3 a la primera equació dóna g com a suma lineal dels residus r N−4 i rN−5. El procés de substituir residus per fórmules que impliquen els seus predecessors es pot continuar fins que s'arriba als nombres originals a i b

r2 = r0q2 r1
r1 = bq1 r0
r0 = aq0 b

Després que tots els residus r0, r1, etc. han estat substituïts, l'equació final expressa g com a suma lineal de a i b: g = sa + tb. La identitat de Bézout, i per tant l'algorisme previ, es poden generalitzar al context de dominis euclidians.

Ideals principals i problemes relacionats[modifica | modifica el codi]

La identitat de Bézout proporciona encara una altra definició del màxim comú divisor g de dos nombres a i b .[11] Considerant el conjunt de tots els nombres ua + vb, on u i v són dos enters qualssevol. Com que a i b són els dos divisibles entre g, tots els nombres en el conjunt són divisibles entre g. En altres paraules, tots els nombres del conjunt són múltiples enters de g. Això és veritable per a tots els divisors comuns de a i b. Tanmateix, a diferència dels altres comuns divisors, el màxim comú divisor és un membre del conjunt; per la identitat de Bézout, triant u = s i v = t dóna g. Un comú divisor més petit no pot ser un membre del conjunt, ja que tots els membres del conjunt han de ser divisibles entre g. Al contrari, qualsevol múltiple m de g pot ser obtingut triant u = ms i v = mt, on s i t són els enters de la identitat de Bézout. Això es pot veure multiplicant la identitat de Bézout per m

mg = msa + mtb

Per això, el conjunt de tots els nombres ua + vb és equivalent al conjunt de múltiples m de g. En altres paraules, el conjunt de totes les sumes possibles de múltiples enters de dos nombres (a i b) és equivalent al conjunt de múltiples de MCD(a,b). El MCD es diu que és el generador de l'ideal de a i b. Aquesta definició de MCD condueix als conceptes algebraics abstractes moderns d'un ideal principal (un ideal generat per un únic element) i un domini d'ideals principals (un domini en el qual tots els ideals són principals).

Certs problemes es poden resoldre utilitzant aquest resultat.[62] Per exemple, considerant dues copes de volum a i b. Sumant/restant u múltiples de la primera copa i v múltiples de la segona copa, es pot mesurar qualsevol volum ua + vb. Aquests volums són tots els múltiples de g = MCD(a, b).

Algorisme d'Euclides ampliat[modifica | modifica el codi]

Article principal: Algorisme d'Euclides ampliat

Els enters s i t de la identitat de Bézout es posen calcular eficaçment emprant l'algorisme d'Euclides ampliat. Aquesta ampliació afegeix dues equacions recursives a l'algorisme d'Euclides.[63]

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

amb els valors d'engegada

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

Emprant aquesta recurrència, els enters de Bézout s i t vénen donats per s = sN i t = tN, on N és el pas en el qual acaba l'algorisme amb rN = 0.

La validesa d'aquesta aproximació es pot demostrar per inducció. Suposant que la fórmula de recurrència és correcta fins al pas k −1 de l'algorisme; en altres paraules, suposant que

rj = sj a + tj b

per a tot j menor que k. El pas k èssim de l'algorisme dóna l'equació

rk = rk−2qk−1rk−1

Com que la fórmula de recurrència s'ha suposat que és correcte per rk−2 i rk−1, es poden expressar en termes dels corresponents s i t variables

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

Redistribuint aquesta equació produeix la fórmula de recurrència pel pas k, com calia

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

Mètode matricial[modifica | modifica el codi]

Els enters s i t també es poden trobar emprant un mètode matricial equivalent.[64] La seqüència d'equacions de l'algorisme d'Euclides

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

es pot escriure com a producte de matrius quocient 2-per-2 que multipliquen un vector residu bidimensional


\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_{0} \end{pmatrix} =
\begin{pmatrix} q_{0} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_{1} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{0} \\ r_{1} \end{pmatrix} =
\cdots =
\prod_{i=0}^{N} \begin{pmatrix} q_{i} & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix}

Si M representa el producte de totes les matrius quocient

La matriu 2-per-2 M té quatre components, m sub 1 1, m sub 1 2, m sub 2 1, i m sub 2 2. Es defineix com el producte de totes les matrius 2-per-2 de la forma q sub i 1 1 0, on l'índex i varia de 0 a N.

Això simplifica l'algorisme euclidià a la forma

El vector bidimensional de a b és igual a la matriu M multiplicada pel vector final, r sub N menys un zero. El residu diferent de zero final és el màxim comú divisor g. Per això, el vector a b és igal a la matriu M pel vector g zero.

Per expressar g com a suma lineal de a i b, els dos costats d'aquesta equació es poden multiplicar per l'invers de la matriu M.[64][65] El determinant de M és igual a (−1)N+1, ja que és igual al producte dels determinants de les matrius quocient, cada un dels quals és menys u. Com que el determinant de M no és mai zero, el vector dels residus finals es pot resoldre fent servir l'invers de M

El vector bidimensional g 0 és igual a l'invers de la matriu M pel vector a b. Això és igual a menys u elevat a la potència Nèssima més u, per la matriu amb components m sub 2 2, menys m sub 1 2, menys m sub 2 1, i m sub 1 1, pel vector a b.

Com que la primera equació dóna

g = (−1)N+1 ( m22 am12 b)

els dos enters de la identitat de Bézout són s = (−1)N+1m22 i t = (−1)Nm12. El mètode matricial és tan eficient com la recurrència equivalent, amb dues multiplicacions i dues addicions per pas de l'algorisme euclidià.

El lema d'Euclides i la factorització única[modifica | modifica el codi]

La identitat de Bézout és essencial per moltes aplicacions de l'algorisme d'Euclides, com per exemple per demostrar la factorització única de nombres en factors primers.[66] Per il·lustrar això, suposant que un nombre L es pot escriure com a producte de dos factors u i v, és a dir L = uv. Si un altre nombre w també divideix L però és coprimer amb u, llavors w ha de dividir v, per l'argument següent: Si el màxim comú divisor de u i w és 1, llavors es poden trobar enters s i t tals que

1 = su + tw

per la identitat de Bézout. Multiplicant els dos costats per v dóna la relació

v = suv + twv = sL + twv

COm que w divideix els dos termes del costat dret, també ha de dividir el costat esquerre, v. Aquest resultat es coneix com el lema d'Euclides.[67] Específicament, si un nombre primer divideix L, llavors ha de dividir com a mínim un factor de L. Recíprocament, si un nombre w és coprimer amb cada un d'una sèrie de nombres a1, a2, …, an, llavors w és també coprimer amb el seu producte, a1 × a2 × … × an.[67]

El lema d'Euclides és suficient per demostrar que tots els nombres tenen una factorització única en nombres primers.[68] Per veure això, suposant el contrari, que hi ha dues factorizations independents de L en m i n factors primers, respectivament

L = p1p2pm = q1q2qn

Com que cada primer p divideix L per hipòtesi, també ha de dividir un dels q factors; com que cada q també és primer, ha de ser p = q. Iterativament dividint entre p factors es demostra que cada p té una contrapartida igual q; les dues factorizations en nombres primers són idèntiques amb l'excepció del seu ordre. La factorització única de nombres primers té moltes aplicacions en demostracions matemàtiques, com es mostra més avall.

Equacions diofàntiques lineals[modifica | modifica el codi]

"línia diagonal de la cantonada de dalt a l'esquerra a la de baix a la dreta. Quinze circumferències s'espaien a intervals regulars al llarg de la línia. Els eixos de coordenades x-y perpendiculars tenen el seu origen a la cantonada d'abaix a l'esquerra; la línia creua l'eix d'ordenades a dalt a l'esquerra i l'eix d'abcisses a baix a la dreta."
Gràfic d'una Equació diofàntica lineal, 9 x + 12y = 483. Les solucions es mostren com circumferències blaves.

Les equacions diofàntiques són equacions en les quals les solucions es restringeixen a enters; se'ls posa el nom del matemàtic alexandrí de segle III Diofant.[69] Una eauació diofàntica lineal típica busca enters x i y tals que.[70]

ax + by = c

on a, b i c són enters donats. Això es pot escriure com equació de x en aritmètica modular

axc mod b.

Sia g el màxim comú divisor de a i b. Els dos termes en ax + by són divisible per g; per això c també ha de ser divisible entre g, o l'equació no té solucions. Dividint els dos costats per c/g, l'equació es pot reduir a la identitat de Bezout

sa + tb = g

on s i t es poden trobar amb l'algorisme euclidià estès.[71] Això proporciona una solució a l'equació diofàntica, x1 = s (c/g) i y1 = t(c/g).

En general, una equació diofàntica lineal no té solucions, o en té un nombre infinit.[72] Per trobar-les en últim cas, considerant dues solucions, (x1, y1) i (x2, y2)

ax1 + by1 = c = ax2 + by2

o equivalentment

a(x1x2) = b(y2y1).

Per això, la diferència més petita entre dos solucions x és b/g, mentre que la diferència més petita entre dos y solucions és a/g. Així, les solucions es poden expressar com

x = x1bt/g
y = y1 + at/g.

Permetent que t variï sobre tots els enters possibles, es pot generar una família infinita de solucions a partir d'una solució única (x1, y1). Si s'exigeixen que les solucions siguin enters positiux (x > 0, y > 0), només hi ha un nombre finit de solucions possibles. Aquesta restricció de les solucions acceptables permet que sistemes d'equacions diofàntiques siguin resoltes amb més desconegudes que equacions;[73] això és impossible per a un sistema d'equacions lineals quan les solucions poden ser qualsevol nombres reals.

Inversa multiplicativa i l'algorisme RSA[modifica | modifica el codi]

Un cos finit és un conjunt de nombres amb quatre operacions generalitzades. Les operacions s'anomenen addició, sostracció, multiplicació i divisió i tenen les seves propietats habituals, com la propietat commutativa, la propietat associativa i la propietat distributiva. Un exemple d'un cos finit és el conjunt de 13 nombres {0, 1, 2, …, 12} emprant aritmètica modular. En aquest cos, els resultats de qualsevol operació matemàtica (addició/sostracció/multiplicació/divisió) es redueix mòdul 13; és a dir, s'afegeixen múltiples de 13 o es resten fins que el resultat es porti dins de la gamma 0-12. Per exemple, el resultat de 5 × 7 = 35 mod 13 = 9. Tals cossos finits es poden definir per a qualsevol primer p; fent servir definicions més sofisticades, també es poden definir per a qualsevol potència m d'un nombre primer pm. Els cossos finits s'anomenen sovint cossos de Galois, i s'abreugen com GF(p) o GF(pm).

En un cos amb m nombres, tot element diferent de zero a té un invers multiplicatiu modular únic, a−1 tal que aa−1 = a−1a ≡ 1 mod m. Aquest invers es pot trobar resolent l'equació de congruència ax ≡ 1 mod m,[74] o l'equació diofàntica lineal equivalent.[75]

ax + my = 1

Aquesta equació pot ser resolta per l'algorisme euclidià, com s'ha descrit més amunt. Trobar inversos multiplicatius és un pas essencial en l'algorisme de RSA, que s'utilitza àmpliament en comerç electrònic; específicament, l'equació determina l'enter utilitzat per desxifrar el missatge.[76] Fixar-se que encara que l'algorisme RSA fa servir anells més que els cossos, l'algorisme euclidià encara es pot fer servir per trobar un invers multiplicatiu on existeix. L'algorisme euclidià també té altres aplicacions a codis correctors; per exemple, es pot utilitzar com a alternativa a l'algorisme de Berlekamp-Massey per desxifrar els codis BCHh i Reed-Solomon, es quals es basen en cossos de Galois.[77]

Teorema xinès del residu[modifica | modifica el codi]

L'algorisme d'Euclides també es pot fer servir per resoldre equacions diofàntiques lineals múltiples.[78] Tals equacions sorgeixen en el teorema xinès del residu, que descriu un mètode nou per representar un enter x. En comptes de representar un enter pels seus dígits, pot ser representat pels seus residus xi mòdul un conjunt de N nombres coprimers mi.[79]

x1x mod m1
x2x mod m2
xNx mod mN

L'objectiu és determinar x a partir dels seus N residus xi. La solució és combinar les equacions múltiples en una única equació diofàntica lineal amb un mòdul molt més gran M que és el producte de tots els mòduls individuals mi /sub>, i definir el Mi

Mi = M / mi

Així, cada Mi és el producte de tots els mòduls excepte mi. La solució depèn de trobar N nombres nous hi tals que

Mihi ≡ 1 mod mi

Amb aquests nombres hi, qualsevol enter x pot ser reconstruït a partir dels seus residus xi per l'equació

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

Com que aquests nombres hi són els inversos multiplicatius de Mi, es poden trobar emprant l'algorisme d'Euclides com s'ha descrit en la subsecció prèvia.

Fraccions Contínues[modifica | modifica el codi]

L'algorisme euclidià està íntimament relacionat amb les fraccions contínues.[80] La successió d'equacions es pot escriure de la forma


\begin{align}
\frac{a}{b} &= q_0 + \frac{r_0}{b} \\
\frac{b}{r_0} &= q_1 + \frac{r_1}{r_0} \\
\frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\
& {}\ \vdots \\
\frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\
& {}\ \vdots \\
\frac{r_{N-2}}{r_{N-1}} &= q_N
\end{align}

El darrer terme del costat dret és sempre igual a l'invers del costat esquerre de la pròxima equació. Així, les primeres dues equacions es poden combinar per formar

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}}

La tercera equació es pot utilitzar per substituir el terme del denominador r1/r0, donant

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}}

La proporció final de residus r k/rk−1 sempre es pot reemplaçar utilitzant la pròxima equació en la sèrie, fins a l'equació final. El resultat és una fracció contínua

\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \ldots, q_N ]

En l'exemple de més amunt, es calculava el MCD(1071, 462), i els quocients qk eren 2, 3 i 7, respectivament. Per això, la fracció 1071/462 es pot escriure

\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3, 7]

com es pot confirmar per càlcul.

Algorismes de factorització[modifica | modifica el codi]

Calcular un màxim comú divisor és un pas essencial en diversos algorismes de factorització dels enters,[81] com l'algorisme rho de Pollard,[82] l'algorisme de Shor,[83] el mètode de factorització de Dixon[84] i la Factorització per corba el·líptica de Lenstra.[85] L'algorisme euclidià es pot utilitzar per trobar aquest MCD eficientment. La factorització de fracció contínua fa servir fraccions contínues, que es determinen emprant l'algorisme d'Euclides.[86]

Eficiència algorísmica[modifica | modifica el codi]

"Un conjunt de línies pintades de colors que radien cap enfora de l'origen d'un sistema de coordenades de x-y. Cada línia correspon a un conjunt de parells de nombres que exigeixen el mateix nombre de passos en l'algorisme euclidià."
Nombre de passos en l'algorisme euclidià per trobar el MCD(x,y). Els punts vermells indiquen relativament pocs passos (més ràpid), mentre que els punts grocs, verds i blaus indiquen successivament més passos (més lent).

L'eficiència computacional de l'algorisme d'Euclides s'ha estudiat minuciosament.[87] Aquesta eficiència es pot descriure pel nombre de passos que l'algorisme requereix, multiplicat per la despesa computacional de cada pas. Com va demostrar per primera vegada Gabriel Lamé el 1844,[88] el nombre de passos requerits per a l'acabament no és mai més gran que cinc vegades el nombre h de dígits (base 10) del nombre b (el més petit).[89][90] Ja que la despesa computacional de cada pas és també típicament d'ordre h, la despesa global creix com h 2.

Nombre de passos[modifica | modifica el codi]

El nombre de passos per calcular el MCD de dos nombres naturals a i b, es pot denotar per T(a, b).[91] Si g és el MCD de a i b, llavors a = mg i b = ng per a dos nombres coprimers m i n. Llavors

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

com es pot veure dividint tots els passos de l'algorisme euclidià per g.[92] Pel mateix argument, el nombre de passos roman el mateix si a i b es multipliquen per un factor comú w: T(a, b) = T(wa, wb). Per això, el nombre de passos T pot variar dramàticament entre parells veïns de nombres, com T(a, b) i T(a, b + 1), depenent de la mida del dos MCD.

La natura recursiva de l'algorisme euclidià dóna una altra equació

T(a, b) = 1 + T(b, r0) = 2 + T(r0, r1) = … = N + T(rN−2, rN−1) = N + 1

on T(x, 0) = 0 per hipòtesi.[91]

Nombre de passos en el cas pitjor[modifica | modifica el codi]

Si l'algorisme euclidià exigeix N passos per a un parell de nombres naturals a > b > 0, els valors més petits de a i b per als quals això és cert són els nombres de Fibonacci FN+2 i FN+1, respectivament.[93] Això es pot demostrar per inducció.[94] Si N = 1, b divideix a sense residu; els nombres naturals més petits per als quals això es compleix són b = 1 i a = 2, que és F2 i F3, respectivament. Ara suposant que el resultat es compleix per a tots els valors de N fins a M − 1. El primer pas del algorisme de M -l' passos és a = q0b + r0, i el segon pas és b = q1r0 + r1. Com que l'algorisme és recursiu, exigirà M − 1 passos per trobar el MCD(b, r0) i els seus valors més petits són FM+1 i FM. El valor més petit de a és per tant quan q0 = 1, que dóna a = b + r0 = FM +1 + FM = FM +2. Aquesta demostració, publicada per Gabriel Lamé el 1844, representa el començament de la teoria de complexitat computacional,[95] i també la primera aplicació pràctica dels nombres de Fibonacci.[93]

Aquest resultat és suficient per mostrar que el nombre de passos en l'algorisme d'Euclides mai no pot ser més que cinc vegades el nombre dels seus dígits (base 10).[96] Per si l'algorisme exigeix N passos, llavors b és més gran que o igual a FN +1 que a canvi és més gran que o igual a φN −1, on φ és la proporció àuria. Com que bφN −1, llavors N − 1 ≤ logφb. Com que log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b. Així N ≤ 5 log10 b. Per tant, l'algorisme euclidià sempre necessita menys que O(H) divisions, on h és el nombre de dígits del nombre més petit b.

Nombre mitjà de passos[modifica | modifica el codi]

El nombre mitjà de passos emprats per l'algorisme euclidià s'ha definit de tres maneres diferents. La primera definició és el temps mitjà T(a) exigit per calcular el MCD d'un nombre donat a i un nombre natural més petit b escollit amb probabilitat igual dels enters 0 a a − 1.[91]

La funció T de a és igual a un sobre a multiplicat pel sumatori de la funció T de a coma b sobre tots els valors no negatius de b més petits que a.

Tanmateix, com que T(a, b) fluctua dramàticament amb el MCD dels dos nombres, la funció mitjana T(a) és de la mateixa manera "sorollosa".[97]

Per reduir aquest soroll, una segona mitjana τ(a) es pren sobre tots els nombres coprimers amb a

La funció tau és igual a un sobre la funció phi de a multiplicada pel sumatori de la funció T da a coma b sobre tots els valors no negatius de b menors que A, on b és coprimer amb a.

Hi ha φ (a) enters coprimers menors que a, on φ és la Funció Fi d'Euler. Aquesta mitjana de tau augmenta suaument amb a.[98][99]

τ(a) = (12/π2) ln 2 ln a + C + O(a−(1/6) + ε)

amb l'error residual de l'ordre de a−(1/6) + ε, on ε; és infinitesimal. La constant C en aquesta fórmula és igual a

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

on γ és la constant d'Euler-Mascheroni i ζ' és la derivada de la Funció zeta de Riemann.[100][101] El coeficient principal (12/π2) ln 2 es va determinar per dos mètodes independents.[102][103]

Ja que la primera mitjana es pot calcular a partir de la mitjana de tau sumant sobre els divisors d de a.[104]

La funció T de a és igual a u sobre a multiplicat perl sumtori d'un argument estes sobre tots els divisors d de a. L'argument és igual a la funció phi de d multiplicada per la funció tau de d.

it can be approximated by the formula[105]

es pot aproximar per la fórmula.[105]

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

on Λ(d) és la funció de von Mangoldt.[106]

Una tercera mitjana Y (n) es definieix com el nombre mig de passos requerits quan els dos nombres a i b són escollits a l'atzar (amb la distribució uniforme) des de l'1 a n[105]

La funció Y és de n és igual a u sobre n quadrat vegades el doble de la suma de la funció T de a coma b per a tots els valors de a i b variant de 1 a n. Això és igual a u sobre n vegades la suma de la funció T de a sobre tots els valors de a variant des de u fins a n.

Substituint la fórmula aproximada per T(a) a aquesta equació dóna una estimació per Y(n).[107]

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

Despesa computacional per pas[modifica | modifica el codi]

A cada pas k de l'algorisme euclidià, el quocient qk i residu rk es calculen per a un parell donat d'enters rk−2 i rk−1

rk−2 = qk rk−1 + rk.

La despesa computacional per pas està associada principalment amb trobar qk, donat que el residu rk es pot calcular ràpidament a partir de rk−2, rk−1, i qk

rk = rk−2qk rk−1.

La despesa computacional de dividir nombres de h -bits és O(h(+1)), on és la longitud del quocient.[108]

Comparativament, l'algorisme basat en la sostracció original d'Euclides pot ser molt més lent. Una única divisió d'enter és equivalent a un nombre de sostraccions igual al quocient q. Si la proporció de a i b és molt gran, el quocient és gran i calen moltes sostraccions. D'altra banda, s'ha demostrat que és molt probable que els quocients siguin enters petits. La probabilitat d'un quocient donat q és aproximadament ln|u/( u − 1)| on u = (q + 1)2.[109] Per tenir una idea, la probabilitat que un quocient sigui 1, 2, 3, o 4 és aproximadament un 41.5%, un 17.0%, un 9.3%, i un 5.9%, respectivament. Com que l'operació de sostracció és més ràpida que la divisió, especialment per a nombres grans,[110] l'algorisme d'Euclides basat en la sostracció és competitiu amb la versió basada en la divisió.[111] Això s'explota en la versió binària de l'algorisme d'Euclides.[112]

Combinant el nombre aproximat de passos amb la despesa computacional aproximada per pas es mostra que l'algorisme de l'Euclides augmenta de manera quadràtica (h2) amb el nombre mitjà de dígits h dels dos nombres inicials a i b. Sia h0, h1, …, hN−1 el nombre de dígits en els successius residus r0, r1, …, rN−1. Com que el nombre de passos N creix linealment amb h, el temps d'execució queda fitat per

L' ordre del sumatori sobre tot i menor que N de h sub i multiplcat per parèntesi h sub i menys h sub i més u més 2 tanca parèntesi és un subconjunt de l'ordre de h pel sumatori sobre tot i menor que N de h sub i menys h sub i més u més 2, que a a la vegada és un subconjunt de l'ordre de h multiplicat per h sub zero més 2 N, que a l'hora és un subconjunt de l'ordre de h al quadrat.

Eficiència de mètodes alternatius[modifica | modifica el codi]

L'algorisme d'Euclides es fa servir a bastament en la pràctica, especialment per a nombres petits, a causa de la seva simplicitat. Per comparació, es pot determinar l'eficiència d'alternatives a l'algorisme d'Euclides.

Una aproximació ineficaç per trobar el MCD de dos nombres naturals a i b és trobar tots els seus divisors comuns; el MCD és llavors el comú divisor més gran. Els divisors comuns es poden trobar dividint els dos nombres per enters successius des de 2 fins al nombre més petit b. El nombre de passos d'aquest enfocament augmenta linealment amb b, o exponencialment en el nombre de dígits. Una altra aproximació ineficaç és trobar els factors primers d'un o els dos nombres. Com s'ha comentat més amunt, el MCD és igual al producte dels factors primers compartits pels dos nombres a i b.[7] Els mètodes presents per descomposició en factors primers són també ineficients; molts sistemes de criptografia moderns fins i tot depenen d'aquesta ineficiència.[10]

L'algorisme de Stein és una alternativa eficient que substitueix la divisió per operacions més ràpides explotant la representació binària emprada pels ordinadors.[113][114] Tanmateix, aquesta alternativa també és O(H²). És generalment més ràpid en ordinadors reals, però l'ordre de magnitud és el mateix que a l'algorisme euclidià.[115] L'eficiència addicional es pot assolir gràcies a examinar només els dígits principals dels dos nombres a i b.[116][117] L'algorisme de Stein que treballa en base 2 es pot estendre a altres bases (algorismes base k),[118] amb augments de velocitat de fina a quintuplicar-la.[119]

Un enfocament recursiu per a enters molt grans (amb més de 25.000 dígits) porta a algorismes de MCD subquadràtics,[120] com els de Schönhage,[121][122] i Stehlé i Zimmermann.[123] Aquests algorismes exploten la forma de matriu de 2×2 de l'algorisme euclidià donat més amunt. Aquests mètodes subquadràtics generalment tenen una complexitat de O(h (log h)2 (log log h)).[115][124]

Altres sistemes de nombres[modifica | modifica el codi]

Com descrit a dalt, l'algorisme euclidià s'utilitza per trobar el màxim comú divisor de dos nombres naturals (enters positius). Tanmateix, es pot generalitzar als nombres reals, i a més sistemes de nombre exòtics com polinomis, enters quadràtics i quaternions de Hurwitz. En els últims casos, l'algorisme euclidià s'utilitza per demostrar la propietat fonamental de que la factorització és única, és a dir, que tals nombres es poden factoritzar de forma única en elements irreductibles, els homòlegs dels nombres primers. La factorització única és essencial per moltes demostracions de teoria de nombres.

Nombres racionals i reals[modifica | modifica el codi]

L'algorisme d'Euclid es pot aplicar a nombres reals, com va descriure Euclides al Llibre 10 del seu Elements. L'objectiu de l'algorisme és identificar un nombre real g tal que donats dos nombres reals, a i b, són múltiples enters d'aquest: a = mg i b = ng, on m i n són enters.[32] Aquesta identificació és equivalent a trobar una relació entera entre els nombres reals a i b; és a dir, determinar enters s i t tals que sa + tb = 0. Euclides utilitza aquest algorisme per tractar la qüestió de longituds incommensurables.[125][126]

L'algorisme euclidià per nombres reals difereix del seu homòleg d'enters en dos aspectes. Primer, els residus rk són nombres reals, encara que els quocients qk són enters com abans. Segon, no està garantit que l'algorisme acabi en un nombre finit N de passos. Si ho fa, la fracció a/b és un nombre racional, és a dir, la raó de dos enters

a/b = mg/ng = m/n

i es pot escriure com a fracció contínua finita [q0; q1, q2, …, qN]. Si l'algorisme no s'atura, la fracció a /b és un nombre irracional i es pot descriure per una fracció contínua infinita [q0; q1, q2, …]. Exemples de fraccions contínues infinites són la secció àuria φ = [1; 1, 1, …] i l'arrel quadrada de dos, √2 = [1; 2, 2, …]. En general, és improbable que l'algorisme s'aturi, ja que gairebé tots els casos a /b de dos nombres reals són irracionals.

Una fracció contínua infinita es pot truncar en un pas k [q0; q1, q2, …, qk] per obtenir una aproximació a a/b que millora a mesura que k creix. L'aproximació es descriu per mk/nk; els numeradors i els denominadors són coprimers i obeeixen la recurrència

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

on m−1 = n−2 = 1 i m−2 = n els−1 = 0 són els valors inicials de la recurrència. La sucessió mk/nk és la millor aproximació d'un nombre racional a a/b amb el denominador nk:

El valor absolut de la diferència de dues proporcions (a partit per b menys m sub k partit per n sub k) és més petit que un partit per n sub k al quadrat.

Polinomis[modifica | modifica el codi]

Els polinomis d'una única variable x es poden sumar, multiplicar i factoritzar en polinomis irreductibles, que són els anàlegs als nombres primers per a enters. El polinomi màxim comú divisor g(x) de dos polinomis a(x) i b(x) es defineix com el producte dels seus polinomis irreductibles compartits, que es poden identificar utilitzant l'algorisme euclidià.[127] El procediment bàsic és similar al cas dels enters. A cada pas k, es troben un polinomi quocient qk(x) i un polinomi de residu rk(x) que satisfan l'equació recursiva

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

on r−2(x) = a (x) i r−1(x) = b (x). El polinomi de quocient s'escull de forma que el terme principal de qk(x) rk −1(x) si gui igual al terme principal de rk −2(x); això assegura que el grau de cada residu sigui més petit que el grau del seu predecessor deg[rk(x) ] < deg[rk −1(x)]. Com que el grau és un enter no negatiu, i com que disminueix a tots els passos, l'algorisme euclidià acaba en un nombre finit de passos. El residu diferent de zero final és el màxim comú divisor dels dos polinomis originals, a(x) i b(x).[128]

Per exemple, considerant els segënts dos polinomis quàrtics, que cada un es factoriza en dos polinomis quadràtics

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

Dividint a(x) entre b(x) dóna una residu r0(x) = x3 + (2/3)x2 + (5/3)x − (2/3). Al següent pas b(x) es divideix entre r0(x) donant un residu r1(x) = x2 + x + 2. Finalment, dividint r0(x) entre r1(x) dóna un zero de residu, el que indica que r1(x) és el polinomi màxim comú divisor de a(x) i b(x), coherent amb la seva factorització.

Moltes de les aplicacions descrites a dalt per a enters s'apliquen a polinomis.[129] L'algorisme euclidià es pot fer servir per resoldre equacions diofàntiques lineals i problemes de residus xinesos per a polinomis; també es poden definir fraccions contínues de polinomis.

L'algorisme euclidià polinòmic també té altres aplicacions, com el Teorema de Sturm, un mètode per comptar el nombre d'arrels reals d'un polinomi dins d'un interval donat de l'eix real. Això té aplicacions en unes quantes àrees, com el Criteri d'estabilitat de Routh-Hurwitz en teoria del control.

Finalment, els coeficients dels polinomis no cal que siguin enters, nombres reals o ni tan sols nombres complexos. Per exemple, els coeficients poden pertànyer a un cos general, com els cossos finits GF(p) descrits més amunt. Les conclusions corresponents sobre l'algorisme euclidià i les seves aplicacions es mantenen fins i tot per aquesta mena de polinomis.[127]

Exemple d'aplicació a trobar múltiples[modifica | modifica el codi]

Un exemple no massa complicat, però tampoc trivial:

Siga  P=X^3-6X^2-63X+392 \quad un polinomi que e que té una arrel doble.

com resoldre una equació de tercer grau no és evident, per a trobar l'arrel múltiple emprem la propietat que diu les arrels múltiples són les comunes entre el polinomi i el seu polinomi derivat.

Per a simplificar les divisions, ens permetem multiplicar-los per factors constants no nuls, en fi de comptes el mcd de dos polinomis està definit mòdul un factor multiplicador, de manera que esta manipulació no altera el resultat.

El polinomi derivat de P és  P' = 3X^2 - 12X - 63 \quad que es pot simplificar per 3, segons el que s'ha dit anteriorment.

Prenguem llavors  Q = \frac {P'} 3 = X^2 - 4X - 21 i efectuem l'algorisme amb P i Q.

P = (X-2)Q -50X + 350 \quad . La resta es factoritza en \quad -50(X - 7) : prenguem llavors \quad R = X - 7

Q = (X+3)R + 0 \quad el que implica que el mcd buscat és X-7 \quad llavors 7 és l'arrel doble de P.

En efecte:  P = (X - 7)^2(X + 8 ) \quad i de pas  P' = 3(X - 7)(X + 3) \quad

Enters de Gauss[modifica | modifica el codi]

"Un conjunt de punts que són dins d'una circumferència. El patró des punts té simetria quàdruple, és a dir, les rotacions de 90 graus deixen inalterat el dibuix. El dibuix també es pot reflectir sobre quatre línies que passen a través del centre del cercle: els eixos verticals i horitzontals, i les dues línies diagonals a ±45 graus."
Distribució de nombres primers de Gauss u + vi al pla complex, amb normes u2 + v2 menors de 500

Els enters de Gauss són nombres complexos de la forma α = u + vi, on u i v són enters ordinaris i i és la unitat imaginària.[130] Definint un anàleg de l'algorisme euclidià, es pot demostrar que els enters gaussians són factorizables de forma única, per la Identitat de Bézout.[45] Aquesta factorització única és útil en moltes aplicacions, com trobar totes les ternes pitagòriques o en la demostració del teorema de la suma de dos quadrats.[130] En general, l'algorisme euclidià és convenient en tals aplicacions, però no essencial; per exemple, els teoremes sovint es poden demostrar amb altres arguments.

L'algorisme euclidià desenvolupat per a dos enters gaussians α i β és gairebé el mateix que per a enters normals, però difereix en dos aspectes. Com abans, la tasca a cada pas k és identificar un quocient qk i una residu rk tals que

rk = rk−2qk rk−1

on rk −2 = α, rk −1 = β, i totes els residus són estrictament més petits que els seus predecessors,|rk| < |rk −1|. La primera diferència és que els quocients i residus són ells mateixos enters gaussians, i així són nombres complexos. Els quocients qk es troben en general arrodonint les parts real i complexa del quocient exacte (com el nombre complex α/β) als enters més propers. La segona diferència és la necessitat de definir com pot ser un residu complex "més petit" que un altre. Per fer això, es defineix una funció norma f (u + v i) = u2 + v2, que converteix cada enter gaussià u + vi a un enter normal. Després de cada pas k de l'algorisme euclidià, la norma del residu f (rk) és més petita que la norma del residu anterior, f(rk −1). Ja que la norma és un enter no negatiu i disminueix amb tots els passos, l'algorisme euclidià per a enters gaussians acaba en un nombre finit de passos. La resta diferent de zero final és el MCD(α,β), l'enter gaussià de norma més gran que divideixi els dos α i β; és únic tret de una multiplicació per una unitat, ±1 o ±i.

Moltes de les altres aplicacions de l'algorisme euclidià es passen als enters gaussians. Per exemple, es pot utilitzar per resoldre equacions diofàntiques lineals i problemes de residus xinesos per a enters gaussians; també es poden definir fraccions contínues d'enters gaussians.

Dominis euclidians[modifica | modifica el codi]

Un conjunt d'elements amb dues operacions binàries, + i ·, s'anomenen un anell euclidià si forma un anell commutatiu R i, a grans trets, si s'hi pot aplicar un algorisme euclidià generalitzat.[131][132] Les dues operacions de tal anell no necessiten ser l'addició i multiplicació de l'aritmètica corrent; poden ser, més aviat, més generals, com les operacions d'un grup matemàtic o monoide. No obstant això, aquestes operacions generals han de respectar moltes de les lleis que governen l'aritmètica corrent, com la propietat commutativa, la propietat associativa i la propietat distributiva.

L'algorisme euclidià generalitzat requereix una funció euclidiana, és a dir, una funció f de R al conjunt d'enters no negatius tal que, per a dos elements diferents de zero qualssevol a i b en R, existeix q i r en R tals que a = qb + r i f(r) < f(b). Un exemple d'aquesta funció és la funció norma utilitzada amb els entersde Gauss a la secció anterior. La funció f pot ser la magnitud del nombre, o el grau d'un polinomi. El principi bàsic és que es redueix a cada pas de l'algorisme; per això, si f es pot reduir només un nombre finit de vegades, l'algorisme s'ha d'aturar en un nombre finit de passos. Aquest principi depèn fortament de l'odre natural dels enters no negatius; a grans trets, això exigeix que tots els conjunts d'enters no negatius tinguin un membre més petit que tots els altres.

El teorema fonamental de l'aritmètica s'aplica a qualsevol anell euclidià: Qualsevol nombre d'un anell euclidià es pot factoritzar de manera única amb elements irreductibles. Qualsevol anell euclidià és un domini de factorització única (UFD), encara que el contrari no és cert. Els anells euclidians són una subclasse dels anells de MCD, anells en els quals sempre existeix un màxim comú divisor de dos nombres. En altres paraules, un màxim comú divisor pot existir (per a tots els elements en un anell), encara que pot no ser possible trobar-lo utilitzant un algorisme euclidià. Un anell euclidià és sempre un anell d'ideals principals, un anell íntegre en el qual tots els ideals són un ideal principal. Una altra vegada, el contrari no és vcert: no tots els anells ideal principal són un anell euclidià.

La factorització única d'anells euclidians és útil en moltes aplicacions. Per exemple, la factorització única dels enters gaussians és convenient permetent obtenir fórmules per totes les ternes pitagòriques i demostrar el teorema de la suma de dos quadrats.[130] La factorització única era també un element clau en un intent de demostració del darrer teorema de Fermat publicat el 1847 per Gabriel Lamé, el mateix matemàtic que analitzava l'eficiència de l'algorisme d'Euclides, basat en un suggeriment de Joseph Liouville.[133] l'aproximació de Lamé exigia la factorització única de nombres de la forma x + ωy, on x i y són enters, i ω = e2i π/n és una n arrel d'1, és a dir ωn = 1. Encara que aquesta aproximació té èxit per a alguns valors de n (com n =3, els Enters d'Eisenstein), en general tals nombres no es factoritzen únicament. Aquest fracàs de factorització única en alguns anells ciclotòmics portava Ernst Kummer al concepte de nombres ideals i, més tard, a Richard Dedekind al d'ideals.[134]

Factorització única d'enters quadràtics[modifica | modifica el codi]

"Un conjunt de punts que són dins d'una circumferència. El dibuix de punts té simetria tal que les rotacions de 60 graus deixen inalterat el dibuix. El dibuix també es pot reflectir sobre sis línies que passen a través del centre de la circumferència: els eixos verticals i horitzontals, i les quatre línies diagonals a ±30 i ±60 graus."
Distribució de nombres primers d'Eisenstein u + vω al pla complex, amb normes menors de 500. El nombre ω és igual a l'arrel cúbica de 1.

Els anells d'enters quadràtics són útils per il·lustrar anells euclidians. Els enters quadràtics són generalizations dels enters gaussians en que la unitat imaginària i és reemplaçada per un nombre ω. Així, tenen la forma u + v ω, on u i v són enters i ω té una de dues formes, depenent d'un paràmetre D. Si D no és igual a un múltiple de quatre més un, llavors

ω = √D.

Tanmateix, si D és igual a un múltiple de quatre més u, llavors

ω = (1 + √D)/2.

Si la funció f correspon a una funció norma, tal com la emprada per ordenar els Enters de Gauss més amunt, llavors l'anell es coneix com normat amb una norma euclidiana. Els anells amb norma euclidiana d'enters quadràtics són exactament aquells on D = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 o 73.[25] Els enters quadràtics amb D = −1 i −3 es coneixen com els Enters gaussians i enters d'Eisenstein, respectivament.

Si és permet que f sigui qualsevol funció euclidiana, llavors la llista de possibles valors D per als quals l'anell és euclidià encara no es coneix.[135] El primer exemple d'un anell euclidià que no era de norma euclidiana (amb D =69) era publicat el 1994.[135] El 1973, Weinberger demostrava que un anell d'enters quadràtics amb D > 0 és euclidià si, i només si, és un anell d'ideals principals, a condició que es compleixi la hipòtesi de Riemann generalitzada.[136]

Anells no commutatius[modifica | modifica el codi]

També és possible aplicar l'algorisme euclidià a anells no commutatius com el conjunt de quaternions de Hurwitz.[137] Siguin α i β dos elements de tal anell. Tenen un comú bé divisor δ si α = ξδ i β = ηδ per a alguna elecció de ξ i η a l'anell. De forma similar, tenen un divisor per l'esquerra comú si α = δξ i β = δη per a alguna elecció de ξ i η a l'anell. com que la multiplicació no és commutativa, hi ha dues versions de l'algorisme euclidià, una per a divisors per la dreta i una per a divisors per l'esquerra. Escollint els divisors per la dreta, el primer pas per trobar el MCD(α, β) amb l'algorisme euclidià es pot escriure

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

on ψ0 representa el quocient i ρ0 el residu. Aquesta equació mostra que qualsevol divisor comú de α i β és de la mateixa manera un comú divisor del residu ρ0. L'equació anàloga per als divisors per l'esquerra seria

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

Amb qualsevol elecció, el procés es repeteix com a dalt fins que el màxim comú divisor per la dreta o per l'esquerra s'identifiqui. Com en l'anell euclidià, la "mida" del residu ρ0 ha de ser estrictament més petita que β, i hi ha d'haver només un nombre finit de mides possibles per a ρ0, de manera que es garanteixi que l'algorisme s'acaba.

La majoria dels resultats per al MCD passen a nombres no commutatius. Per exemple, la identitat de Bézout estableix que el MC(α, β) per la dreta es pot expressar com a combinació lineal de α i β. En altres paraules, hi ha nombres σ i τ tals que

Γdreta = σα + τβ

La identitat anàloga per al MCD per l'esquerra és gairebé la mateixa

Γesquerra = ασ + βτ

La identitat de Bézout es pot fer servir per resoldre equacions diofàntiques.

Generalitzacions a altres estructures matemàtiques[modifica | modifica el codi]

"Un cordó enrotllat set vegades al voltant d'un torus i reconnectat al seu començament, formant un bucle tancat. En el procés, el cordó completa tres circuits del torus, conformant un (3, 7) nus de torus."
L'algorisme euclidià es pot aplicar en la teoria de nusos.[138]

L'algorisme euclidià té tres trets generals que junts asseguren que no continuarà indefinidament. Primer, es pot escriure com a seqüència d'equacions recursives

rk = rk−2qk rk−1

on cada residu és estrictament més petit que el seu predecessor,|rk| < |rk −1|. Segon, la mida de cada residu té un límit inferior estricte, com|rk| ≥ 0. Tercer, hi ha només un nombre finit de mides més petites que un residu donat|rk|. Els Generalitzacions de l'algorisme d'Euclides amb aquests trets bàsics s'han aplicat a altres estructures matemàtiques, com embolics[139] i a nombres ordinals transfinits.[140]

Una generalització important de l'algorisme euclidià és el concepte d'una base de Gröbner en geometria algebraica. Com s'ha mostrat més amun, El MCD g de dos enters A i b és el generador del seu ideal. En altres paraules, per a qualsevol elecció dels enters s i t, hi ha un altre enter m tal que

sa + tb = mg.

Encara que això roman cert quan s, t, m, a i b representen polinomis d'una única variable, no és vert per a anells de més d'una variable.[141] En aquest cas, un conjunt finit de polinomis generadors g1, g2, etc. pot ser definit tal que qualsevol combinació lineal de dos polinomis multivariables a i b pot ser expressat com múltiples dels generadors

sa + tb = Σk mkgk

on s, t i mk són polinomis multivariables.[142] Qualsevol polinomi multivariable f es pot expressar com tal suma de polinomis generadors més un polinomi residu únic r, a vegades anomenat la forma normal del polinomi f

f = r + Σk qkgk

encara que els polinomis quocient qk poden no ser únics.[143] El conjunt d'aquests polinomis generadors es coneixe com a base de Gröbner.[144]

Notes[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  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àg. 16.
  3. Stark, pàg. 21.
  4. LeVeque, pàg. 32.
  5. Leveque, pàg. 31.
  6. Grossman JW. Discrete Mathematics. Nova York: Macmillan, 1990, p. 213. ISBN 0-02-348331-8. 
  7. 7,0 7,1 Schroeder, pàg. 21-22.
  8. Schroeder, pàg. 19.
  9. . Ogilvy CS, Anderson JT. Excursions in number theory. Nova York: Oxford University Press, 1966, p. 27–29. LCCN 66-0-14484. 
  10. 10,0 10,1 Schroeder, pàg. 216-219.
  11. 11,0 11,1 Leveque, pàg. 33.
  12. Stark, pàg. 25.
  13. Oregon, pàg. 47-48.
  14. Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. 3rd. Addison-Wesley, 1997. ISBN 0-201-89683-4.  (Secció 1.2.1: Inducció matemàtica, pàg. 11-21.)
  15. Rosen, pàg. 18-21.
  16. Rosen, pàg. 21-24.
  17. Anderson JA. Discrete Mathematics with Combinatorics. de localitzacions, Nj: Prentice Hall, 2001, p. 165–223. ISBN 0-13-086998-8. 
  18. Rosen, pàg. 492.
  19. Anderson JA. Discrete Mathematics with Combinatorics. de localitzacions, Nj: Prentice Hall, 2001, p. 109–119. ISBN 0-13-086998-8. 
  20. 20,0 20,1 Stark, pàg. 18.
  21. 21,0 21,1 Stark, pàg. 16-20.
  22. Knuth, pàg. 320.
  23. . Lovász L, Pelikán J, Vesztergombi K. Discrete Mathematics: Elementary and Beyond. d'editor localització = Nova York: Springer-Verlag, 2003, p. 100–101. ISBN 0-387-95584-4. 
  24. Kimberling C. «A Visual Euclidean Algorithm». Mathematics Teacher, 76, 1983, pàg. 108–109.
  25. 25,0 25,1 Cohn, pàg. 104-110.
  26. Knuth, pàg. 319-320.
  27. Knuth, pàg. 318-319.
  28. Stillwell, pàg. 14.
  29. 29,0 29,1 Oregon, pàg. 43.
  30. 30,0 30,1 . Stewart BM. Theory of Numbers. 2n. Nova York: Macmillan, 1964, p. 43–44. LCCN 64-0-10964. 
  31. 31,0 31,1 Knuth, pàg. 318.
  32. 32,0 32,1 Weil A. Number Theory. Boston: Birkhäuser, 1983, p. 4–6. ISBN 0-8176-3141-0. 
  33. . Jones A. «Greek mathematics to AD 300». A: Companion encyclopedia of the history and philosophy of the mathematical sciences. Nova York: Routledge, 1994, p. 46–48. ISBN 0-415-09238-8. 
  34. van der Waerden BL. Science Awakening. Groningen: P. Noordhoff Ltd, 1954, p. 114–115 (translated by Arnold Dresden). 
  35. . von Fritz K. «The Discovery of Incommensurability by Hippasus of Metapontum». Ann. Math., 46, 1945, pàg. 242–264. DOI: 10.2307/1969021.
  36. Heath TL. Mathematics in Aristotle. Oxford Press, 1949, p. 80–83. 
  37. . Fowler DH. The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press, 1987, p. 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, 1933, pàg. 311–333.
  39. 39,0 39,1 Stillwell, pàg. 31.
  40. 40,0 40,1 Tattersall, pàg. 70.
  41. Rosen, pàg. 86-87.
  42. Oregon, pàg. 247-248.
  43. Tattersall, pàg. 72, 184-185.
  44. Tattersall, pàg. 72-76.
  45. 45,0 45,1 Gauss CF. «Theoria residuorum biquadraticorum». Comm. Soc. Reg. Sci. Gött. Rec., 4, 1832. Vegeu també Werke, 2:67-148.
  46. Stillwell, pàg. 31-32.
  47. Dirichlet, pàg. 29-31.
  48. Dedekind R. «Supplement XI». A: PGL Dirichlet. Vorlesungen über Zahlentheorie, 1894. 
  49. Stillwell J. Elements of Number Theory. d'editor localització = Nova York: Springer-Verlag, 2003, p. 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, 1829, pàg. 419–422.
  51. Weisstein, Eric W., "Integer Relation" a MathWorld (en anglès).
  52. Peterson I. «Jazzing Up Euclid's Algorithm». ScienceNews, 12 August 2002.
  53. . Cipra BA. «The Best of the 20th Century: Editors Name Top 10 Algorithms]». SIAM News. Society for Industrial and Applied Mathematics, 33, 4, 16 May 2000.
  54. Cole AJ, Davie AJT. «A game based on the Euclidean algorithm and a winning strategy for it». Math. Gaz., 53, 1969, pàg. 354–357. DOI: 10.2307/3612461.
  55. Spitznagel EL. «Properties of a game based on Euclid's algorithm». Math. Mag., 46, 1973, pàg. 87–92.
  56. Rosen, pàg. 95.
  57. . Roberts J. Elementary Number Theory: A Problem Oriented Approach. Cambridge, Ma: MIT Press, 1977, p. 1–8. ISBN 0-262-68028-0. 
  58. Jones GA, Jones JM. «Bezout's Identity». A: Elementary Number Theory. d'editor localització = Nova York: Springer-Verlag, 1998, p. 7–11. 
  59. Rosen, pàg. 81.
  60. . Cohn, pàg. 104.
  61. Rosen, pàg. 91.
  62. Schroeder, pàg. 23.
  63. Rosen, pàg. 90-93.
  64. 64,0 64,1 Koshy T. Elementary Number Theory with Applications. Burlington, Ma: Harcourt/Academic Press, 2002, p. 167–169. ISBN 0-12-421171-2. 
  65. Bach E, Shallit J. Algorithmic number theory. Cambridge, Ma: MIT Press, 1996, p. 70–73. ISBN 0-262-02405-5. 
  66. Stark, pàg. 26-36.
  67. 67,0 67,1 Oregon, pàg. 44.
  68. Stark, pàg. 281-292.
  69. Rosen, pàg. 119-125.
  70. Schroeder, pàg. 106-107.
  71. Schroeder, pàg. 108-109.
  72. Rosen, pàg. 120-121.
  73. Stark, pàg. 47.
  74. Schroeder, pàg. 107-109.
  75. Stillwell, pàg. 186-187.
  76. Schroeder, pàg. 134.
  77. "Error correction coding: mathematical methods and algorithms", pàgina 266, Todd K. Moon, John Wiley and sons, 2005, Isbn 0471648000
  78. Rosen, pàg. 143-170.
  79. Schroeder, pàg. 194-195.
  80. Vinogradov IM. Elements of Number Theory. Nova York: Dover, 1954, p. 3–13. 
  81. Crandall R, Pomerance C. Prime Numbers: A Computational Perspective. 1r. d'editor localització = Nova York: Springer-Verlag, 2001, p. 225–349. ISBN 0-387-94777-9. 
  82. Knuth, pàg. 369-371.
  83. Shor PW. «Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer». SIAM J. Sci. Statist. Comput., 26, 1997, pàg. 1484.
  84. Dixon JD. «Asymptotically fast factorization of integers». Math. Comput., 36, 1981, pàg. 255–260. DOI: 10.2307/2007743.
  85. Lenstra Jr. HW. «Factoring integers with elliptic curves». Annals of Mathematics, 126, 1987, pàg. 649–673. DOI: 10.2307/1971363.
  86. Knuth, pàg. 380-384.
  87. Knuth, pàg. 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, 1844, pàg. 867–870.
  89. Grossman H. «On the Number of Divisions in Finding a G.C.D.». The American Mathematical Monthly, 31, 1924, pàg. 443. DOI: 10.2307/2298146.
  90. . Honsberger R. Mathematical Gems II. The Mathematical Association of America, 1976, p. 54–57. ISBN 0-88385-302-7. 
  91. 91,0 91,1 91,2 Knuth, pàg. 344.
  92. Oregon, pàg. 45.
  93. 93,0 93,1 Knuth, pàg. 343.
  94. Mollin, pàg. 21.
  95. LeVeque, pàg. 35.
  96. Mollin, pàg. 21-22.
  97. Knuth, pàg. 353.
  98. Knuth, pàg. 357.
  99. . Tonkov T. «On the average length of finite continued fractions». Acta arithmetica, 26, 1974, pàg. 47–57.
  100. Porter JW. «On a Theorem of Heilbronn». Mathematika, 22, 1975, pàg. 20–28.
  101. Knuth DE. «Evaluation of Porter's Constant». Computers and Mathematics with Applications, 2, 1976, pàg. 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, 1970, pàg. 414–422. DOI: 10.1016/0022-314X(70)90044-2.
  103. . Heilbronn HA. «On the Average Length of a Class of Finite Continued Fractions». A: Paul Turán. Number Theory and Analysis. Nova York: Plenum, 1969, p. 87–96. LCCN 68-00-8991. 
  104. Knuth, pàg. 354.
  105. 105,0 105,1 105,2 Norton GH. «On the Asymptotic Analysis of the Euclidean Algorithm». Journal of Symbolic Computation, 10, 1990, pàg. 53–58. DOI: 10.1016/S0747-7171(08)80036-3.
  106. Knuth, pàg. 355.
  107. Knuth, pàg. 356.
  108. Knuth, pàg. 257-261.
  109. Knuth, pàg. 352.
  110. Wagon S. Mathematica in Action. d'editor localització = Nova York: Springer-Verlag, 1999, p. 335–336. ISBN 0-387-98252-3. 
  111. Cohen, pàg. 14.
  112. Cohen, pàg. 14-15, 17-18.
  113. Knuth, pàg. 321-323.
  114. Stein J. «Computational problems associated with Racah algebra». Journal of Computational Physics, 1, 1967, pàg. 397–405. DOI: 10.1016/0021-9991(67)90047-2.
  115. 115,0 115,1 Crandall R, Pomerance C. Prime Numbers: A Computational Perspective. 1r. d'editor localització = Nova York: Springer-Verlag, 2001, p. 77–79, 81–85, 425–431. ISBN 0-387-94777-9. 
  116. Knuth, pàg. 328.
  117. . Lehmer DH. «Euclid's Algorithm for Large Numbers». The American Mathematical Monthly, 45, 1938, pàg. 227–233. DOI: 10.2307/2302607.
  118. Sorenson J. «Two fast MCD algorithms». J. Algorithms, 16, 1994, pàg. 110–144. DOI: 10.1006/jagm.1994.1006.
  119. Weber K. «The accelerated MCD algorithm». ACM Trans. Math. Soft., 21, 1995, pàg. 111–122. DOI: 10.1145/200979.201042.
  120. Aho A, Hopcroft J, Ullman J. The Design and Analysis of Computer Algorithms. Nova York: Addison–Wesley, 1974, p. 300–310. 
  121. Schönhage A. «Schnelle Berechnung von Kettenbruchentwicklungen». Acta Informatica, 1, 1971, pàg. 139–144. DOI: 10.1007/BF00289520.
  122. . Cesari G. «Parallel implementation of Schönhage's integer MCD algorithm». A: G. Buhler. Algorithmic Number Theory: Proc. ANTS-III, Portland, OR. d'editor localització = Nova York: Springer-Verlag, 1998, p. 64–76.  Volum 1423 en bitllets de Conferència en la Informàtica.
  123. Stehlé D, Zimmermann P. «Gal’s accurate tables method revisited». A: Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17). Los Alamitos, Ca: IEEE Computer Society Press, 2005. 
  124. Möller N. «On Schönhage's algorithm and subquadratic integer MCD computation». Mathematics of Computation, 77, 2008, pàg. 589–607. DOI: 10.1090/S0025-5718-07-02017-0.
  125. Boyer CB, Merzbach UC. A History of Mathematics. 2n. Nova York: Wiley, 1991, p. 116–117. ISBN 0-471-54397-7. 
  126. . Cajori F. A History of Mathematics. Nova York: Macmillan, 1894, p. 70. 
  127. 127,0 127,1 Lang S. Algebra. 2n. Menlo de localitzacions, Ca: Addison–Wesley, 1984, p. 190–194. ISBN 0-201-05487-6. 
  128. Cox, pàg. 37-46.
  129. Schroeder, pàg. 254-259.
  130. 130,0 130,1 130,2 Stillwell J. Elements of Number Theory. d'editor localització = Nova York: Springer-Verlag, 2003, p. 101–116. ISBN 0-387-95587-9. 
  131. Stark, pàg. 290.
  132. . Cohn, pàg. 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, 1847, pàg. 172–184.
  134. (anglès) Leo Corry, Modern algebra and the rise of mathematical structures, p.81
  135. 135,0 135,1 Clark DA. «A quadratic field which is Euclidean but not norm-Euclidean». Manuscripta mathematica, 83, 1994, pàg. 327–330. DOI: 10.1007/BF02567617.
  136. Weinberger P. «On Euclidean rings of algebraic integers». Proc. Sympos. Pure Math., 24, pàg. 321–332.
  137. Stillwell J. Elements of Number Theory. d'editor localització = Nova York: Springer-Verlag, 2003, p. 151–152. ISBN 0-387-95587-9. 
  138. Yamada Y. «Generalized rational blow-down, torus knots, and Euclidean algorithm». Falta indicar la publicació, 2007. arXiv: 0708.2316v1.
  139. Conway, John Horton. «An enumeration of knots and links, and some of their algebraic properties». A: Computational Problems in Abstract Algebra. Oxford: Pergamon, 1967), p. 329–358. 
  140. Jategaonkar AV. «Rings with transfinite left division algorithm». Bull. Amer. Math. Soc., 75, 1969, pàg. 559–561. DOI: 10.1090/S0002-9904-1969-12242-1.
  141. Cox, pàg. 65.
  142. Cox, pàg. 73-79.
  143. Cox, pàg. 79-86.
  144. Cox, pàg. 74.

Bibliografia[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Algorisme d'Euclides Modifica l'enllaç a Wikidata