b"\n_START_ARTICLE_\nAlgorisme d'Euclides\n_START_SECTION_\nInducci\xc3\xb3, recursivitat i descens infinit\n_START_PARAGRAPH_\nTres m\xc3\xa8todes matem\xc3\xa0tics relacionats s'utilitzen en els arguments seg\xc3\xbcents: inducci\xc3\xb3, recursivitat i descent infinit. La inducci\xc3\xb3 sovint es fa servir per demostrar un teorema per a tots els nombres naturals n. Aquest enfocament comen\xc3\xa7a demostrant que, si el teorema es compleix per n, tamb\xc3\xa9 es compleix per n + 1. Per aix\xc3\xb2, si el teorema es compleix per a un cas (t\xc3\xadpicament n = 1), es compleix per a tots els casos m\xc3\xa9s alts (n = 2, 3, etc.). Una recurr\xc3\xa8ncia \xc3\xa9s una equaci\xc3\xb3 que relaciona nombres que formen una s\xc3\xa8rie a\xe2\x82\x81, a\xe2\x82\x82, a\xe2\x82\x83, etc. El terme n-\xc3\xa8sim de la s\xc3\xa8rie, a\xe2\x82\x99, sovint s'expressa en funci\xc3\xb3 de termes anteriors de la s\xc3\xa8rie, com a\xe2\x82\x99 \xe2\x88\x921. Per exemple, els nombres de Fibonacci es defineixen recursivament; cada terme \xc3\xa9s la suma dels dos termes anteriors: F\xe2\x82\x99 = F\xe2\x82\x99 \xe2\x88\x921 + F\xe2\x82\x99 \xe2\x88\x922. Unes quantes equacions associades amb l'algorisme euclidi\xc3\xa0 s\xc3\xb3n recursives. Finalment, en el descens infinit, una soluci\xc3\xb3 donada en nombres naturals \xc3\xa9s utilitzada per construir una soluci\xc3\xb3 amb nombres naturals m\xc3\xa9s petits. Tanmateix, les solucions no es poden encongir indefinidament, ja que nom\xc3\xa9s hi ha un nombre finit de nombres naturals m\xc3\xa9s petits que qualsevol nombre natural. Per aix\xc3\xb2, la soluci\xc3\xb3 original era impossible, o la construcci\xc3\xb3 de solucions m\xc3\xa9s petites ha d'acabar. L'\xc3\xbaltim argument s'utilitza per demostrar que l'algorisme euclidi\xc3\xa0 per a nombres naturals ha d'acabar en un nombre finit de passos.\n_START_SECTION_\nVisualitzaci\xc3\xb3\n_START_PARAGRAPH_\nL'algorisme d'Euclides es pot visualitzar en termes de l'analogia d'enrajolar donada abans per al m\xc3\xa0xim com\xc3\xba divisor. Suposant que es vol cobrir completament un rectangle de a-per-b amb rajoles quadrades, on a \xc3\xa9s el m\xc3\xa9s gran dels dos nombres. Primer s'intenta enrajolar el rectangle fent servir rajoles quadrades de b-per-b; tanmateix, aix\xc3\xb2 deixa un rectangle residual r\xe2\x82\x80-per-b sense nenrajolar, on r\xe2\x82\x80<b. Llavors s'intenta enrajolar el rectangle residual amb rajoles quadrades de r\xe2\x82\x80-per-r\xe2\x82\x80. Aix\xc3\xb2 deixa un segon rectangle residual r\xe2\x82\x81-per-r\xe2\x82\x80, que s'intenta enrajolar emprant rajoles quadrades de r\xe2\x82\x81-per-r\xe2\x82\x81, etc\xc3\xa8tera. La seq\xc3\xbc\xc3\xa8ncia acaba quan no hi ha cap rectangle residual, \xc3\xa9s a dir, quan les rajoles quadrades cobreixen el rectangle residual previ exactament. La llargada dels costats de la rajola quadrada m\xc3\xa9s petita \xc3\xa9s el MCD de les dimensions del rectangle original. Per exemple, la rajola quadrada m\xc3\xa9s petita en la figura adjacent \xc3\xa9s 21-per-21 (es mostra en vermell), i 21 \xc3\xa9s el MCD de 1071 i 462, les dimensions del rectangle original (que es mostra en verd).\n_START_SECTION_\nImplementacions\n_START_PARAGRAPH_\nLes aplicacions de l'algorisme es poden expressar en el pseudocodi. Per exemple, la versi\xc3\xb3 basada en la divisi\xc3\xb3 es pot programar com._NEWLINE_funci\xc3\xb3 mcd(a, b)_NEWLINE_  mentre b \xe2\x89\xa0 0_NEWLINE_    t\xc2\xa0:= b_NEWLINE_    b\xc2\xa0:= a mod b_NEWLINE_    a\xc2\xa0:= t_NEWLINE_retorna a_NEWLINE_Al comen\xc3\xa7ament de la iteraci\xc3\xb3 k-\xc3\xa8sima, la variable b cont\xc3\xa9 l'\xc3\xbaltim residu r\xe2\x82\x96\xe2\x88\x921, mentre que la variable a cont\xc3\xa9 el seu predecessor, r\xe2\x82\x96\xe2\x88\x922. El pas b\xc2\xa0:= a mod b \xc3\xa9s equivalent a la f\xc3\xb3rmula de recurr\xc3\xa8ncia citada r\xe2\x82\x96 \xe2\x89\xa1 r\xe2\x82\x96 \xe2\x88\x922 mod r\xe2\x82\x96 \xe2\x88\x921. La variable auxiliar t cont\xc3\xa9 el valor de r\xe2\x82\x96\xe2\x88\x921 mentre el proper residu r\xe2\x82\x96  est\xc3\xa0 sent calculat. Al final de la iteraci\xc3\xb3 del bucle, la variable b cont\xc3\xa9 el residu r\xe2\x82\x96, mentre que la variable a cont\xc3\xa9 el seu predecessor, r\xe2\x82\x96 \xe2\x88\x921._NEWLINE_En la versi\xc3\xb3 basada en la sostracci\xc3\xb3 definida per Euclides, el c\xc3\xa0lcul del residu (b = a mod  b) \xc3\xa9s reempla\xc3\xa7at per una sostracci\xc3\xb3 repetida._NEWLINE_funci\xc3\xb3 mcd(a, b)_NEWLINE_  si a = 0_NEWLINE_    retorna b_NEWLINE_  mentre b \xe2\x89\xa0 0_NEWLINE_    si a > b_NEWLINE_      a\xc2\xa0:= a \xe2\x88\x92 b_NEWLINE_    altrament_NEWLINE_      b\xc2\xa0:= b \xe2\x88\x92 a_NEWLINE_  retorna a_NEWLINE_Les variables a i b contenen alternativament els residus previs r\xe2\x82\x96 \xe2\x88\x921 i r\xe2\x82\x96 \xe2\x88\x922. Suposant que a \xc3\xa9s m\xc3\xa9s gran que b al comen\xc3\xa7ament d'una iteraci\xc3\xb3; llavors a \xc3\xa9s igual a r\xe2\x82\x96 \xe2\x88\x922, com que r\xe2\x82\x96 \xe2\x88\x922 > r\xe2\x82\x96 \xe2\x88\x921. Durant la iteraci\xc3\xb3 del bucle a es redueix per m\xc3\xbaltiples restes de b fins que a \xc3\xa9s m\xc3\xa9s petit que b. Llavors a \xc3\xa9s el pr\xc3\xb2xim residu r\xe2\x82\x96. Llavors b es redueix per m\xc3\xbaltiples restes de a fins que sigui una altra vegada m\xc3\xa9s petit que a, donant el pr\xc3\xb2xim residu r\xe2\x82\x96 \xe2\x82\x8a\xe2\x82\x81, etc\xc3\xa8tera._NEWLINE_La versi\xc3\xb3 recursiva es basa en la igualtat de MCDs dels successius residus i la condici\xc3\xb3 d'aturada MCD( rN \xe2\x88\x921, 0) = rN \xe2\x88\x921._NEWLINE_funci\xc3\xb3 mcd(a, b)_NEWLINE_  si b = 0_NEWLINE_    retorna a_NEWLINE_  altrament_NEWLINE_    retorna mcd(b, a mod b)_NEWLINE_Per il\xc2\xb7lustrar-ho, el MCD(1071, 462) es calcula a partir de l'equivalent MCD(462, 1071 mod 462) = MCD(462, 147). Aquest \xc3\xbaltim 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.\n_START_SECTION_\nAlgorismes de factoritzaci\xc3\xb3\n_START_PARAGRAPH_\nCalcular un m\xc3\xa0xim com\xc3\xba divisor \xc3\xa9s un pas essencial en diversos algorismes de factoritzaci\xc3\xb3 dels enters, com l'algorisme rho de Pollard, l'algorisme de Shor, el m\xc3\xa8tode de factoritzaci\xc3\xb3 de Dixon i la Factoritzaci\xc3\xb3 per corba el\xc2\xb7l\xc3\xadptica de Lenstra. L'algorisme euclidi\xc3\xa0 es pot utilitzar per trobar aquest MCD eficientment. La factoritzaci\xc3\xb3 de fracci\xc3\xb3 cont\xc3\xadnua fa servir fraccions cont\xc3\xadnues, que es determinen emprant l'algorisme d'Euclides.\n_START_SECTION_\nEfici\xc3\xa8ncia algor\xc3\xadsmica\n_START_PARAGRAPH_\nL'efici\xc3\xa8ncia computacional de l'algorisme d'Euclides s'ha estudiat minuciosament. Aquesta efici\xc3\xa8ncia 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\xc3\xa9 el 1844, el nombre de passos requerits per a l'acabament no \xc3\xa9s mai m\xc3\xa9s gran que cinc vegades el nombre h de d\xc3\xadgits (base 10) del nombre b (el m\xc3\xa9s petit). Com que la despesa computacional de cada pas \xc3\xa9s tamb\xc3\xa9 t\xc3\xadpicament d'ordre h, la despesa global creix com h\xc2\xb2.\n_START_SECTION_\nNombre de passos en el cas pitjor\n_START_PARAGRAPH_\nSi l'algorisme euclidi\xc3\xa0 exigeix N passos per a un parell de nombres naturals a > b > 0, els valors m\xc3\xa9s petits de a i b per als quals aix\xc3\xb2 \xc3\xa9s cert s\xc3\xb3n els nombres de Fibonacci FN\xe2\x82\x8a\xe2\x82\x82 i FN\xe2\x82\x8a\xe2\x82\x81, respectivament. Aix\xc3\xb2 es pot demostrar per inducci\xc3\xb3. Si N = 1, b divideix a sense residu; els nombres naturals m\xc3\xa9s petits per als quals aix\xc3\xb2 es compleix s\xc3\xb3n b = 1 i a = 2, que \xc3\xa9s F\xe2\x82\x82 i F\xe2\x82\x83, respectivament. Ara suposant que el resultat es compleix per a tots els valors de N fins a M \xe2\x88\x92 1. El primer pas de l'algorisme de M - 1 passos \xc3\xa9s a = q\xe2\x82\x80b + r\xe2\x82\x80, i el segon pas \xc3\xa9s b = q\xe2\x82\x81r\xe2\x82\x80 + r\xe2\x82\x81. Com que l'algorisme \xc3\xa9s recursiu, exigir\xc3\xa0 M \xe2\x88\x92 1 passos per trobar el MCD(b, r\xe2\x82\x80) i els seus valors m\xc3\xa9s petits s\xc3\xb3n FM\xe2\x82\x8a\xe2\x82\x81 i FM. El valor m\xc3\xa9s petit de a \xc3\xa9s per tant quan q\xe2\x82\x80 = 1, que d\xc3\xb3na a = b + r\xe2\x82\x80 = FM \xe2\x82\x8a\xe2\x82\x81 + FM = FM \xe2\x82\x8a\xe2\x82\x82. Aquesta demostraci\xc3\xb3, publicada per Gabriel Lam\xc3\xa9 el 1844, representa el comen\xc3\xa7ament de la teoria de complexitat computacional, i tamb\xc3\xa9 la primera aplicaci\xc3\xb3 pr\xc3\xa0ctica dels nombres de Fibonacci._NEWLINE_Aquest resultat \xc3\xa9s suficient per mostrar que el nombre de passos en l'algorisme d'Euclides mai no pot ser m\xc3\xa9s que cinc vegades el nombre dels seus d\xc3\xadgits (base 10). El raonament \xc3\xa9s el seg\xc3\xbcent: si l'algorisme exigeix N passos, llavors b \xc3\xa9s m\xc3\xa9s gran que o igual a FN \xe2\x82\x8a\xe2\x82\x81 que a canvi \xc3\xa9s m\xc3\xa9s gran que o igual a \xcf\x86\xe1\xb4\xba \xe2\x81\xbb\xc2\xb9, on \xcf\x86 \xc3\xa9s la proporci\xc3\xb3 \xc3\xa0uria. Com que b \xe2\x89\xa5 \xcf\x86\xe1\xb4\xba \xe2\x81\xbb\xc2\xb9, llavors N \xe2\x88\x92 1 \xe2\x89\xa4 log\xcf\x86b. Com que log\xe2\x82\x81\xe2\x82\x80\xcf\x86 > 1/5, (N \xe2\x88\x92 1)/5 < log\xe2\x82\x81\xe2\x82\x80\xcf\x86 log\xcf\x86b = log\xe2\x82\x81\xe2\x82\x80b. Aix\xc3\xad N \xe2\x89\xa4 5 log\xe2\x82\x81\xe2\x82\x80 b. Per tant, l'algorisme euclidi\xc3\xa0 sempre necessita menys que O(h) divisions, on h \xc3\xa9s el nombre de d\xc3\xadgits del nombre m\xc3\xa9s petit b.\n_START_SECTION_\nEfici\xc3\xa8ncia de m\xc3\xa8todes alternatius\n_START_PARAGRAPH_\nL'algorisme d'Euclides es fa servir a bastament en la pr\xc3\xa0ctica, especialment per a nombres petits, a causa de la seva simplicitat. Per comparaci\xc3\xb3, es pot determinar l'efici\xc3\xa8ncia d'alternatives a l'algorisme d'Euclides._NEWLINE_Una aproximaci\xc3\xb3 inefica\xc3\xa7 per trobar el MCD de dos nombres naturals a i b \xc3\xa9s trobar tots els seus divisors comuns; el MCD \xc3\xa9s llavors el com\xc3\xba divisor m\xc3\xa9s gran. Els divisors comuns es poden trobar dividint els dos nombres per enters successius des de 2 fins al nombre m\xc3\xa9s petit b. El nombre de passos d'aquest enfocament augmenta linealment amb b, o exponencialment en el nombre de d\xc3\xadgits. Una altra aproximaci\xc3\xb3 inefica\xc3\xa7 \xc3\xa9s trobar els factors primers d'un o els dos nombres. Com s'ha comentat m\xc3\xa9s amunt, el MCD \xc3\xa9s igual al producte dels factors primers compartits pels dos nombres a i b. Els m\xc3\xa8todes actuals per descomposici\xc3\xb3 en factors primers s\xc3\xb3n tamb\xc3\xa9 ineficients; molts sistemes de criptografia moderns fins i tot depenen d'aquesta inefici\xc3\xa8ncia._NEWLINE_L'algorisme de Stein \xc3\xa9s una alternativa eficient que substitueix la divisi\xc3\xb3 per operacions m\xc3\xa9s r\xc3\xa0pides explotant la representaci\xc3\xb3 bin\xc3\xa0ria emprada pels ordinadors. Tanmateix, aquesta alternativa tamb\xc3\xa9 \xc3\xa9s O(H\xc2\xb2). \xc3\x89s generalment m\xc3\xa9s r\xc3\xa0pid en ordinadors reals, per\xc3\xb2 l'ordre de magnitud \xc3\xa9s el mateix que a l'algorisme euclidi\xc3\xa0. L'efici\xc3\xa8ncia addicional es pot assolir gr\xc3\xa0cies a examinar nom\xc3\xa9s els d\xc3\xadgits 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._NEWLINE_Un enfocament recursiu per a enters molt grans (amb m\xc3\xa9s de 25.000 d\xc3\xadgits) porta a algorismes de MCD subquadr\xc3\xa0tics, com els de Sch\xc3\xb6nhage, i Stehl\xc3\xa9 i Zimmermann. Aquests algorismes exploten la forma de matriu de 2\xc3\x972 de l'algorisme euclidi\xc3\xa0 donat m\xc3\xa9s amunt. Aquests m\xc3\xa8todes subquadr\xc3\xa0tics generalment tenen una complexitat de O(h (log h)\xc2\xb2 (log log h)).\n_START_SECTION_\nAltres sistemes de nombres\n_START_PARAGRAPH_\nCom descrit a dalt, l'algorisme euclidi\xc3\xa0 s'utilitza per trobar el m\xc3\xa0xim com\xc3\xba divisor de dos nombres naturals (enters positius). Tanmateix, es pot generalitzar als nombres reals, i a m\xc3\xa9s sistemes de nombre ex\xc3\xb2tics com polinomis, enters quadr\xc3\xa0tics i quaternions de Hurwitz. En els \xc3\xbaltims casos, l'algorisme euclidi\xc3\xa0 s'utilitza per demostrar la propietat fonamental que la factoritzaci\xc3\xb3 \xc3\xa9s \xc3\xbanica, \xc3\xa9s a dir, que tals nombres es poden factoritzar de forma \xc3\xbanica en elements irreductibles, els hom\xc3\xb2legs dels nombres primers. La factoritzaci\xc3\xb3 \xc3\xbanica \xc3\xa9s essencial per moltes demostracions de teoria de nombres.\n_START_SECTION_\nExemple d'aplicaci\xc3\xb3 a trobar arrels m\xc3\xbaltiples\n_START_PARAGRAPH_\nSiga  un polinomi que t\xc3\xa9 una arrel doble._NEWLINE_Com que resoldre una equaci\xc3\xb3 de tercer grau no \xc3\xa9s evident, per a trobar l'arrel m\xc3\xbaltiple emprem la propietat que diu les arrels m\xc3\xbaltiples s\xc3\xb3n les comunes entre el polinomi i el seu polinomi derivat._NEWLINE_Per a simplificar les divisions, ens permetem multiplicar-los per factors constants no nuls. Aix\xc3\xb2 no suposa cap p\xc3\xa8rdua de generalitat, ja que el mcd de dos polinomis est\xc3\xa0 definit m\xc3\xb2dul un factor multiplicador, de manera que esta manipulaci\xc3\xb3 no altera el resultat._NEWLINE_El polinomi derivat de P \xc3\xa9s  que es pot simplificar per 3, segons el que s'ha dit anteriorment. _NEWLINE_Prenguem llavors  i efectuem l'algorisme amb P i Q._NEWLINE_. La resta es factoritza en : prenguem llavors _NEWLINE_ el que implica que el mcd buscat \xc3\xa9s  llavors 7 \xc3\xa9s l'arrel doble de P._NEWLINE_En efecte:  i addicionalment\n_START_SECTION_\nDominis euclidians\n_START_PARAGRAPH_\nUn conjunt d'elements amb dues operacions bin\xc3\xa0ries, + i \xc2\xb7, s'anomenen un anell euclidi\xc3\xa0 si forma un anell commutatiu R i, a grans trets, si s'hi pot aplicar un algorisme euclidi\xc3\xa0 generalitzat. Les dues operacions de tal anell no necessiten ser l'addici\xc3\xb3 i multiplicaci\xc3\xb3 de l'aritm\xc3\xa8tica corrent; poden ser, m\xc3\xa9s aviat, m\xc3\xa9s generals, com les operacions d'un grup matem\xc3\xa0tic o monoide. No obstant aix\xc3\xb2, aquestes operacions generals han de respectar moltes de les lleis que governen l'aritm\xc3\xa8tica corrent, com la propietat commutativa, la propietat associativa i la propietat distributiva._NEWLINE_L'algorisme euclidi\xc3\xa0 generalitzat requereix una funci\xc3\xb3 euclidiana, \xc3\xa9s a dir, una funci\xc3\xb3 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\xc3\xb3 \xc3\xa9s la funci\xc3\xb3 norma utilitzada amb els entersde Gauss a la secci\xc3\xb3 anterior. La funci\xc3\xb3 f pot ser la magnitud del nombre, o el grau d'un polinomi. El principi b\xc3\xa0sic \xc3\xa9s que es redueix a cada pas de l'algorisme; per aix\xc3\xb2, si f es pot reduir nom\xc3\xa9s un nombre finit de vegades, l'algorisme s'ha d'aturar en un nombre finit de passos. Aquest principi dep\xc3\xa8n fortament de l'ordre natural dels enters no negatius; a grans trets, aix\xc3\xb2 exigeix que tots els conjunts d'enters no negatius tinguin un membre m\xc3\xa9s petit que tots els altres._NEWLINE_El teorema fonamental de l'aritm\xc3\xa8tica s'aplica a qualsevol anell euclidi\xc3\xa0: Qualsevol nombre d'un anell euclidi\xc3\xa0 es pot factoritzar de manera \xc3\xbanica amb elements irreductibles. Qualsevol anell euclidi\xc3\xa0 \xc3\xa9s un domini de factoritzaci\xc3\xb3 \xc3\xbanica (UFD), encara que el contrari no \xc3\xa9s cert. Els anells euclidians s\xc3\xb3n una subclasse dels anells de MCD, anells en els quals sempre existeix un m\xc3\xa0xim com\xc3\xba divisor de dos nombres. En altres paraules, un m\xc3\xa0xim com\xc3\xba divisor pot existir (per a tots els elements en un anell), encara que pot no ser possible trobar-lo utilitzant un algorisme euclidi\xc3\xa0. Un anell euclidi\xc3\xa0 \xc3\xa9s sempre un anell d'ideals principals, un anell \xc3\xadntegre en el qual tots els ideals s\xc3\xb3n un ideal principal. Una altra vegada, el contrari no \xc3\xa9s cert: no tots els anells ideal principal s\xc3\xb3n un anell euclidi\xc3\xa0._NEWLINE_La factoritzaci\xc3\xb3 \xc3\xbanica d'anells euclidians \xc3\xa9s \xc3\xbatil en moltes aplicacions. Per exemple, la factoritzaci\xc3\xb3 \xc3\xbanica dels enters gaussians \xc3\xa9s convenient permetent obtenir f\xc3\xb3rmules per totes les ternes pitag\xc3\xb2riques i demostrar el teorema de la suma de dos quadrats. La factoritzaci\xc3\xb3 \xc3\xbanica era tamb\xc3\xa9 un element clau en un intent de demostraci\xc3\xb3 del darrer teorema de Fermat publicat el 1847 per Gabriel Lam\xc3\xa9, el mateix matem\xc3\xa0tic que analitzava l'efici\xc3\xa8ncia de l'algorisme d'Euclides, basat en un suggeriment de Joseph Liouville. l'aproximaci\xc3\xb3 de Lam\xc3\xa9 exigia la factoritzaci\xc3\xb3 \xc3\xbanica de nombres de la forma x + \xcf\x89y, on x i y s\xc3\xb3n enters, i \xcf\x89 = e\xc2\xb2\xe2\x81\xb1 \xcf\x80/\xe2\x81\xbf \xc3\xa9s una n arrel d'1, \xc3\xa9s a dir \xcf\x89\xe2\x81\xbf = 1. Encara que aquesta aproximaci\xc3\xb3 t\xc3\xa9 \xc3\xa8xit per a alguns valors de n (com n =3, els Enters d'Eisenstein), en general tals nombres no es factoritzen \xc3\xbanicament. Aquest frac\xc3\xa0s de factoritzaci\xc3\xb3 \xc3\xbanica en alguns anells ciclot\xc3\xb2mics portava Ernst Kummer al concepte de nombres ideals i, m\xc3\xa9s tard, a Richard Dedekind al d'ideals."