Come trovare il massimo comun divisore tra due numeri con l'algoritmo di Euclide

tramite: O2O
Difficoltà: media
14

Introduzione

La matematica è certamente una delle materie scolastiche che a tanti di noi ha dato le maggiori preoccupazioni; tuttavia, con un po' di pazienza e costante applicazione può rivelarsi meno complicata di quanto sembra e regalarci tante soddisfazioni. Sin dalle scuole elementari, ad esempio, ci è stato insegnato come calcolare il massimo comune divisore tra due numeri con il metodo tradizionale. In questa guida voglio proporvi, invece, un metodo alternativo che sfrutta i resti della divisione tra numeri, il quale viene utilizzato soprattutto in campo informatico e presenta un livello di difficoltà molto simile al metodo tradizionale. Applicando, quindi, le seguenti indicazioni imparerete a trovare il massimo comun divisore tra due numeri con l'algoritmo di Euclide.

24

Grazie all'utilizzo di questo metodo riusciremo a stabilire il massimo comune divisore tra due numeri sfruttando la divisione tra numeri interi, che non prevede l'uso di virgole. Per praticità chiameremo X il numero più grande e Y quello più piccolo.
Come prima operazione iniziamo a scrivere il numero X come dato dalla somma di un multiplo di Y con l'aggiunta di un certo resto R1 tale per cui avremo l'espressione: X=Y*multiplo R1. Successivamente prendiamo Y e lo scriviamo come somma di R1 e un nuovo resto R2 tale che Y=R1*multiplo R2 e cosi via.

34

Dopo una serie più o meno lunga di passaggi (il numero di passaggi dipende anche dalla grandezza dei numeri scelti), riusciremo ad ottenere un resto che sarà pari a 0. A questo punto non ci rimane altro che vedere qual è il resto dell'ultimo passaggio, che corrisponderà proprio al MCD tra X e Y.
Per capire meglio il concetto sarà utile fare un paio di esempi pratici.
Come primo esempio possiamo utilizzare due numeri molto semplici, il cui MCD è facilmente intuibile: prendiamo, allora, 72=X e 27=Y ed andiamo ad applicare la formula indicata in precedenza. Otterremo così:
72=27*2 resto 18; 27=18*1 resto 9; 18=9*2 resto 0.
Quando l'ultimo resto sarà uguale a zero, andremo, quindi, a considerare il resto dell'equazione precedente, cioè 9, che corrisponderà proprio al massimo comun divisore fra 72 e 27.

Continua la lettura
44

Possiamo passare ora ad un esempio solo apparentemente più complesso, dato che soltanto il numero di passaggi da eseguire è più elevato, mentre la regola da applicare è sempre la stessa.
Prendiamo 374=X e 143=Y e procediamo in questo modo:
374=143*2 resto 88; 143=88*1 resto 55; 88=55*1 resto 33; 55=33*1 resto 22; 33=22*1 resto 11; 22=11*2 resto 0.
Siamo arrivati ad ottenere 0, quindi, come nell'esempio precedente, prendiamo l'ultimo resto diverso dallo 0, cioè 11, che corrisponderà proprio al MCD tra i numeri 374 e 143, come potremo verificare grazie all'uso di una calcolatrice.
Questo tipo di calcolo è molto utilizzato nello svolgimento delle equazioni congruenziali, che riguardano la parte dell'aritmetica degli interi.

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Superiori

Come Risolvere I Casi Particolari Della Divisione Con I Numeri Relativi

I numeri relativi fanno parte di una categoria di numeri certamente molto utilizzata in matematica. Molti, infatti, sono gli ambiti in cui essi trovano applicazione. Tra le operazioni fondamentali che possono essere fatti con i numeri relativi si colloca...
Elementari e Medie

Come Sapere Se Un Numero è Divisibile Per Due

A partire dalle scuole dell'infanzia fino ad arrivare all'università e alla vita quotidiana (compreso il lavoro, le piccole mansioni domestiche, fare la spesa e comprare ciò che ci piace) ci hanno abituato a imparare mnemonicamente quali sono i criteri...
Elementari e Medie

Come svolgere una divisione con il metodo anglosassone

Questa guida vi permetterà di svolgere e quindi risolvere le divisioni con un metodo decisamente più semplice e più veloce di quello italiano, il metodo anglosassone, utilizzato in tutti i paesi del Commonwealth, del Canada e degli Stati Uniti d'America....
Elementari e Medie

Come calcolare il massimo comune divisore tra monomi

Il massimo comune divisore (che normalmente viene abbreviato con l'acronimo di M. C. D.) di più numeri non è altro che il numero più grande per il quale possono essere divisi tutti i numeri dati in una operazione. In altre parole, possiamo dire che...
Elementari e Medie

Come spiegare la divisione a due cifre ai bambini

La divisione a due cifre senza l'uso di una calcolatrice può risultare ostica perfino ad un adulto, figuriamoci ad un bambino di seconda o terza elementare. Bisogna, pertanto, essere davvero dei bravi insegnanti per riuscire a far comprendere velocemente...
Superiori

Come moltiplicare e dividere i decimali

Qualunque sia la nostra idea sulla matematica: più o meno difficoltosa, più o meno gradita, una cosa è certa; non è una scienza opinabile. Le apparenti problematiche che ce la fanno sembrare ardua da studiare, si possono risolvere con solo due mezzi,...
Superiori

Come risolvere una divisione tra numeri decimali finiti

I numeri decimali fanno parte della matematica a tutti gli effetti, proprio come accade con i numeri naturali. In particolare, i decimali finiti (per esempio 3.1, 4.2) sono quei numeri che, dopo la virgola, presentano un "determinato" numero di cifre....
Elementari e Medie

Come fare le divisioni con la virgola

Chi si ricorda del mitico pallottoliere? In effetti viviamo in un’epoca in cui per fare le operazioni matematiche non occorre neanche piú la calcolatrice, dato che possiamo comodamente usare un telefono cellulare, a tutto discapito peró dell’agilitá...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.