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.^[1]

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

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

Això permet detallar l'algorisme efectiu:

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.