[HOME - BASE Cinque - Appunti di Matematica ricreativa]
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.
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.
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 Ora ripetiamo lo stesso
procedimento sostituendo al posto di a e b
i nuovi valori a e r1 con r1<a: Continuiamo a costruire
queste successioni di resto sino ad arrivare all'i-esima
iterazione dove 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. Tratto da: http://www.dm.unibo.it/matematica/Congruenze/html/pag2/pag2.htm |
agosto 2004
Sito Web realizzato da Gianfranco Bo