Algoritmo di Euclide

L'algoritmo di Euclide è un procedimento algebrico che permette di calcolare il massimo comun divisore tra due numeri interi attraverso un numero finito di passi basati sul calcolo di alcune divisioni.

Alla scuola media impariamo a calcolare il massimo comun divisore tra due numeri naturali ricorrendo alla scomposizione in fattori primi.

Quando però i numeri iniziamo a diventare leggermente grandi (anche solo superiori a 100) scomporli in fattori primi risulta sempre più difficile, anche perché non si ricorda bene quali siano i numeri primi maggiori di 100.

In questi casi ci viene in aiuto l'algoritmo di Euclide, il quale attraverso il calcolo di alcune semplici divisioni ci fornisce il massimo comun divisore cercato.

Passi dell'algoritmo di Euclide

Siano due numeri interi, con .

1) Se allora (qualsiasi numero diverso da zero è un divisore di zero).

2) Se si svolge la divisione tra , chiamando il quoziente ed il resto della divisione

3) Porre .

4) Iniziare una nuova iterazione ripartendo dal punto 1).

L'algoritmo di Euclide procede finché non si trova un .

Esempio sull'algoritmo di Euclide

Calcolare il massimo comun divisore tra 126 e 147.

PASSO 1

Poiché , poniamo .

Dal momento che calcoliamo quoziente e resto della divisione tra

Poniamo , dove 21 è il resto della divisione appena svolta.

PASSO 2

Visto che svolgiamo la divisione tra

Poniamo , dove 0 è il resto dell'ultima divisione svolta.

PASSO 3

Poiché possiamo concludere che il massimo comun divisore cercato è uguale all'ultimo valore assegnato alla variabile , ossia

Come risulta evidente dall'esempio precedente, ai fini del calcolo del massimo comun divisore tra due numeri con l'algoritmo di Euclide, il termine di riferimento è il resto di ciascuna delle divisioni svolte.

Algoritmo di Euclide con il diagramma di flusso

Nel seguente diagramma di flusso abbiamo riportato i vari passaggi utili all'applicazione dell'algoritmo di Euclide.

Diagramma di flusso per l'algoritmo di Euclide.

Algoritmo di Euclide per il mcm

Dati due numeri naturali , il loro minimo comune multiplo si ottiene dividendo il loro prodotto per il loro massimo comun divisore, ossia

Pertanto per calcolare il minimo comune multiplo tra due numeri con l'algoritmo di Euclide è sufficiente ricorrere a tale algoritmo per il calcolo del massimo comun divisore, per poi utilizzarlo per dividere il prodotto dei due numeri.

Algoritmo di Euclide esteso

Tenendo nota dei quozienti ottenuti durante lo svolgimento dell'algoritmo di Euclide per calcolare il massimo comun divisore tra , si possono determinare due numeri interi tali che

Tale procedimento è noto come algoritmo di Euclide esteso ed è alla base della risoluzione delle equazioni diofantee.

Per vedere un esempio: equazione diofantea con l'algoritmo di Euclide - click!

***

Con questo abbiamo finito. :) Se dovete applicare l'algoritmo di Euclide nella risoluzione degli esercizi vi raccomandiamo di usare il tool per calcolare il MCD online, in modo da controllare l'esattezza dei risultati. ;)