Calcolatrice del massimo comune divisore e del minimo comune multiplo
Inserendo due interi positivi, ricava il massimo comune divisore con l'algoritmo di Euclide e ne mostra i passaggi uno per uno. Calcola contemporaneamente anche il minimo comune multiplo.
| Massimo comune divisore | |
|---|---|
| Minimo comune multiplo |
Passaggi dell'algoritmo di Euclide
| Calcolo |
|---|
| = × + |
Che cos'è l'algoritmo di Euclide
L'algoritmo di Euclide è il procedimento classico per ricavare il massimo comune divisore di due interi. Si divide il numero maggiore per il minore, si considera il resto e si ripete l'operazione con il divisore e il resto; quando il resto si annulla, il divisore di quel passaggio è il massimo comune divisore. Anche con numeri grandi bastano pochi passaggi per ottenerlo con esattezza. È riportato negli Elementi di Euclide, intorno al 300 avanti Cristo, ed è considerato uno degli algoritmi più antichi giunti fino a noi.
Che cos'è il calcolo di MCD e mcm
Il massimo comune divisore (MCD) è il più grande intero che divide due interi senza resto, e il minimo comune multiplo (mcm) è il più piccolo intero fra i multipli comuni a due interi. Inserite due interi positivi e questo strumento ricava all'istante entrambi i valori con l'algoritmo di Euclide, mostrando inoltre il procedimento passo per passo: dividendo, divisore, quoziente e resto.
A mano la via consueta passa dalla scomposizione in fattori primi e dalla ricerca dei fattori comuni, ma più i numeri crescono, più quella scomposizione diventa laboriosa. L'algoritmo di Euclide che questo strumento adopera trova il massimo comune divisore con sole divisioni ripetute, così anche interi con molte cifre seguono esattamente lo stesso procedimento. L'inserimento è limitato agli interi da 1 in su; con zero, un numero negativo o un decimale non compare alcun risultato.
Come usare il calcolatore di MCD e mcm
- Inserire il numero A Digitate il primo intero positivo di cui volete il massimo comune divisore e il minimo comune multiplo.
- Inserire il numero B Digitate il secondo intero positivo. Quale fra A e B sia il maggiore non cambia il risultato.
- Controllare il risultato Il massimo comune divisore (MCD) e il minimo comune multiplo (mcm) compaiono automaticamente.
- Seguire il procedimento Ogni passo dell'algoritmo di Euclide (dividendo = divisore × quoziente + resto) è disposto in una tabella, così potete seguire il procedimento finché il resto arriva a zero.
Consigli per sfruttarlo al meglio
- Il minimo comune multiplo si ricava dividendo il prodotto dei due numeri per il loro massimo comune divisore. Si usa spesso per ridurre le frazioni al comune denominatore e per stabilire quando coincidano eventi che si ripetono con periodi diversi.
- Se i due numeri sono coprimi, cioè hanno massimo comune divisore pari a uno, il minimo comune multiplo coincide semplicemente con il loro prodotto.
- L'algoritmo di Euclide ha il vantaggio pratico di calcolare il massimo comune divisore di numeri grandi assai più rapidamente della scomposizione in fattori primi.
- L'ordine dei due numeri inseriti non incide sul risultato: internamente il calcolo comincia sempre dal maggiore.
Quando il calcolo di MCD e mcm torna utile
Preparare la semplificazione di una frazione
Trovate il massimo comune divisore di numeratore e denominatore: dividendo entrambi per quel numero la frazione si semplifica. Se volete vedere il risultato semplificato, un calcolatore di frazioni con funzione di semplificazione è comodo.
Calcolare quando più cicli coincidono
Se una cosa accade ogni 3 giorni e un'altra ogni 5, la volta successiva in cui cadranno nello stesso giorno è 15 giorni dopo — il minimo comune multiplo di 3 e 5. Si applica alla regolazione dei cicli di turni ed eventi.
Verificare compiti di matematica ed esercizi d'esame
Potete controllare subito se il massimo comune divisore o il minimo comune multiplo ricavato a mano è corretto, procedimento compreso.
Preparare la ricerca di un denominatore comune
Quando riducete allo stesso denominatore più frazioni con denominatori diversi, il minimo comune multiplo di quei denominatori diventa il nuovo denominatore comune.
Afferrare le basi della crittografia
Il calcolo dei massimi comuni divisori sorregge la crittografia moderna, fra l'altro la generazione delle chiavi RSA, perciò seguire il procedimento è un utile primo passo per capirne il funzionamento.
I termini impiegati qui
- Massimo comune divisore (MCD)
- Il più grande fra gli interi che dividono senza resto due o più interi e che si chiamano i loro divisori comuni.
- Minimo comune multiplo (mcm)
- Il più piccolo fra i multipli che due o più interi hanno in comune e che si chiamano i loro multipli comuni.
- Algoritmo di Euclide
- Un procedimento che guarda il resto della divisione del numero maggiore per il minore e ripete la stessa operazione sulla coppia divisore-resto per trovare il massimo comune divisore. Il nome risale all'opera del matematico greco antico Euclide.
- Coprimi
- Si dice di due interi il cui massimo comune divisore è 1. Il minimo comune multiplo di due numeri coprimi è semplicemente il loro prodotto.
- Scomposizione in fattori primi
- Il ridurre un intero a un prodotto di numeri primi. MCD e mcm si possono ricavare anche dalla combinazione dei fattori primi comuni, ma per numeri grandi l'algoritmo di Euclide è più rapido.
- Divisore comune e multiplo comune
- Un divisore comune è un divisore condiviso da più interi; un multiplo comune è un multiplo che essi hanno in comune. MCD e mcm ne sono rispettivamente il più grande e il più piccolo.
Domande frequenti
A proposito — perché un algoritmo di oltre duemila anni è ancora in servizio
L'algoritmo di Euclide è descritto nel settimo libro degli Elementi, l'opera composta intorno al 300 avanti Cristo dal matematico greco Euclide. È considerato uno degli algoritmi più antichi di cui resti documentazione e, oltre duemila anni dopo, continua a essere il primo esempio presentato nei manuali di informatica.
La ragione di tanta longevità sta nella sua efficienza. Si dimostra che il numero di passaggi necessari è dell'ordine del numero di cifre dei valori in ingresso — il caso peggiore si presenta con coppie di numeri legate alla successione di Fibonacci — cosicché il massimo comune divisore si calcola in tempi ragionevoli per interi di qualunque grandezza.
Anche la crittografia moderna, come quella RSA, si serve del calcolo del massimo comune divisore, o della sua versione estesa, nella generazione delle chiavi: che una scoperta matematica dell'antichità sia oggi parte dell'infrastruttura che protegge Internet è un fatto che dice molto sull'universalità della matematica.