Algoritmo di Euclide

Normalmente quando si deve calcolare il MCD tra due o più numeri si procede prima alla scomposizione in fattori primi dei numeri dati, poi si prendono solo i fattori comuni con il massimo esponente e si moltiplicano tra loro.

Questo procedimento può essere agevole per numeri relativamente piccoli, dell'ordine delle centinaia o migliaia, ma quando si tratta di trovare, ad esempio il MDC di due numeri come 288681 e 210453?

In questo caso la scomposizione in fattori prima potrebbe risultare un po' laboriosa, per questo si ricorre all'algoritmo di Euclide.

In pratica dati due numeri a, b con a > b e b diverso da 0 si procede con i seguenti passi:

1)
Eseguire la divisione a : b in modo da ottenere un quoziente (q) e un resto (r)

se r è diverso da 0 proseguire, altrimenti, se r = 0, b rappresenterà il MCD tra a e b

2)
Se r del punto 1) è diverso da 0, allora considerare a = b e b = r, quindi ripetere i punti 1) e 2) fino ad arrivare ad avere r = 0

Se si arriva ad avere una divisione con q = 0 e r diverso da 0, allora i due numeri di partenza non hanno divisori in comune sono, cioè, primi tra loro.

Detto così può sembrare un metodo complesso, ma con un esempio pratico l'utilizzo dell'algoritmo sarà sicuramente più chiaro.

Riconsideriamo i due numeri 288681 e 210453 e cerchiamone il MCD con l'applicazione di questo algoritmo:

288681 : 210453 = 1,371...

per esprimerla come quoziente + resto, calcoliamo il resto della divisione

r = 288681 - (210453 * 1) = 78228

quindi 288681 : 210453 = 1 + 78228, essendo r diverso da 0 proseguiamo

210453 : 78228 = 2,690...

r = 210453 - (78228 * 2) = 53997

quindi 210453 : 78228 = 2 + 53997, r è ancora diverso da 0, proseguiamo

78228 : 53997 = 1,448...

r = 78228 - (53997 * 1) = 24231

quindi 78228 : 53997 = 1 + 24231, r diverso da 0, proseguiamo

53997 : 24231 = 2,228...

r = 53997 - (24231 * 2) = 5535

quindi 53997 : 24231 = 2 + 5535, r diverso da 0, proseguiamo

24231 : 5535 = 4,377...

r = 24231 - (5535 * 4) = 2091

quindi 24231 : 5535 = 4 + 2091, r diverso da 0, proseguiamo

5535 : 2091 = 2,647...

r = 5535 - (2091 * 2) = 1353

quindi 5535 : 2091 = 2 + 1353, r diverso da 0, proseguiamo

2091 : 1353 = 1,492...

r = 2019 - (1353 * 1) = 738

quindi 2091 : 1353 = 1 + 738, r diverso da 0, proseguiamo

1353 : 738 = 1,833...

r = 1353 - (738 * 1) = 615

quindi 1353 : 738 = 1 + 615, r diverso da 0, proseguiamo

738 : 615 = 1,2

r = 738 - (615 * 1) = 123

quindi 738 : 615 = 1 + 123, r diverso da 0, proseguiamo

615 : 123 = 5

A questo punto il resto di quest'ultima divisione è 0, quindi abbiamo trovato che il MCD tra 288681 e 210453 è 123.

Il procedimento con l'algoritmo di Euclide può, come abbiamo appena visto, risultare abbastanza lungo, ma, trattandosi essenzialmente di una sequenza di divisioni, risulta di agevole utlizzo.