Algorisme d'Euclides

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.

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, r₁, r_n ... r_n-1 i r_n = 0 els residus successius, llavors:

mcd (a, b) = mcd (b, r₁), amb r₁ = 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, r₁) = mcd (r₁, r₂) = mcd (r₂, r₃) = ... = mcd (r_n-1, r_n) = mcd (r_n-1, 0) = r_n-1.

Això permet detallar l'algorisme efectiu:

dades d'entrada a i b  - si cal, canvieu-los a positius l'algorisme: mentre b ≠ 0 repetiu les tres instruccions següents: r ← residu de a entre b    (doneu a r el valor del residu de a entre 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 dona com a resultat 0 si a i b són nuls, mentre que en matemàtiques el major divisor de zero no existix.

Fonaments

Màxim comú divisor

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), 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. Aquesta propietat és independent de si a i b són ells mateixos nombres primers. 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ú.

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

El MCD es pot visualitzar de la manera següent. 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. 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. La factorització d'enters grans es creu que és un problema tan difícil que s'hi basen molts sistemes de criptografia moderns.

Una definició més subtil del MCD és útil en matemàtiques avançades, especialment en teoria d'anells. 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, que es pot calcular prenent el MCD de cada parella de nombres. Per exemple

$MCD(a,b,c)=MCD(a,MCD(b,c))=MCD(MCD(a,b),c)=MCD(MCD(a,c),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

Tres mètodes matemàtics relacionats s'utilitzen en els arguments següents: inducció, recursivitat i descent infinit. La inducció sovint es fa servir per demostrar un teorema per a tots els nombres naturals n. 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 és una equació que relaciona nombres que formen una sèrie a₁, a₂, a₃, etc. El terme n-èsim de la sèrie, a_n, sovint s'expressa en funció de termes anteriors de la sèrie, com a_{n −1}. Per exemple, els nombres de Fibonacci es defineixen recursivament; cada terme és la suma dels dos termes anteriors: F_n = F_{n −1} + F_{n −2}. Unes quantes equacions associades amb l'algorisme euclidià són recursives. Finalment, en el descens infinit, una solució donada en nombres naturals és utilitzada per construir una solució amb nombres naturals més petits. 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.

Descripció

Procediment

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. 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-èsim pas és trobar un quocient q_k i un residu r_k tals que satisfan l'equació

$r_{k-2}=q_{k}\ r_{k-1}+r_{k}$

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

Al pas inicial (k = 0), els residus r₋₂ i r₋₁ 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 ₀ del pas inicial, etcètera. Així, l'algorisme es pot escriure com a seqüència d'equacions

$a=q_{0}\ b+r_{0}$

$b=q_{1}\ r_{0}+r_{1}$

$r_{0}=q_{2}\ r_{1}+r_{2}$

$r_{1}=q_{3}\ r_{2}+r_{3}$

…

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 q₀ és igual a zero, i el residu r₀ és a. Així r_k és més petit que el seu predecessor r_k−1 per a tot k ≥ 0.

Com que els residus disminueixen amb tots els passos però mai no poden ser negatius, al final un residu r_N ha de ser igual a zero, en aquest punt s'atura l'algorisme. L'últim residu diferent de zero r_N−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 r₀ i zero.

Demostració de validesa

La validesa de l'algorisme d'Euclides es pot demostrar per un argument de dos passos. Al primer pas, es demostra que l'últim residu diferent de zero r_{N −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 r_{N −1}; per això g ha de ser menor que o igual a r_{N −1}. Aquestes dues conclusions impliquen que r_{N −1} = g.

Per demostrar que r_{N −1} divideix els dos a i b (el primer pas), r_{N −1} divideix el seu predecessor r_N−2

$r_{N-2}=q_{N}\ r_{N-1}$

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

$r_{N-3}=q_{N-1}\ r_{N-2}+r_{N-1}$

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

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 r_k . 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 r₀, des de r₀ = a − q ₀b = mc − q₀nc = (m − q₀n)c. Un argument anàleg demostra que c també divideix els subsegüents residus r₁, r₂, etc. Per això, el màxim comú divisor g ha de dividir r_N−1, el que implica que g ≤ r_N−1. Com que la primera part de l'argument mostrava l'invers (r_N−1 ≤ g), resulta que g = r_N−1. Així g és el màxim comú divisor de tots els parells de la successió:

$g=MCD(a,b)=MCD(b,r_{0})=MCD(r_{0},r_{1})=...=MCD(r_{N-2},r_{N-1})=r_{N-1}$

Exemple

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 (q₀ = 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 (q₁ = 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 (q₂ = 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 = q₂ 21 + r₂	q₂ = 7 i r₂ = 0; l'algorisme s'acaba

Visualització

L'algorisme d'Euclides es pot visualitzar en termes de l'analogia d'enrajolar donada abans per al màxim comú divisor. 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 r₀-per-b sense enrajolar, on r₀<b. Llavors s'intenta enrajolar el rectangle residual amb rajoles quadrades de r₀-per-r₀. Això deixa un segon rectangle residual r₁-per-r₀, que s'intenta enrajolar emprant rajoles quadrades de r₁-per-r₁, 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

Vegeu també: Divisió euclidiana

A tots els passos k, l'algorisme d'Euclides calcula un quocient q_k i un residu r_k de dos nombres r_{k −1} i r_{k −2}

$r_{k-2}=q_{k}\ r_{k-1}+r_{k}$

on la magnitud de r_k és estrictament menor que la de r_{k −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 q_k i r_k són únics, però això no cal per a l'algorisme d'Euclides.

En la versió original de l'algorisme d'Euclides, el quocient i el residu es troben per sostracció repetida; és a dir r_{k −1} es resta de r_{k −2} repetidament fins que la resta r_k és més petita que r_{k −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 dona el residu de dos nombres després de dividir-los; així

$r_{k}\equiv r_{k-2}\ mod\ r_{k-1}$

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

Implementacions

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

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

Al començament de la iteració k-èsima, la variable b conté l'últim residu r_k−1, mentre que la variable a conté el seu predecessor, r_k−2. El pas b := a mod b és equivalent a la fórmula de recurrència citada r_k ≡ r_{k −2} mod r_{k −1}. La variable auxiliar t conté el valor de r_k−1 mentre el proper residu r_k està sent calculat. Al final de la iteració del bucle, la variable b conté el residu r_k, mentre que la variable a conté el seu predecessor, r_{k −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.

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 r_{k −1} i r_{k −2}. Suposant que a és més gran que b al començament d'una iteració; llavors a és igual a r_{k −2}, com que r_{k −2} > r_{k −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 r_k. 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 r_{k +1}, etcètera.

La versió recursiva es basa en la igualtat de MCDs dels successius residus i la condició d'aturada MCD( r_{N −1}, 0) = r_{N −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

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. Prèviament, l'equació

$r_{k-2}=q_{k}\ r_{k-1}+rk$

suposa que r_{k −1} > r_k > 0. Tanmateix, es pot calcular un residu negatiu alternatiu e_k

$r_{k-2}=(q_{k}+1)\ r_{k-1}+e_{k}$

on r_{k −1} se suposa que és positiu. Si |e_k| < |r_k|, llavors r_k és reemplaçat per e_k. 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.

Desenvolupament històric

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. 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. El matemàtic i l'historiador Bartel 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. L'algorisme probablement era conegut per Èudox de Cnidos (sobre el 375 AC.). L'algorisme pot fins i tot predatar Èudox, sobre la base de l'ús del terme tècnic ἀνθυφαίρεσις (anthyphairesis, sostracció recíproca) en treballs d'Euclides i Aristòtil.

Segles més tard, l'algorisme d'Euclides es descobria independentment tant a l'Índia com a la Xina, 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", potser a causa de la seva eficàcia en la solució d'equacions diofàntiques. 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, la solució general era publicada per Qin Jiushao al seu llibre de 1247 Shushu Jiuzhang (數書九章 Els nou capítols de les arts matemàtiques). L'algorisme euclidià es descrivia per primera vegada a Europa a la segona edició del llibre de Bachet Problèmes plaisants et délectables (problemes agradables i divertits, 1624). 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.

El 1811, Reynaud feia el que sembla el primer anàlisi explícit de l'algorisme. 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. Gauss esmenta l'algorisme en el seu Disquisitiones arithmeticae (publicat el 1801), però només com a mètode per fraccions contínues. Émile Léger (1837) sembla haver estat el primer en descobrir el pitjor cas de l'algorisme: quan els inputs són nombres de Fibonacci consecutius. Peter Dirichlet sembla haver estat el primer a descriure l'algorisme euclidià com la base de gran part de la teoria de nombres. Dirichlet va observar que molts resultats de la teoria de nombres, com la factorització única, valdrien per a qualsevol altre sistema de nombres al qual es pogués aplicar l'algorisme euclidià. 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. 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 avall). 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.

"[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.

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, i els seus parents, l'algorisme LLL, l'algorisme HJLS, i l'algorisme PSLQ.

El 1969, Cole i Davie desenvolupaven un joc de dos jugadors basat en l'algorisme euclidià, anomenat El Joc d'Euclides, que té una estratègia òptima. 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 en 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 x − my pedres, mentre quedi un enter no negatiu. El guanyador és el primer jugador que redueixi una pila a zero pedres.

Aplicacions matemàtiques

La identitat de Bézout

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. En altres paraules, sempre és possible trobar enters s i t tals que g = sa + tb.

Els enters s i t es poden calcular a partir dels quocients q₀, q₁, etc. tirant enrere l'ordre de les equacions en l'algorisme d'Euclides. Començant amb l'equació més propera al final, g es pot expressar en termes del quocient q_{N −1} i els dos residus precedents, r_{N −2} i r _N−3.

$g=r_{N-1}=r_{N-3}-q_{N-1}\ r_{N-2}$

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

$r_{N-2}=r_{N-4}-q_{N-2}\ r_{N-3}$

$r_{N-3}=r_{N-5}-q_{N-3}\ r_{N-4}$

Substituint aquestes fórmules per r_N−2 i r_N−3 a la primera equació dona g com a suma lineal dels residus r_N−4 i r_N−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

$r_{2}=r_{0}-q_{2}\ r_{1}$

$r_{1}=b-q_{1}\ r_{0}$

$r_{0}=a-q_{0}\ b$

Després que tots els residus r₀, r₁, 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

La identitat de Bézout proporciona encara una altra definició del màxim comú divisor g de dos nombres a i b . Considerem 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 cert 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 dona 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. Per exemple, considerem 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

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.

$s_{k}=s_{k-2}-q_{k-1}s_{k-1}$

$t_{k}=t_{k-2}-q_{k-1}t_{k-1}$

amb els valors d'engegada

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1

Emprant aquesta recurrència, els enters de Bézout s i t venen donats per s = s_N i t = t_N, on N és el pas en el qual acaba l'algorisme amb r_N = 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

$r_{j}=s_{j}a+t_{j}b$

per a tot j menor que k. El pas k-èsim de l'algorisme dona l'equació

$r_{k}=r_{k-2}-q_{k-1}\ r_{k-1}$

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

$r_{k}=(s_{k-2}\ a+t_{k-2}\ b)-q_{k-1}(s_{k-1}\ a+t_{k-1}\ b)$

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

$r_{k}=s_{k}\ a+t_{k}\ b=(s_{k-2}-q_{k-1}\ s_{k-1})\ a+(t_{k-2}-q_{k-1}\ t_{k-1})\ b$

Mètode matricial

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

$a=q_{0}\ b+r_{0}$

$b=q_{1}\ r_{0}+r_{1}$

…

$r_{N-2}=q_{N}\ r_{N-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

$\mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}$

Això simplifica l'algorisme euclidià a la forma

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

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

${\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}$

Com que la primera equació dona

$g=(-1)^{N+1}\ (m_{22}\ a-m_{12}\ b)$

els dos enters de la identitat de Bézout són $s=(-1)^{N+1}m_{22}$ i $t=(-1)^{N}m_{12}$. 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

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. Per il·lustrar això, suposem 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 dona 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. 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 $a_{1},a_{2},...,a_{n}$, llavors w és també coprimer amb el seu producte, $a_{1}\times a_{2}\times \ldots \times a_{n}$.

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

$L=p_{1}p_{2}\ldots p_{m}=q_{1}q_{2}\ldots q_{n}$

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 factoritzacions 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

Gràfic d'una Equació diofàntica lineal, 9x + 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. Una equació diofàntica lineal típica busca enters x i y tals que:

ax + by = c

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

ax ≡ c mod b.

Sia g el màxim comú divisor de a i b. Els dos termes de ax + by són divisibles 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 Bézout

sa + tb = g

on s i t es poden trobar amb l'algorisme euclidià estès. Això proporciona una solució a l'equació diofàntica, $x_{1}=s(c/g)$ i $y_{1}=t(c/g)$.

En general, una equació diofàntica lineal no té solucions, o en té un nombre infinit. Per trobar-les en l'últim cas, considerant dues solucions, $(x_{1},y_{1})$ i $(x_{2},y_{2})$

$ax_{1}+by_{1}=c=ax_{2}+by_{2}$

o equivalentment

$a(x_{1}-x_{2})=b(y_{2}-y_{1})$.

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

$x=x_{1}-bt/g$

$y=y_{1}+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 (x₁, y₁). Si s'exigeix que les solucions siguin enters positius (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 incògnites que equacions; això és impossible per a un sistema d'equacions lineals quan les solucions poden ser nombres reals qualssevol.

Inversa multiplicativa i l'algorisme RSA

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 p^m. Els cossos finits s'anomenen sovint cossos de Galois, i s'abreugen com GF(p) o GF(p^m).

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

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. Cal notar que, encara que l'algorisme RSA fa servir anells més que 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.

Teorema xinès del residu

L'algorisme d'Euclides també es pot fer servir per resoldre equacions diofàntiques lineals múltiples. 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 x_i mòdul un conjunt de N nombres coprimers m_i.

x₁ ≡ x mod m₁

x₂ ≡ x mod m₂

…

x_N ≡ x mod m_N

L'objectiu és determinar x a partir dels seus N residus x_i. 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 m_i , i definir el M_i

M_i = M / m_i

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

M_ih_i ≡ 1 mod m_i

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

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

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

Fraccions Contínues

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

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

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 r₁/r₀, 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/r_k−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 q_k 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ó

Calcular un màxim comú divisor és un pas essencial en diversos algorismes de factorització dels enters, com l'algorisme rho de Pollard, l'algorisme de Shor, el mètode de factorització de Dixon i la Factorització per corba el·líptica de Lenstra. 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.

Eficiència algorísmica

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. 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, 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). Com que la despesa computacional de cada pas és també típicament d'ordre h, la despesa global creix com h².

Nombre de passos

El nombre de passos per calcular el MCD de dos nombres naturals a i b, es pot denotar per T(a, b). 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. 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à dona una altra equació

T(a, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

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

Nombre de passos en el cas pitjor

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 F_N+2 i F_N+1, respectivament. Això es pot demostrar per inducció. 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 F₂ i F₃, respectivament. Ara suposant que el resultat es compleix per a tots els valors de N fins a M − 1. El primer pas de l'algorisme de M - 1 passos és a = q₀b + r₀, i el segon pas és b = q₁r₀ + r₁. Com que l'algorisme és recursiu, exigirà M − 1 passos per trobar el MCD(b, r₀) i els seus valors més petits són F_M+1 i F_M. El valor més petit de a és per tant quan q₀ = 1, que dona a = b + r₀ = F_{M +1} + F_M = F_{M +2}. Aquesta demostració, publicada per Gabriel Lamé el 1844, representa el començament de la teoria de complexitat computacional, i també la primera aplicació pràctica dels nombres de Fibonacci.

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). El raonament és el següent: si l'algorisme exigeix N passos, llavors b és més gran que o igual a F_{N +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 log₁₀φ > 1/5, (N − 1)/5 < log₁₀φ log_φb = log₁₀b. Així N ≤ 5 log₁₀ 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

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.

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

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

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

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

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

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

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

Ja que la primera mitjana es pot calcular a partir de la mitjana de τ sumant sobre els divisors d de a.

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

es pot aproximar per la fórmula:

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

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

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

$Y(n)={\frac {1}{n^{2}}}\sum _{a=1}^{n}\sum _{b=1}^{n}T(a,b)={\frac {1}{n}}\sum _{a=1}^{n}T(a).$

Substituint la fórmula aproximada per T(a) a aquesta equació dona una estimació per Y(n).

Y(n) ≈ (12/π²) ln 2 ln n + 0,06.

Despesa computacional per pas

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

$r_{k-2}=q_{k}\ r_{k-1}+r_{k}.$

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

$r_{k}=r_{k-2}-q_{k}\ r_{k-1}.$

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

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)². 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, l'algorisme d'Euclides basat en la sostracció és competitiu amb la versió basada en la divisió. Això s'explota en la versió binària de l'algorisme d'Euclides.

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 (h²) amb el nombre mitjà de dígits h dels dos nombres inicials a i b. Sia h₀, h₁, …, h_N−1 el nombre de dígits en els successius residus r₀, r₁, …, r_N−1. Com que el nombre de passos N creix linealment amb h, el temps d'execució queda fitat per

$O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).$

Eficiència de mètodes alternatius

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. Els mètodes actuals per descomposició en factors primers són també ineficients; molts sistemes de criptografia moderns fins i tot depenen d'aquesta ineficiència.

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. 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à. L'eficiència addicional es pot assolir gràcies a examinar només els dígits principals dels dos nombres a i b. L'algorisme de Stein que treballa en base 2 es pot estendre a altres bases (algorismes base k), amb augments de velocitat de fins a un factor 5.

Un enfocament recursiu per a enters molt grans (amb més de 25.000 dígits) porta a algorismes de MCD subquadràtics, com els de Schönhage, i Stehlé i Zimmermann. 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)² (log log h)).

Altres sistemes de nombres

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

L'algorisme d'Euclides 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. 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.

L'algorisme euclidià per nombres reals difereix del seu homòleg d'enters en dos aspectes. Primer, els residus r_k són nombres reals, encara que els quocients q_k 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 $[q_{0};q_{1},q_{2},...,q_{N}]$. Si l'algorisme no s'atura, la fracció a /b és un nombre irracional i es pot descriure per una fracció contínua infinita $[q_{0};q_{1},q_{2},...]$. 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[q_{0};q_{1},q_{2},...,q_{k}]$ per obtenir una aproximació a a/b que millora a mesura que k creix. L'aproximació es descriu per m_k/n_k; els numeradors i els denominadors són coprimers i obeeixen la recurrència

$m_{k}=q_{k}\ m_{k-1}+m_{k-2}$

$n_{k}=q_{k}\ n_{k-1}+n_{k-2}$

on m₋₁ = n₋₂ = 1 i m₋₂ = n₋₁ = 0 són els valors inicials de la recurrència. La successió m_k/n_k és la millor aproximació d'un nombre racional a a/b amb el denominador n_k:

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

Polinomis

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à. El procediment bàsic és similar al cas dels enters. A cada pas k, es troben un polinomi quocient q_k(x) i un polinomi de residu r_k(x) que satisfan l'equació recursiva

$r_{k-2}(x)=q_{k}(x)\ r_{k-1}(x)+r_{k}(x)$

on r₋₂(x) = a (x) i r₋₁(x) = b (x). El polinomi de quocient s'escull de forma que el terme principal de q_k(x) r_{k −1}(x) sigui igual al terme principal de r_{k −2}(x); això assegura que el grau de cada residu sigui més petit que el grau del seu predecessor deg[r_k(x)] < deg[r_{k −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).

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

$a(x)=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)$

