Algoritmo di Euclide per il calcolo del massimo comun divisore (MCD)

L'algoritmo di Euclide si basa sul seguente teorema:

Dati due numeri naturali a e b, entrambi maggiori di 1 con a > b:

se b è un divisore esatto di a, b è ovviamente il massimo comun divisore tra i due numeri;
altrimenti, detto r il resto della divisione tra a e b, il MCD tra a e b è uguale al MCD tra b e r.

Dimostrazione

Se a è maggiore di b e non è multiplo di b, detto d il MCD(a,b), si ha

dove q_ad e q_bd indicano rispettivamente i quozienti delle divisioni di a per d e b per d.

Indicando con q_ab il quoziente della divisione di a per b e con r il resto della stessa divisione (r < b) si ha

Sostituendo nella (2) i valori (1) di a e b si ha

cioè d è anche divisore di r.

Quindi

fintanto che r > 0 si può quindi sostituire il calcolo di MCD(a,b) con il calcolo di MCD(b,r);
quando il resto risulta 0, allora MCD(a,b) coincide con l'ultimo resto precedentemente trovato.

Il minimo comune multiplo (mcm)

Detti d il MCD e m il mcm di due numeri a e b si ha che

Dimostrazione

è un multiplo di a
è un multiplo di b
dunque è un multiplo comune di a e b e, ovviamente, sarà maggiore o, al minimo, uguale a m: ; quindi
è un divisore di a. Infatti
è un divisore di b. Infatti
Dunque è un divisore comune di a e b e, ovviamente, sarà minore o, al massimo, uguale a d: e quindi
La validità contemporanea della (5) e della (6) implica

Dalla (7) segue immediatamente

quindi, per calcolare il mcm di due numeri si divide il loro prodotto per il loro MCD.

Implementazione Javascript