Un algoritmo più veloce, è basato su divisioni successive.

Euclide descrisse questo algoritmo nel suo libro degli Elementi. Invece di usare i numeri interi, però, utilizzò i segmenti di retta. Perciò il suo algoritmo serve anche a determinare il massimo comune divisore di due segmenti. In certi casi l'algoritmo può richiedere numerosissimi passaggi, risultando molto lento (provate con MCD (900,15)). Conviene quindi renderlo più veloce e si può fare ricorrendo ad una serie di divisioni con resto anziché sottrazioni. Il principio su cui ci si basa è il seguente (supponiamo m>n):

MCD(m,n) = MCD(r,n)dove r è il resto della divisione m/n

Come si vede, questa regola permette di passare rapidamente, per mezzo di divisioni con resto successive, a MCD di numeri sempre più piccoli, fino ad ottenere:

MCD(r,0)=r

Questo algoritmo è molto più veloce del primo. La traccia dei calcoli vi farà capire come funziona. Più sotto troverete la spiegazione dettagliata

(se non si ha sufficiente dimestichezza con certi calcoli si può ometterla).

Spiegazione del teorema

Prendiamo a,b interi con a,b>0 e supponiamo 0<a<b.

Dividiamo b per a, avremo che:

b = q₁´a+r₁, con 0 <r₁<a.

Osserviamo che:

i) se r₁=0, allora b = q₁´a e abbiamo già che MCD(a,b)=a;

ii) altrimenti, preso un intero positivo d

1) se d divide sia a che b, allora dividerà anche r₁ in quanto combinazione lineare di a e b;

2) viceversa, se d divide a e r₁, dividerà anche b per la stessa proprietà sopra.

Quindi possiamo concludere che

MCD(a,b) = MCD(a,r₁),

con il vantaggio che r₁<a<b.

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r₁ con r₁<a:

a = q₂´r₁+r₂, con 0 <r₂<r₁

dove

i) se r₂=0, si ha che r₂|a, quindi MCD(a,b) = MCD(a,r₁) = r₂;

ii) altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a,b)=MCD(a,r₁)=MCD(r₁,r₂).

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i-esima iterazione dove

r_i-1 = q_i+1´r_i+r_i+1, con 0 £ r_i+1<r_i

e avremo che

i) se r_i=0, allora MCD(a,b) = r_i-1;

ii) altrimenti, continuiamo il procedimento.

Poiché gli r_i sono interi non negativi e la successione di resti è decrescente, ad un certo punto ci dovremo fermare, cioè esisterà un r_n diverso da zero tale che r_n+1=0, allora il nostro MCD(a,b) sarà uguale all’ultimo resto diverso da zero della catena di divisioni.

Questo procedimento è vantaggioso perché non dobbiamo scomporre in fattori primi e si utilizzano divisioni sempre più facili.

Proviamo ora a ricostruire s,t procedendo a ritroso nell’algoritmo euclideo:

presi MCD(a,b) = r_n e sa+tb = r_n, possiamo scrivere

r_n = r_n-2 - q_n´r_n-1,

e andiamo a sostituire il valore di r_n-1 che si ricava dall’uguaglianza r_n-3 = q_n-1´r_n-2 + r_n-1:

r_n = r_n-2 - q_n´ (r_n-3 - q_n-1´r_n-2) = (1+q_nq_n-1) r_n-2 - q_n´ r_n-3.

Ora sostituiamo in questa equazione il valore di r_n-2 che si ottiene da r_n-4 = q_n-2´r_n-3 + r_n-2 e avremo r_n come espressione in r_n-3 e r_n-4, quindi andremo a sostituire r_n-3 e continueremo questo procedimento fino ad ottenere r_n come combinazione lineare dei soli a e b.