L'algoritmo originale di Euclide, basato su sottrazioni successive
L'algoritmo per il calcolo del MCD di due numeri interi positivi, nella sua versione più semplice, si basa sulla seguente proprietà: Se due numeri, m, n, sono divisibili per un terzo numero, x, allora anche la loro differenza è divisibile per x.
Per dimostrarla, si può utilizzare la proprietà distributiva. Supponiamo m>n.
m=kx
n=hx
m-n=kx-hx=x(k-h)
Dunque si può dire che:
MCD(m,n) = MCD((m-n),n)
Come si vede, questa regola permette di passare, per mezzo di sottrazioni successive, al MCD di numeri sempre più piccoli, fino ad ottenere: MCD(a,0)=a
Calcoliamo, ad esempio, il MCD tra 6 e 15. Si avrà:
15 - 6 = 9
9 - 6= 3
6 - 3 = 3
3 - 3 = 0
Quindi MCD (6, 15) = 3
--> Clicca per sperimentare l'algoritmo delle sottrazioni successive
Utilizzalo più volte con diverse coppie di numeri. La traccia dei calcoli ti farà capire come funziona.
Un algoritmo più veloce, basato su divisioni successive
In certi casi l'algoritmo basato sulle sottrazioni succesive può richiedere numerosissimi passaggi, risultando molto lento. Provate, ad esempio 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
--> Prova ora l'algoritmo delle divisioni successive
E' molto più veloce del primo!! La traccia dei calcoli ti farà capire come funziona.