Algoritmo euclideo, MCD e mcm
Due autobus partono insieme dal capolinea. Uno torna ogni 36 minuti, l'altro ogni 48. Dopo quanto tempo si ritrovano di nuovo insieme? E se dobbiamo dividere 180 cannoli e 252 bignè in vassoi identici, quanti vassoi possiamo fare al massimo? Sono due problemi diversi, ma si risolvono con lo stesso strumento: divisori e multipli comuni.
Divisori, multipli e fattori primi
Un numero naturale $a$ è multiplo di $b$ (e $b$ è divisore di $a$) se la divisione $a : b$ ha resto $0$. Un numero è primo se ha solo due divisori: $1$ e se stesso.
Ogni numero naturale maggiore di $1$ si scrive in un solo modo come prodotto di numeri primi (a meno dell'ordine): è la scomposizione in fattori primi. Si dividono i numeri per i primi $2, 3, 5, 7, \dots$ finché si arriva a $1$.
Dalla scomposizione si ricavano subito:
-
MCD = prodotto dei fattori primi comuni, ciascuno col minimo esponente;
-
mcm = prodotto di tutti i fattori primi, comuni e non comuni, ciascuno col massimo esponente.
Scomponi in fattori primi i numeri $84$ e $126$. Poi calcola $\text{MCD}(84, 126)$ e $\text{mcm}(84, 126)$.
Scomponi in fattori primi i numeri $84$ e $126$. Poi calcola $\text{MCD}(84, 126)$ e $\text{mcm}(84, 126)$.
L'algoritmo euclideo
Scomporre numeri grandi, come $1.071$ o $4.199$, è faticoso. Euclide trovò un metodo che usa solo divisioni con resto.
Ricorda che $a = b \cdot q + r$ con $0 \le r < b$. Se un numero $d$ divide sia $a$ sia $b$, divide anche $r = a - b \cdot q$. Viceversa, se $d$ divide $b$ e $r$, divide anche $a = bq + r$. Quindi $a, b$ e $b, r$ hanno gli stessi divisori comuni:
$$\text{MCD}(a, b) = \text{MCD}(b, r)$$Si ripete: la coppia diventa sempre più piccola finché il resto è $0$. L'ultimo resto diverso da zero è il MCD.
Applica l'algoritmo euclideo delle divisioni successive per calcolare $\text{MCD}(252, 105)$. Scrivi tutte le divisioni con quoziente e resto.
Applica l'algoritmo euclideo delle divisioni successive per calcolare $\text{MCD}(252, 105)$. Scrivi tutte le divisioni con quoziente e resto.
Calcola con l'algoritmo euclideo $\text{MCD}(91, 35)$ e stabilisci se i numeri $91$ e $35$ sono primi tra loro.
Calcola con l'algoritmo euclideo $\text{MCD}(91, 35)$ e stabilisci se i numeri $91$ e $35$ sono primi tra loro.
Siano $a$ e $b$ due numeri naturali con $a>b$. a) Dimostra che ogni divisore comune di $a$ e $b$ divide anche il resto $r$ della divisione di $a$ per $b$. b) Deduci che…
Siano $a$ e $b$ due numeri naturali con $a>b$.
- a) Dimostra che ogni divisore comune di $a$ e $b$ divide anche il resto $r$ della divisione di $a$ per $b$.
- b) Deduci che $\text{MCD}(a,b)=\text{MCD}(b,r)$ e spiega perché ciò giustifica l'algoritmo euclideo.
Il mcm e la relazione con il MCD
Per due numeri naturali $a$ e $b$ vale
$$\text{MCD}(a, b) \cdot \text{mcm}(a, b) = a \cdot b$$Il perché: i fattori comuni, presi col minimo esponente nel MCD e col massimo nel mcm, insieme danno esattamente tutti i fattori di $a$ e di $b$.
Quindi, dopo aver trovato il MCD con Euclide, il mcm è
$$\text{mcm}(a, b) = \frac{a \cdot b}{\text{MCD}(a, b)}$$Calcola con l'algoritmo euclideo $\text{MCD}(1.071, 462)$ e ricava $\text{mcm}(1.071, 462)$ usando la relazione $\text{MCD}(a,b)\cdot\text{mcm}(a,b)=a\cdot b$. Verifica…
Calcola con l'algoritmo euclideo $\text{MCD}(1.071, 462)$ e ricava $\text{mcm}(1.071, 462)$ usando la relazione $\text{MCD}(a,b)\cdot\text{mcm}(a,b)=a\cdot b$. Verifica poi il risultato con la scomposizione in fattori primi.
Due numeri naturali hanno $\text{MCD}=12$ e $\text{mcm}=360$. Uno dei due è $72$. a) Trova l'altro numero. b) Trova tutte le coppie $(a,b)$ di numeri naturali con $a<b$,…
Due numeri naturali hanno $\text{MCD}=12$ e $\text{mcm}=360$. Uno dei due è $72$.
- a) Trova l'altro numero.
- b) Trova tutte le coppie $(a,b)$ di numeri naturali con $a
Problemi con MCD e mcm
Come si capisce quale dei due usare?
-
Si chiede di dividere in parti uguali, di trovare il massimo numero di gruppi, o la misura più grande che sta un numero esatto di volte in due lunghezze: serve il MCD.
-
Si chiede quando due eventi periodici coincidono, o il primo momento in cui si ripetono insieme: serve il mcm.
Quando le misure hanno la virgola, convertile in numeri interi (per esempio da metri a centimetri) prima di calcolare. Se vuoi la piastrella quadrata più grande per un pavimento $a \times b$, il lato è il $\text{MCD}$ delle due misure. Ogni altro lato possibile è un divisore comune, e ogni divisore comune di due numeri divide il loro MCD.
Una pasticceria di Bologna ha $180$ cannoli e $252$ bignè. Vuole preparare vassoi identici, ciascuno con lo stesso numero di cannoli e lo stesso numero di bignè, senza…
Una pasticceria di Bologna ha $180$ cannoli e $252$ bignè. Vuole preparare vassoi identici, ciascuno con lo stesso numero di cannoli e lo stesso numero di bignè, senza avanzi.
- a) Qual è il massimo numero di vassoi che può preparare?
- b) Quanti cannoli e quanti bignè contiene ciascun vassoio?
Due autobus partono insieme alle $6{:}00$ dal capolinea di Firenze. Il primo ritorna al capolinea ogni $36$ minuti, il secondo ogni $48$ minuti. a) Dopo quanti minuti si…
Due autobus partono insieme alle $6{:}00$ dal capolinea di Firenze. Il primo ritorna al capolinea ogni $36$ minuti, il secondo ogni $48$ minuti.
- a) Dopo quanti minuti si ritrovano insieme al capolinea per la prima volta?
- b) A che ora accade?
- c) Quante volte si ritrovano insieme tra le $6{:}00$ e le $18{:}00$ (esclusa la partenza)?
Un pavimento rettangolare di $4,95\text{ m}\times 3,30\text{ m}$ deve essere ricoperto con piastrelle quadrate intere, tutte uguali, senza tagli. a) Determina il lato…
Un pavimento rettangolare di $4,95\text{ m}\times 3,30\text{ m}$ deve essere ricoperto con piastrelle quadrate intere, tutte uguali, senza tagli.
- a) Determina il lato massimo (in cm) delle piastrelle.
- b) Quante piastrelle servono?
- c) Giustifica perché ogni lato valido per le piastrelle è un divisore del MCD delle due misure espresse in cm.
Vuoi altri esercizi? Eccone alcuni scelti per te.
In sintesi
-
Con la scomposizione in fattori primi: MCD = fattori comuni col minimo esponente; mcm = tutti i fattori col massimo esponente.
-
Algoritmo euclideo: $a = b q + r$ e $\text{MCD}(a, b) = \text{MCD}(b, r)$; si ripete fino a resto $0$ e l'ultimo resto non nullo è il MCD.
-
$\text{MCD}(a, b) \cdot \text{mcm}(a, b) = a \cdot b$.
-
Se $\text{MCD} = 1$ i numeri sono primi tra loro.
-
MCD per dividere in parti uguali (massimo numero di gruppi); mcm per eventi che si ripetono e coincidono.
Vuoi tornare ai due autobus? Con $36$ e $48$ minuti il mcm è $144$: si ritrovano dopo $144$ minuti, cioè $2$ ore e $24$ minuti.