MCD: come si calcola il massimo comune divisore
MatematicaScegli da quanti numeri partire e inseriscili: il calcolatore ricava il massimo comune divisore e mostra la scomposizione in fattori primi e le divisioni di Euclide, così puoi seguire il calcolo e rifarlo da solo.
Passaggi
MCD(12, 18) = 6
- Si scompongono 12 e 18 in fattori primi, come mostra la tabella qui sotto.
- Si moltiplicano i fattori primi comuni, ciascuno con l’esponente più piccolo: 2 · 3 (se non ce ne sono, il prodotto è 1).
- Il prodotto è il massimo comune divisore: 6.
- Con le divisioni successive di Euclide si arriva allo stesso risultato: l’ultimo divisore, quello che lascia resto 0, è 6.
Appena tutti i dati sono validi, qui vedi ogni passaggio del calcolo.
Formula
- MCD
- massimo comune divisore, il più grande numero che divide tutti i numeri dati
- pi
- i numeri primi che dividono tutti i numeri
- mi
- il più piccolo esponente con cui quel numero primo compare nelle scomposizioni
- q, r
- quoziente e resto della divisione di a per b, con r minore di b
Come funziona il calcolo
Il massimo comune divisore (MCD) di due o più numeri interi è il più grande numero che li divide tutti senza lasciare resto. I divisori di 12 sono 1, 2, 3, 4, 6 e 12; quelli di 18 sono 1, 2, 3, 6, 9 e 18. I divisori comuni sono 1, 2, 3 e 6 e il più grande è 6, quindi MCD(12, 18) = 6. Quando il MCD è 1 i numeri si dicono primi tra loro (o coprimi).
Il primo metodo è la scomposizione in fattori primi: si scrive ogni numero come prodotto di numeri primi, si tengono i fattori che compaiono in tutti i numeri e si moltiplicano, ciascuno con l’esponente più piccolo. È il metodo che si impara a scuola e il calcolatore mostra la scomposizione di ogni numero nella tabella sotto il risultato.
Il secondo metodo è quello delle divisioni successive, o algoritmo di Euclide, e non richiede di scomporre i numeri: si divide il maggiore per il minore, poi il divisore per il resto ottenuto, e si ripete finché il resto è 0. L’ultimo divisore è il MCD. È il metodo più rapido con i numeri grandi. Con tre o quattro numeri si calcola il MCD dei primi due e poi quello tra il risultato e il numero successivo: nella seconda tabella trovi tutte le divisioni, una dopo l’altra.
Il MCD serve a ridurre una frazione ai minimi termini, dividendo numeratore e denominatore per il loro MCD, e a semplificare un rapporto: 36 : 60 diventa 3 : 5 dividendo per 12. Serve anche a dividere in parti uguali senza avanzi: un pavimento di 360 cm per 240 cm si copre con piastrelle quadrate intere, tutte uguali, di lato massimo 120 cm. Per semplificare una frazione passo per passo c’è il calcolo frazioni, per misurare la superficie da piastrellare il calcolo dei metri quadri, per sapere che percentuale è una parte sul totale il calcolo percentuale e per le misure di una pianta o di un modellino il convertitore di scala.
La formula
Con la scomposizione, 12 = 2² · 3 e 18 = 2 · 3²: i fattori primi comuni sono 2 e 3 e l’esponente più piccolo di ciascuno è 1, quindi MCD = 2 · 3 = 6. Un fattore che manca in uno dei numeri non entra nel prodotto e, se non ci sono fattori in comune, il MCD è 1.
L’algoritmo di Euclide si basa sul fatto che MCD(a, b) = MCD(b, r), dove r è il resto della divisione di a per b: ogni divisione sostituisce la coppia con una più piccola che ha lo stesso MCD, perciò il resto 0 si raggiunge in pochi passaggi. Con 18 e 12: 18 = 1 · 12 + 6, poi 12 = 2 · 6 + 0, e l’ultimo divisore è 6.
Tra il MCD e il minimo comune multiplo (mcm) di due numeri vale la relazione a · b = MCD · mcm, riportata anche dall’Enciclopedia Treccani.
Esempio di calcolo
Quanto fa il MCD di 252 e 198?
- Scomposizione in fattori primi: 252 = 2² · 3² · 7 e 198 = 2 · 3² · 11.
- I fattori comuni sono 2 e 3, presi con l’esponente più piccolo (2 alla prima e 3 alla seconda): 2 · 3² = 18.
- Con le divisioni successive: 252 = 1 · 198 + 54, 198 = 3 · 54 + 36, 54 = 1 · 36 + 18, 36 = 2 · 18 + 0. L’ultimo divisore è 18, lo stesso risultato.
Il MCD di 252 e 198 è 18: è il più grande numero che divide entrambi.
Inserisci l’esempio nel calcolatoreDomande frequenti
Come si calcola il MCD con la scomposizione in fattori primi?
Si scrive ogni numero come prodotto di numeri primi, si individuano i fattori che compaiono in tutti i numeri e si moltiplicano, ciascuno con l’esponente più piccolo. Per 12 = 2² · 3 e 18 = 2 · 3² i fattori comuni sono 2 e 3, entrambi alla prima potenza: MCD = 2 · 3 = 6. Il calcolatore mostra la scomposizione di ogni numero.
Come funziona l’algoritmo di Euclide per il MCD?
Si divide il numero maggiore per il minore e si guarda il resto, poi si divide il divisore per quel resto, e così via finché il resto è 0. L’ultimo divisore è il MCD. Con 18 e 12: 18 = 1 · 12 + 6, poi 12 = 2 · 6 + 0, quindi il MCD è 6. Funziona bene anche con numeri molto grandi, dove scomporre richiederebbe molto tempo.
Qual è il MCD di 12 e 18?
È 6. I divisori comuni di 12 e 18 sono 1, 2, 3 e 6 e il più grande è 6. Con i fattori primi: 12 = 2² · 3 e 18 = 2 · 3², quindi MCD = 2 · 3 = 6. È anche il risultato che il calcolatore mostra all’apertura della pagina.
Quanto fa il MCD di 16 e 14, di 3 e 6 o di 5 e 7?
MCD(16, 14) = 2, perché 16 = 2⁴ e 14 = 2 · 7 hanno in comune un solo 2. MCD(3, 6) = 3: quando il numero più piccolo divide il più grande, è lui il MCD. MCD(5, 7) = 1: due numeri primi diversi non hanno altri divisori comuni oltre a 1, quindi sono primi tra loro.
Che cos’è il massimo comune divisore?
È il più grande numero intero che divide tutti i numeri dati senza lasciare resto. Per due numeri a e b si scrive MCD(a, b), in inglese GCD (greatest common divisor). Esiste sempre ed è unico: per esempio MCD(30, 45) = 15, perché 15 divide sia 30 sia 45 e nessun numero più grande lo fa.
Come si calcola il MCD di tre o più numeri?
Si può scomporre ogni numero e moltiplicare i fattori comuni a tutti, oppure applicare Euclide due numeri alla volta: MCD(a, b, c) = MCD(MCD(a, b), c). Per 48, 180 e 300: MCD(48, 180) = 12 e MCD(12, 300) = 12. Il calcolatore gestisce da due a quattro numeri e scrive tutte le divisioni.
Quando due numeri sono primi tra loro?
Quando il loro MCD è 1, cioè non hanno altri divisori comuni oltre a 1. Non devono essere numeri primi: 8 e 15 sono primi tra loro anche se nessuno dei due è primo, perché MCD(8, 15) = 1. In questo caso il calcolatore lo segnala nel risultato. Con tre o quattro numeri il MCD è 1 quando nessun divisore maggiore di 1 li divide tutti, anche se qualche coppia ne ha uno: 6, 10 e 15 hanno MCD 1, ma 6 e 10 sono entrambi pari.
A cosa serve il MCD nella pratica?
Serve a ridurre una frazione ai minimi termini (36/60 diventa 3/5 dividendo per 12), a semplificare un rapporto e a dividere in parti uguali senza avanzi, per esempio per trovare il lato della piastrella quadrata più grande che copre un pavimento di 360 cm per 240 cm: 120 cm.
Che cosa succede se i numeri sono uguali o uno divide l’altro?
Il MCD è il numero più piccolo: MCD(7, 7) = 7 e MCD(3, 6) = 3, perché il più piccolo divide già il più grande. Il calcolatore accetta numeri interi positivi fino a mille miliardi (1.000.000.000.000).
- Massimo comune divisore (Enciclopedia della Matematica, Treccani)
- Massimo comun divisore (Enciclopedia on line, Treccani)
- Algoritmo di Euclide (Wikipedia)