i

$b(x)=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2)$.

Dividint a(x) entre b(x) dona una residu r₀(x) = x³ + (2/3)x² + (5/3)x − (2/3). Al següent pas b(x) es divideix entre r₀(x) donant un residu r₁(x) = x² + x + 2. Finalment, dividint r₀(x) entre r₁(x) dona un zero de residu, el que indica que r₁(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. 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.

Exemple d'aplicació a trobar arrels múltiples

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

Com que 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. Això no suposa cap pèrdua de generalitat, ja que 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 addicionalment $P'=3(X-7)(X+3)\quad$

Enters de Gauss

Distribució de nombres primers de Gauss u + vi al pla complex, amb normes u² + v² 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. Definint un anàleg de l'algorisme euclidià, es pot demostrar que els enters gaussians són factoritzables de forma única, per la Identitat de Bézout. 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. 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 q_k i una residu r_k tals que

$r_{k}=r_{k-2}-q_{k}\ r_{k-1}$

on r_{k −2} = α, r_{k −1} = β, i tots els residus són estrictament més petits que els seus predecessors, |r_k| < |r_{k −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 q_k 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) = u² + v², 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 (r_k) és més petita que la norma del residu anterior, f(r_{k −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 d'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

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. 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'ordre 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 cert: 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. 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. l'aproximació de Lamé exigia la factorització única de nombres de la forma x + ωy, on x i y són enters, i ω = e^{2i π/n} és una n arrel d'1, és a dir ωⁿ = 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.

Factorització única d'enters quadràtics

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 què 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 l'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. 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. El primer exemple d'un anell euclidià que no era de norma euclidiana (amb D =69) era publicat el 1994. 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.

Anells no commutatius

També és possible aplicar l'algorisme euclidià a anells no commutatius com el conjunt de quaternions de Hurwitz. Siguin α i β dos elements de tal anell. Tenen un comú bé divisor δ si α = ξδ i β = ηδ per a alguna elecció de ξ i η a l'anell. De manera 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

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

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

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

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 ρ₀ ha de ser estrictament més petita que β, i hi ha d'haver només un nombre finit de mides possibles per a ρ₀, 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 MCD(α, β) 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

L'algorisme euclidià es pot aplicar en la teoria de nusos.

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

$r_{k}=r_{k-2}-q_{k}\ r_{k-1}$

on cada residu és estrictament més petit que el seu predecessor, |r_k| < |r_{k −1}|. Segon, la mida de cada residu té un límit inferior estricte, com |r_k| ≥ 0. Tercer, hi ha només un nombre finit de mides més petites que un residu donat |r_k|. Les generalitzacions de l'algorisme d'Euclides amb aquests trets bàsics s'han aplicat a altres estructures matemàtiques, com nusos i a nombres ordinals transfinits.

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 amunt, 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 cert per a anells de més d'una variable. En aquest cas, es pot definir un conjunt finit de polinomis generadors g₁, g₂, etc. tal que qualsevol combinació lineal de dos polinomis multivariables a i b pot ser expressat com múltiples dels generadors

$sa+tb=\Sigma _{k}\ m_{k}\ g_{k}$

on s, t i m_k són polinomis multivariables. 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+\Sigma _{k}\ q_{k}\ g_{k}$

encara que els polinomis quocient q_k poden no ser únics. El conjunt d'aquests polinomis generadors es coneix com a base de Gröbner.

Notes

• a. ^{^} Alguns llibres de text àmpliament utilitzats, com I. N. Herstein Topics in Algebra i Serge Lang Algebra, fan servir el terme "Algorisme euclidià" per referir-se a la algorisme de divisió amb residu. Tanmateix, l'algorisme de divisió és un teorema, no un algorisme.

Bibliografia

• Cohen H.. A Course in Computational Algebraic Number Theory. Nova York: Springer-Verlag, 1993. ISBN 0-387-55640-0. 
• Cohn H. Advanced Number Theory. Nova York: Dover, 1962. ISBN 0-486-64023-X. 
• Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 2a ed.. MIT Press and McGraw–Hill, 2001. ISBN 0262032937. 
• Cox D, Little J, and O'Shea D. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. 2a ed.. Springer-Verlag, 1997. ISBN 0-387-94680-2. 
• Dirichlet PGL. Richard Dedekind. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg, 1894. 
• Hardy GH, Wright EM [revised by D.R. Heath-Brown and J.H. Silverman].. An Introduction to the Theory of Numbers. 6a ed.. Oxford: Clarendon Press, 2008. 
• Knuth D. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3a ed.. Addison–Wesley, 1997. ISBN 0201896842. 
• LeVeque WJ. Fundamentals of Number Theory. Nova York: Dover, 1977. ISBN 0-486-68906-9. 
• Mollin RA. Fundamental Number Theory with Applications. 2a ed.. Boca Raton: Chapman & Hall/CRC, 2008. ISBN 9781420066593. 
• Ore Ø. Number Theory and Its History. Nova York: McGraw–Hill, 1948. 
• Rosen KH. Elementary Number Theory and its Applications. 4a ed.. Reading, Ma: Addison–Wesley, 2000. ISBN 0201870738. 
• Schroeder MR. Number Theory in Science and Communication. 4a ed.. Springer-Verlag, 2005. ISBN 0387158006. 
• Shallit, Jeffrey «Origins of the analysis of the Euclidean algorithm». Historia Mathematica, Vol 21, Num 4, 1994, pàg. 401-419. DOI: 10.1006/hmat.1994.1031. ISSN: 0315-0860.
• Stark H. An Introduction to Number Theory. MIT Press, 1978. ISBN 0-262-69060-8. 
• Stillwell J. Numbers and Geometry. d'editor localització = Nova York: Springer-Verlag, 1997. ISBN 0-387-98289-2. 
• Tattersall JJ. Elementary number theory in nine chapters. Cambridge: Cambridge University Press, 2005. ISBN 9780521850148. 
• Uspensky JV, Heaslet MA. Elementary Number Theory. Nova York: McGraw–Hill, 1939. 

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Algorisme d'Euclides

• Demostracions de l'algorisme d'Euclides. David Sumner
• l'Algorisme d'Euclides a cut-the-knot
• l'Algorisme d'Euclides a Planet Math (anglès)
• L'Algorisme euclidià a MathPages
• el Joc d'Euclides a cut-the-knot
• Música i l'algorisme d'Euclides. Plus Magazine (anglès)
• Weisstein, Eric W., «Euclidean Algorithm» a MathWorld (en anglès).