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

Università e Master

Come dimostrare l'infinità dei numeri primi

Euclide fu il primo a dimostrare l’infinità dei numeri primi per la prima volta nella storia. Egli, infatti, dimostrò che non esiste il numero più grande di tutti, perché ne esisterà sempre uno più grande di un altro. Successivamente a questa...
Università e Master

Come scoprire se due numeri sono amicabili

La matematica non è certo una delle materie più amate dagli studenti. Anzi, un recente sondaggio afferma come sia in fondo alle classifiche di gradimento. Ma la matematica ha un fascino molto particolare, che va capito prima di poter essere apprezzato....
Università e Master

Come risolvere una equazione diofantea

Un'equazione diofantea è un'equazione algebrica in una o più incognite di cui si cercano le soluzioni intere. Prende il nome dal matematico Diofanto, vissuto nel III secolo d. C., noto per l'epitaffio che permette di calcolare l'età della sua morte...
Università e Master

Come Dire I Numeri In Cinese

La civiltà della Repubblica Popolare Cinese è sicuramente una tra le più affascinanti sia grazie alla sua storia millenaria, ma anche grazie alla sua lingua. Il cinese, infatti, è decisamente distante da tutte le lingue occidentali ed è dotata di...
Università e Master

Come Si Dicono I Numeri In Francese

Per tantissimo tempo, il francese ha rappresentato la lingua della "cultura" per eccellenza: infatti, era la lingua internazionale di riferimento prima di essere sostituita dall'inglese. Questa lingua ha una grammatica abbastanza impegnativa con molte...
Università e Master

Come funziona la crittografia RSA

Iniziamo questa guida con il capire cos'è la crittografia RSA.In seguito vedremo anche da cosa è costituita, l'esempio pratico e le varie fasi.RSA è l'acronimo di Ron Rivest, Adi Shamir e Leonard Adleman, che per primi descrissero pubblicamente l'algoritmo...
Università e Master

Teorema dell'infinità dei numeri primi: dimostrazione

La matematica è da sempre la materia più complicata sia per i bambini delle scuole elementari, sia per gli studenti delle superiori e delle facoltà universitarie. Questa difficoltà è dovuta soprattutto al fatto che i concetti sono tutti collegati...
Università e Master

Come Calcolare I Numeri Di Fibonacci

In matematica quella che viene definita la successione di Fibonacci, è una successione composta da numeri interi positivi, nella quale ciascun numero è l'esatta somma dei due precedenti. Quindi essa ha una definizione ricorsiva. Tale successione prendere...
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 »”.