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.
Consigli
- 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.
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.