Due metodi
Scomposizione in fattori primi. Si scompongono i numeri e si moltiplicano i soli fattori comuni, presi con l’esponente più basso. Per 48 = 2⁴ × 3, 180 = 2² × 3² × 5 e 84 = 2² × 3 × 7: MCD = 2² × 3 = 12.
Algoritmo di Euclide. Si basa sul fatto che MCD(a, b) = MCD(b, a mod b). Per 180 e 48:
- 180 = 3 × 48 + 36
- 48 = 1 × 36 + 12
- 36 = 3 × 12 + 0
L’ultimo resto non nullo è 12. È molto più veloce della scomposizione con numeri grandi.
I divisori comuni a tutti i numeri sono esattamente i divisori del MCD.
Domande frequenti
Come funziona l'algoritmo di Euclide?
Si divide il numero più grande per il più piccolo e si prende il resto. Poi si divide il divisore per il resto, e così via, finché il resto diventa zero: l'ultimo resto diverso da zero è il MCD. È uno degli algoritmi più antichi ancora in uso.
Cosa significa che due numeri sono primi tra loro?
Che il loro massimo comune divisore è 1: non hanno fattori primi in comune. 8 e 15 sono primi tra loro anche se nessuno dei due è un numero primo.
Fonti
- Euclide, Elementi, libro VII, proposizioni 1-2 (algoritmo di Euclide)