Lalgorisme d'Euclides é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 que el va descriure en els volums VII i X del llibre Elements., Thomas Little, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

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 més petit dels divisors comuns és el mateix, i repetint l'operació:

mcd (b, r1) = mcd (r1, r₂) = mcd (r₂, r₃) = ... = mcd (rn-1, rn) = mcd (rn-1, 0) = rn-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 existeix.

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 gros 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),Stark, pàg. 16. 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.Stark, pàg. 21. Aquesta propietat és independent de si a i b són ells mateixos nombres primers.LeVeque, pàg. 32. 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ú.

miniatura|alt="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 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.Leveque, pàg. 31.

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.Schroeder, pàg. 21-22. 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.Schroeder, pàg. 19.. La factorització d'enters grans es creu que és un problema tan difícil que s'hi basen molts sistemes de criptografia moderns.Schroeder, pàg. 216-219.

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,Stark, pàg. 25. que es pot calcular prenent el MCD de cada parella de nombres.Oregon, pàg. 47-48. Per exemple

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ó (Secció 1.2.1: Inducció matemàtica, pàg. 11-21.) sovint es fa servir per demostrar un teorema per a tots els nombres naturals n.Rosen, pàg. 18-21. 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ènciaRosen, pàg. 21-24. és una equació que relaciona nombres que formen una sèrie a1, a₂, a₃, etc. El terme n-èsim 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,Rosen, pàg. 492. 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.Stark, pàg. 16-20. 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 rk−1 i rk−2. Com que l'algorisme assegura que els residus disminueixen constantment a tots els passos rk−1 és menor que el seu predecessor rk−2. L'objectiu del k-èsim pas és trobar un quocient qk i un residu rk tals que satisfan l'equació

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

…

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.

Com 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.Stark, pàg. 18. 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 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 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 impliquen que rN −1 = g.

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

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

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

com es volia veure.

Exemple miniatura|alt=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.