MCD (algoritmo euclideo) e mcm
Una cartolibreria ha 180 quaderni e 216 penne e vuole preparare dei pacchi tutti uguali, senza avanzi. Quanti pacchi può fare al massimo? E se due autobus partono insieme dal capolinea, ma tornano a intervalli diversi, quando si rincontreranno? Sono due problemi di aspetto diverso, ma si risolvono con due strumenti: il MCD e il mcm.
Divisori comuni e multipli comuni
Scrivere tutti i divisori di due numeri e cercare quelli in comune funziona, ma è lungo. Vediamo prima che cosa cerchiamo.
Esempio con $12$ e $18$:
-
divisori di $12$: $1, 2, 3, 4, 6, 12$
-
divisori di $18$: $1, 2, 3, 6, 9, 18$
-
divisori comuni: $1, 2, 3, 6$, quindi $\text{MCD}(12, 18) = 6$.
Multipli di $12$: $12, 24, 36, 48, \dots$ Multipli di $18$: $18, 36, 54, \dots$ Il primo in comune è $36$, quindi $\text{mcm}(12, 18) = 36$.
Due numeri con $\text{MCD} = 1$ si dicono primi tra loro (per esempio $8$ e $15$, anche se nessuno dei due è primo).
Scomponi in fattori primi i numeri $84$ e $126$ e calcola: a) $\text{MCD}(84, 126)$ b) $\text{mcm}(84, 126)$
Scomponi in fattori primi i numeri $84$ e $126$ e calcola:
- a) $\text{MCD}(84, 126)$
- b) $\text{mcm}(84, 126)$
Con la scomposizione in fattori primi
Per numeri grandi si scompongono in fattori primi. Un divisore comune può contenere solo fattori presenti in entrambi i numeri; un multiplo comune deve contenere tutti i fattori di entrambi.
Calcola $\text{MCD}$ e $\text{mcm}$ dei tre numeri $12$, $18$ e $30$.
Calcola $\text{MCD}$ e $\text{mcm}$ dei tre numeri $12$, $18$ e $30$.
Determina il più piccolo numero naturale maggiore di $5$ che, diviso per $8$, $12$ e $15$, dà sempre resto $5$. Giustifica il procedimento e indica poi quale è il…
Determina il più piccolo numero naturale maggiore di $5$ che, diviso per $8$, $12$ e $15$, dà sempre resto $5$. Giustifica il procedimento e indica poi quale è il successivo numero con la stessa proprietà.
L'algoritmo euclideo
Scomporre numeri grandi, come $1.071$ e $462$, può essere faticoso. Euclide (circa 300 a.C.) inventò un metodo che usa solo divisioni.
Perché? Ogni divisore comune di $a$ e $b$ divide anche $r = a - bq$. Viceversa, ogni divisore comune di $b$ e $r$ divide $a = bq + r$. Le due coppie hanno quindi gli stessi divisori comuni e dunque lo stesso massimo.
Si ripete la divisione finché il resto è $0$: l'ultimo resto diverso da zero è il MCD.
Applica l'algoritmo euclideo delle divisioni successive per calcolare $\text{MCD}(252, 198)$. Scrivi tutte le divisioni con quoziente e resto.
Applica l'algoritmo euclideo delle divisioni successive per calcolare $\text{MCD}(252, 198)$. Scrivi tutte le divisioni con quoziente e resto.
Dimostra che, se $a>b$ e $a = bq + r$ con $0 \le r < b$, allora $\text{MCD}(a,b)=\text{MCD}(b,r)$. Usa poi questo risultato per giustificare l'algoritmo euclideo e…
Dimostra che, se $a>b$ e $a = bq + r$ con $0 \le r < b$, allora $\text{MCD}(a,b)=\text{MCD}(b,r)$. Usa poi questo risultato per giustificare l'algoritmo euclideo e calcolare $\text{MCD}(1.071, 462)$.
Problemi con MCD e mcm
Come riconoscere quale strumento serve?
-
Si divide in parti uguali, si cerca la parte più grande, si taglia o si raggruppa: MCD.
-
Si cerca quando due eventi periodici coincidono di nuovo, o una lunghezza minima da ottenere ripetendo: mcm.
Nei problemi di piastrelle quadrate su un rettangolo, il lato massimo è il MCD delle due misure (nella stessa unità, per esempio in centimetri); il numero di piastrelle si trova dividendo l'area del pavimento per quella di una piastrella.
Una cartolibreria di Bologna ha $180$ quaderni e $216$ penne. Vuole confezionare dei pacchi tutti uguali, senza avanzi, usando tutti gli articoli. a) Qual è il massimo…
Una cartolibreria di Bologna ha $180$ quaderni e $216$ penne. Vuole confezionare dei pacchi tutti uguali, senza avanzi, usando tutti gli articoli.
- a) Qual è il massimo numero di pacchi che può preparare?
- b) Quanti quaderni e quante penne contiene ciascun pacco?
Due autobus partono insieme alle $7{:}00$ dalla stazione di Firenze Santa Maria Novella. Il primo torna in stazione ogni $24$ minuti, il secondo ogni $36$ minuti. a)…
Due autobus partono insieme alle $7{:}00$ dalla stazione di Firenze Santa Maria Novella. Il primo torna in stazione ogni $24$ minuti, il secondo ogni $36$ minuti.
- a) Dopo quanti minuti si ritroveranno in stazione contemporaneamente per la prima volta?
- b) A che ora accadrà?
- c) Quante volte, tra le $7{:}00$ e le $13{:}00$ (escluse le $7{:}00$, incluse le $13{:}00$), si troveranno insieme in stazione?
Un pavimento rettangolare di $4,20 \text{ m}$ per $3,00 \text{ m}$ deve essere ricoperto con piastrelle quadrate tutte uguali, senza tagli e senza sovrapposizioni, con…
Un pavimento rettangolare di $4,20 \text{ m}$ per $3,00 \text{ m}$ deve essere ricoperto con piastrelle quadrate tutte uguali, senza tagli e senza sovrapposizioni, con il lato più grande possibile (in numero intero di centimetri).
- a) Quanto misura il lato di ogni piastrella?
- b) Quante piastrelle servono?
Ragionare con le proprietà
Se conosci MCD e mcm di due numeri puoi ricostruirli. Poniamo $a = 12m$ e $b = 12n$, con $m$ e $n$ primi tra loro (dopo aver diviso per il MCD non restano fattori comuni). Allora $\text{mcm} = 12mn$.
Per i problemi del tipo «il numero che diviso per $8$, $12$, $15$ dà resto $5$»: togliendo $5$ si ottiene un multiplo comune di $8$, $12$ e $15$. Il più piccolo è il mcm, poi si aggiunge $5$.
Siano $a$ e $b$ due numeri naturali con $\text{MCD}(a,b)=12$ e $\text{mcm}(a,b)=180$. a) Dimostra che $a \cdot b = 2.160$. b) Trova tutte le coppie $(a,b)$ con $a<b$ che…
Siano $a$ e $b$ due numeri naturali con $\text{MCD}(a,b)=12$ e $\text{mcm}(a,b)=180$.
- a) Dimostra che $a \cdot b = 2.160$.
- b) Trova tutte le coppie $(a,b)$ con $a
In sintesi
-
$\text{MCD}$: il maggiore dei divisori comuni; $\text{mcm}$: il minore dei multipli comuni diversi da zero.
-
Con la scomposizione: MCD = fattori comuni con esponente minimo; mcm = fattori comuni e non comuni con esponente massimo.
-
$\text{MCD}(a, b) \cdot \text{mcm}(a, b) = a \cdot b$ (solo per due numeri).
-
Algoritmo euclideo: da $a = bq + r$ segue $\text{MCD}(a, b) = \text{MCD}(b, r)$; il MCD è l'ultimo resto diverso da zero.
-
Problemi: parti uguali e più grandi possibili → MCD; coincidenze periodiche → mcm.
-
Vuoi sapere perché la cartolibreria fa $\text{MCD}(180, 216) = 36$ pacchi? Perché $36$ è il massimo numero che divide entrambe le quantità.