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

(R. Bigoni)


English version


L'algoritmo di Euclide si basa sul seguente teorema:

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

Dimostrazione

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

Eqn002.gif

dove qad e qbd indicano rispettivamente i quozienti delle divisioni di a per d e b per d.

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

Eqn003.gif

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

Eqn004.gif

Eqn005.gif

cioè d è anche divisore di r.

Quindi

 


Il minimo comune multiplo (mcm)


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

Eqn008.gif

Dimostrazione

Dalla (7) segue immediatamente

Eqn021.gif

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

 


Implementazione Javascript