Massimo comune divisore e minimo comune multiplo
Uno sciame di magicicada in volo
Cos’è il massimo comune divisore (MCD)?
Il massimo comune divisore, abbreviato dall’acronimo MCD è, come dice il nome stesso, il più grande divisore possibile in comune tra due o più numeri interi.
Ad esempio, sia 12 che 16 sono divisibili per 2 perché sono entrambi pari, ma 2 non è il più grande divisore comune per entrambi.
Con un rapido calcolo, possiamo infatti verificare che sono anche divisibili per 4, dato che le relative divisioni hanno come risultato numeri interi:
Effettuando ulteriori tentativi, possiamo verificare che non ci sono numeri più grandi di 4 che siano divisori di entrambi. Si dice quindi che 4 è il massimo comune divisore di 12 e 16.
Cercare di calcolare il massimo comune divisore effettuando tentativi è però un metodo inefficace e dispendioso, se abbiamo a che fare con numeri molto grandi.
Il metodo più efficace per effettuare questo calcolo è scomporre in fattori primi i numeri di cui vogliamo calcolare il massimo comune divisore, e moltiplicare tra loro i fattori primi comuni, presi una sola volta, elevati al minimo esponente.
Iniziamo con il fattorizzare entrambi i numeri per individuare i fattori primi comuni. Effettuando una rapida scomposizione in fattori primi otteniamo che:
Notiamo come entrambi i numeri abbiano nella loro fattorizzazione il numero 7, che in entrambi ha esponente 1. Gli altri fattori primi non sono comuni. Questo vuol dire che 7 è il massimo comune divisore per entrambi:
Iniziamo con il fattorizzare entrambi i numeri per individuare i fattori primi comuni. Effettuando una rapida scomposizione in fattori primi otteniamo che:
In questa situazione, entrambi i numeri hanno in comune il numero 2 nella loro fattorizzazione.
Notiamo però come in 12 questo appaia due volte (l’esponente è 2), mentre in 40 appaia tre volte (l’esponente è 3). L’esponente minimo per questo fattore, quindi, è 2.
Per determinare il massimo comune divisore bisogna moltiplicare tra loro i fattori comuni, ovvero che appaiono per entrambi, ma con il minimo esponente. In questo caso l’unico fattore comune è 2, e il suo esponente minimo è 2, quindi:
Iniziamo con il fattorizzare entrambi i numeri per individuare i fattori primi comuni:
I numeri hanno due fattori primi comuni:
- Il primo è il 2. In 270 l’esponente non è indicato, ossia è 1, mentre in 1008 è 4; il minimo esponente è 1, per cui il primo fattore del MCD è 2.
- Il secondo è il 3. In 270 ha esponente 3, mentre in 504 ha esponente 2; il minimo esponente è 2, per cui il secondo fattore del MCD è 3^2.
Moltiplichiamo i fattori trovati: otteniamo 2 \cdot 3^2 = 2 \cdot 4 = 8, quindi:
Se il massimo comune divisore tra due o più numeri è 1, si dice che sono primi tra loro, oppure coprìmi.
Sia il divisore 3 che 5 compaiono in entrambe le fattorizzazioni. Sebbene 5 compaia due volte nella scomposizione di 75, compare una volta sola in quella di 195.
Pertanto:
Ricordiamo che per divisore intendiamo un numero tale che, quando il numero dato è diviso per esso, il risultato è un numero intero. Infatti si ha:
Cos’è il minimo comune multiplo (mcm)?
Il minimo comune multiplo, abbreviato dall’acronimo mcm, è il più piccolo multiplo comune tra due o più numeri interi.
Proviamo ad esempio a calcolare il minimo comune multiplo tra 10 e 15. Per definizione, dobbiamo trovare il più piccolo dei multipli comuni, quindi iniziamo elencando i multipli dei due numeri, fino a trovarne qualcuno in comune:
Multipli di 10 sono 10 stesso, 20, 30, 40, 50, 60, 70, 80, 90 e così via.
Multipli di 15 sono 15 stesso, 30, 45, 60, 75, 90 e così via.
Notiamo che il primo multiplo in comune che appare in queste due sequenze è 30. Altri multipli in comune sono 60 e 90 (e ne avremmo trovati altri se avessimo proseguito), ma noi stiamo cercando il più piccolo. Pertanto 30 è il minimo comune multiplo per 10 e 15.
Calcolare multipli di due o più numeri fino a incontrarne uno in comune per entrambi è un’operazione che può richiedere molto tempo.
Il metodo più efficace per effettuare questo calcolo è scomporre in fattori primi i numeri di cui vogliamo calcolare il minimo comune multiplo, e moltiplicare tra loro i fattori comuni e non comuni, presi una sola volta, elevati al massimo esponente.
Iniziamo con il fattorizzare entrambi i numeri per individuare i fattori primi. Effettuando una rapida scomposizione in fattori primi otteniamo che:
Per individuare il minimo comune multiplo, dobbiamo considerare i fattori comuni e non comuni, presi una sola volta, ma stavolta con l’esponente più grande. In totale i fattori primi dei due numeri, sia quelli comuni che quelli non comuni, sono i seguenti:
- 2 è in comune; ha esponente 1 per entrambi i numeri di partenza, per cui il suo massimo esponente è appunto 1.
- 3 è in comune; ha esponente 2 per 18, e ha esponente 1 per 30, per cui il suo massimo esponente è 2.
- 5 è divisore solo di 30.
Ne deduciamo che il minimo comune multiplo, abbreviato con mcm, è:
Questo vuol dire che 90 è il numero più piccolo possibile che sia divisibile sia per 18 che per 30.
Consideriamo ora il prodotto di tutti i fattori presi una sola volta con l’esponente più grande. La soluzione è:
Un’utile proprietà
Esiste un ulteriore metodo di eseguire il calcolo del massimo comune divisore se abbiamo già calcolato il minimo comune multiplo, o viceversa. Possiamo infatti sfruttare queste relazioni:
In un esempio precedente, abbiamo già calcolato mcm(10, 1 5) = 30.
Calcoliamo ora il prodotto a \cdot b, ovvero 10 \cdot 15 = 150.
Sfruttando la prima proprietà appena enunciata, possiamo calcolare che il massimo comune divisore tra i due numeri è:
Proviamo a usare il metodo standard per calcolare il MCD tra i due numeri. Scomponendoli in fattori primi otteniamo:
Notiamo che l’unico fattore comune, elevato a 1 in entrambi i numeri, è 5. Quindi il minimo comune multiplo è 5, che è lo stesso risultato che abbiamo ottenuto applicando la proprietà.
Esercizi
Come la matematica ha aiutato l’evoluzione delle cicale?
La magicicada vive la maggior parte della sua vita sottoterra sotto forma di ninfa, ma, passato un certo periodo, emerge per accoppiarsi e depositare le uova. Delle 7 specie di magicicada finora scoperte, 4 restano sottoterra per 13 anni, mentre le altre 3 restano sottoterra per 17 anni.
Ogni quanti anni si ritroverebbero due popolazioni di magicicada di specie diverse a dover competere per le risorse e la sopravvivenza durante il periodo di accoppiamento? La risposta è proprio il mcm(13, 17) = 13 \cdot 17 = 221, ovvero si incontrerebbero ogni 221 anni!
Notiamo infine come sia 13 che 17 siano numeri primi, che per definizione sono divisibili solo per 1 o per se stessi. In particolare non hanno fattori primi in comune: è per questo che il loro minimo comune multiplo coincide col loro prodotto.
Scomposizione in fattori primi
Scomporre un numero in fattori primi significa trovare quei numeri primi che, moltiplicati tra loro, danno come risultato il numero di partenza. Ad esempio la scomposizione (o fattorizzazione) di 21 è 3 · 7, mentre la scomposizione di 60 è 2 · 2 · 3 · 5 = 22 · 3 · 5 (in quest'ultimo caso si dice che il 2 compare due volte nella scomposizione).Per scomporre un numero in fattori primi spesso si utilizzano delle regole dette criteri di divisibilità, che ci aiutano a individuare, uno alla volta, i numeri primi che fanno parte della scomposizione. Ad esempio, se l'ultima cifra del numero è pari (0, 2, 4, 6, 8), allora il numero è divisibile per 2, mentre se la somma delle sue cifre è divisibile per 3, allora il numero è divisibile per 3.
Per maggiori dettagli, consulta la pagina Numeri primi e fattorizzazione.
Numero primo
Un numero primo è un numero intero maggiore di 1 divisibile solo per 1 e per se stesso.I numeri primi sono infiniti, ma è facile memorizzare i primi dieci: 2, 3, 5, 7, 11, 13, 17, 23, 29, 31.
Divisibilità
Equivalentemente, la relazione si può anche esprimere dicendo che b è divisore di a.
Potenze
L'operazione di moltiplicare un numero per se stesso più volte può essere scritto in maniera più concisa come una potenza. L'esponente indica quante volte il numero è stato moltiplicato per se stesso.8 \cdot 8 \cdot 8 \cdot 8 = 8^4. L'esponente di 8 è 4 poiché 8 è moltiplicato per se stesso quattro volte.
