Soluzioni
  • 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 a \mbox{ e } b due numeri interi, con 0 \le b < a.

    1) Se b=0 allora \mbox{mcd}(a,b)=a (qualsiasi numero diverso da zero è un divisore di zero).

    2) Se b \neq 0 si svolge la divisione tra a \mbox{ e } b, chiamando q il quoziente ed r il resto della divisione

    a:b=q\ \mbox{ resto } r,\ \ \ \mbox{ con } 0\le r < b

    3) Porre a=b \mbox{ e } b=r.

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

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

    Esempio sull'algoritmo di Euclide

    Calcolare il massimo comun divisore tra 126 e 147.

    PASSO 1

    Poiché 126<147, poniamo a=147 \mbox{ e } b=126.

    Dal momento che b=126 \neq 0 calcoliamo quoziente e resto della divisione tra a \mbox{ e } b

    147:126=1, \mbox{ resto } 21

    Poniamo a=126 \mbox{ e } b=21, dove 21 è il resto della divisione appena svolta.

    PASSO 2

    Visto che b=21 \neq 0 svolgiamo la divisione tra a=126 \mbox{ e } b=21

    126:21=6, \mbox{ resto } 0

    Poniamo a=21 \mbox{ e } b=0, dove 0 è il resto dell'ultima divisione svolta.

    PASSO 3

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

    \mbox{mcd}(126,147)=21

    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.

     

    Algoritmo di Euclide con diagramma di flusso

     

    Algoritmo di Euclide per il mcm

    Dati due numeri naturali a \mbox{ e } b, il loro minimo comune multiplo si ottiene dividendo il loro prodotto per il loro massimo comun divisore, ossia

    \mbox{mcm}(a,b) = \frac{a \cdot b}{\mbox{mcd}(a,b)}

    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 a \mbox{ e } b, si possono determinare due numeri interi x \mbox{ e } y tali che

    ax+by=\mbox{mcd}(a,b)

    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. ;)

    Risposta di Galois
MEDIEGeometriaAlgebra e Aritmetica
SUPERIORIAlgebraGeometriaAnalisiVarie
UNIVERSITÀAnalisiAlgebra LineareAlgebraAltro
EXTRAVita quotidiana
Esercizi simili e domande correlate
Domande della categoria Superiori-Algebra