Algoritmo di Euclide per il calcolo MDC

Consideriamo due numeri interi a e b, con a diverso da 0 e maggiore di b. Vogliamo calcolare il MCD(a,b).

Teniamo presenti le seguenti proprietà del MCD:

  • Se b=0 allora MCD(a,0)=a
  • Se b è diverso da 0, detto r il resto della divisione tra a e b, MCD(a,b)=MCD(b,r)

Queste proprietà permettono di calcolare il MCD di a e b, eseguendo una serie di divisioni.

Nel riquadro sottostante viene descritto il procedimento: basta digitare due numeri e cliccare per eseguire il calcolo.

Calcolo del Massimo Comune Divisore di 2 numeri
Algoritmo delle divisioni successive

Digita i due numeri:

a = b =   

 

MCD (a,b) = mcm (a,b)=

Divisioni successive: