[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Algoritmo di Euclide
per il calcolo del MCD

Questa pagina contiene programmi in javascript.
Potete salvarla sul vostro computer e utilizzarla senza essere collegati a internet.


L'algoritmo originale di Euclide, basato su sottrazioni successive

L'algoritmo per il calcolo del MCD di due interi positivi, nella sua versione pi� semplice, si basa sulla seguente propriet�:

Se due numeri, m, n, sono divisibili per un terzo numero, x, allora anche la loro differenza � divisibile per x.

Per dimostrarla, si pu� utilizzare la propriet� distributiva. Supponiamo m>n.
m=kx
n=hx
m-n=kx-hx=x(k-h)
Dunque si pu� dire che:

MCD(m,n) = MCD((m-n),n)

Come si vede, questa regola permette di passare, per mezzo di sottrazioni successive, a MCD di numeri sempre pi� piccoli, fino ad ottenere:

MCD(a,0)=a

L'algoritmo pu� essere scritto cos�:

Finch� m>0
se n>m allora scambia m con n
Sottrai n da m e assegna ad m il valore della differenza (m=m-n)
Ripeti il ciclo
n � il MCD cercato

Questo algoritmo � implementato in linguaggio javascript nel riquadro qui sotto.
Potete utilizzarlo per fare degli esperimenti.
La traccia dei calcoli vi far� capire come funziona.

Calcolo del Massimo Comune Divisore di 2 numeri
Algoritmo originale di Euclide, metodo delle sottrazioni successive

Digita i due numeri nelle caselle a destra: m= n=

MCD (m,n) =

Traccia dei calcoli eseguiti


Un algoritmo pi� veloce, basato su divisioni successive

Euclide descrisse questo algoritmo nel suo libro degli Elementi. Invece di usare i numeri interi, per�, utilizz� i segmenti di retta. Perci� il suo algoritmo serve anche a determinare il massimo comune divisore di due segmenti.
In certi casi l'algoritmo pu� richiedere numerosissimi passaggi, risultando molto lento (provate con MCD (900,15)).
Conviene quindi renderlo pi� veloce e si pu� fare ricorrendo ad una serie di divisioni con resto anzich� sottrazioni.
Il principio su cui ci si basa � il seguente (supponiamo m>n):

MCD(m,n) = MCD(r,n)dove r � il resto della divisione m/n

Come si vede, questa regola permette di passare rapidamente, per mezzo di divisioni con resto successive, a MCD di numeri sempre pi� piccoli, fino ad ottenere:

MCD(r,0)=r

Questo algoritmo � implementato in linguaggio javascript nel riquadro qui sotto.
Potete utilizzarlo per fare degli esperimenti. E' molto pi� veloce del primo.
La traccia dei calcoli vi far� capire come funziona.
Pi� sotto troverete la spiegazione dettagliata.

Calcolo del Massimo Comune Divisore di 2 numeri
Algoritmo derivato da Euclide, metodo delle divisioni successive

Digita i due numeri nelle caselle a destra: m= n=  

-

MCD (m,n) = mcm (m,n)=

Traccia dei calcoli eseguiti

Combinazione lineare di m, n:   

 
Spiegazione dell'algoritmo basato sulle divisioni con resto successive
Prendiamo a,b interi con a,b>0 e supponiamo 0<a<b.
Dividiamo b per a, avremo che:
b = q1a+r1, con 0 <= r1<a.
Osserviamo che:
i) se r1=0, allora b = q1a e abbiamo gi� che MCD(a,b)=a;
ii) altrimenti, preso un intero positivo d
1) se d divide sia a che b, allora divider� anche r1 in quanto combinazione lineare di a e b;
2) viceversa, se d divide a e r1, divider� anche b per la stessa propriet� sopra.

Quindi possiamo concludere che
MCD(a,b) = MCD(a,r1),
con il vantaggio che
r1<a<b.

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r1 con r1<a:
a
= q2r1+r2 , con 0<=r2<r1
dove
i) se r2=0, si ha che r2|a, quindi MCD(a,b) = MCD(a,r1) = r2;
ii) altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a,b)=MCD(a,r1)=MCD(r1,r2).

Continuiamo a costruire queste successioni di resto sino ad arrivare all'i-esima iterazione dove
r
i-1=qi+1ri+ri+1, con 0<=ri+1<ri
e avremo che
i) se ri=0, allora MCD(a,b) = ri-1;
ii) altrimenti, continuiamo il procedimento.

Poich� gli ri sono interi non negativi e la successione di resti � decrescente, ad un certo punto ci dovremo fermare, cio� esister� un rn diverso da zero tale che rn+1=0, allora il nostro MCD(a,b) sar� uguale all'ultimo resto diverso da zero della catena di divisioni.
Questo procedimento � vantaggioso perch� non dobbiamo scomporre in fattori primi e si utilizzano divisioni sempre pi� facili.
Proviamo ora a ricostruire s,t procedendo a ritroso nell'algoritmo euclideo:
presi MCD(a,b) = rn e sa+tb = rn, possiamo scrivere
r
n = rn-2 - qnrn-1,
e andiamo a sostituire il valore di rn-1 che si ricava dall'uguaglianza rn-3 = qn-1rn-2 + rn-1:
r
n = rn-2 - qn(rn-3-qn-1rn-2) = (1+qnqn-1) rn-2 - qnrn-3.
Ora sostituiamo in questa equazione il valore di rn-2 che si ottiene da rn-4 = qn-2rn-3 + rn-2 e avremo rn come espressione in rn-3 e rn-4, quindi andremo a sostituire rn-3 e continueremo questo procedimento fino ad ottenere rn come combinazione lineare dei soli a e b.

Tratto da: http://www.dm.unibo.it/matematica/Congruenze/html/pag2/pag2.htm

agosto 2004


Sito Web realizzato da Gianfranco Bo