LezIA|HUB
← Matematica →esercizi m.c.d e M.C.D.
Torna a Lezioni
Lezione Matematica 1ª Superiore

m.c.m. e M.C.D.

Le due operazioni fondamentali tra numeri interi. Dalle definizioni formali alle dimostrazioni, dall'algoritmo di Euclide alle applicazioni pratiche e alla relazione MCD · mcm = a · b.

✓ Definizioni formali ✓ Dimostrazioni ✓ Algoritmo di Euclide ✓ Applicazioni

0Introduzione

Due amici vanno in piscina: Marco ogni 6 giorni, Luca ogni 8 giorni. Oggi si sono incontrati. Tra quanti giorni si rivedranno? E se volessimo dividere 24 caramelle e 36 cioccolatini in sacchetti uguali senza avanzi, quanti sacchetti potremmo fare al massimo?

Il primo problema richiede il minimo comune multiplo, il secondo il Massimo Comune Divisore. Sono due concetti complementari: l'uno cerca il più piccolo che contiene, l'altro il più grande che sta dentro.

💡

Perché è importante? Perché MCD e mcm non sono solo "esercizi": servono per sommare frazioni, semplificare radicali, sincronizzare eventi periodici, ottimizzare risorse. In informatica, la sincronizzazione dei processi e la crittografia RSA poggiano su queste idee.

Cosa imparerai

  • Le definizioni formali di MCD e mcm
  • Come si calcolano con la fattorizzazione
  • La relazione fondamentale MCD · mcm = a · b, con dimostrazione
  • Le proprietà formali di MCD e mcm
  • L'algoritmo di Euclide per il calcolo rapido
  • Come si estendono a più numeri
  • Le applicazioni tipiche
  • Cenni alle strutture algebriche sottostanti

1Definizioni formali

Prima di tutto, definiamo in modo rigoroso di cosa stiamo parlando. Lavoriamo in ℤ, l'insieme degli interi relativi.

# Divisibilità Dati a, b ∈ ℤ con b ≠ 0, diciamo che b | a (b divide a) se esiste q ∈ ℤ tale che a = b · q. # Insieme dei divisori di n Div(n) = { d ∈ ℤ : d | n } # Esempio Div(12) = { ±1, ±2, ±3, ±4, ±6, ±12 }
# Insieme dei multipli di n Mult(n) = { m ∈ ℤ : n | m } = { n · k : k ∈ ℤ } # Esempio Mult(6) = { …, −12, −6, 0, 6, 12, 18, … }
💡

Osservazione: Div(n) è sempre finito (ha al massimo 2·d(n) elementi, dove d(n) è il numero dei divisori positivi). Mult(n) è sempre infinito (basta moltiplicare n per k crescenti).

Cos'è il MCD e cos'è il mcm

🔻 M.C.D.

Il Massimo Comune Divisore di a e b è il più grande intero positivo che divide entrambi.

MCD(a, b) = max { d ∈ ℕ⁺ : d | a e d | b }

🔺 m.c.m.

Il minimo comune multiplo di a e b è il più piccolo intero positivo che è multiplo di entrambi.

mcm(a, b) = min { m ∈ ℕ⁺ : a | m e b | m }
🎯

Differenza di "direzione":

  • Il MCD cerca il più grande che "sta dentro" a entrambi (il massimo di un insieme finito).
  • Il mcm cerca il più piccolo che "contiene" entrambi (il minimo di un insieme infinito).

2Il Massimo Comune Divisore

Il M.C.D. (o gcd, dall'inglese greatest common divisor) di due interi a e b, non entrambi nulli, è il più grande intero positivo che divide entrambi.

🧮 Esempio — MCD(24, 36)
Divisori di 24: ±1, ±2, ±3, ±4, ±6, ±8, ±12, ±24 Divisori di 36: ±1, ±2, ±3, ±4, ±6, ±9, ±12, ±18, ±36 Divisori comuni positivi: 1, 2, 3, 4, 6, 12 Il più grande è 12 Quindi: MCD(24, 36) = 12

Proprietà immediate

  • MCD(a, b) = MCD(b, a) — commutativa
  • MCD(a, 0) = |a| (ogni intero divide 0)
  • MCD(a, a) = |a|
  • MCD(a, 1) = 1 per ogni a
  • Se b | a, allora MCD(a, b) = |b|

Numeri coprimi

Due interi a e b sono coprimi (o primi tra loro) se MCD(a, b) = 1.

# Esempi MCD(8, 15) = 1 (8 = 2³, 15 = 3 · 5, nessun fattore comune) MCD(9, 28) = 1 (9 = 3², 28 = 2² · 7) MCD(14, 21) = 7 (NON sono coprimi)
🎯

Nota importante: essere coprimi non significa essere entrambi primi! 8 e 15 non sono primi ma sono coprimi.

3Calcolo del M.C.D.

Il metodo più usato sfrutta la fattorizzazione in fattori primi e il teorema fondamentale dell'aritmetica.

📐 Regola
Siano a = p₁^α₁ · p₂^α₂ · … · pₖ^αₖ b = p₁^β₁ · p₂^β₂ · … · pₖ^βₖ (con gli stessi primi, eventualmente con esponente 0) Allora: MCD(a, b) = p₁^min(α₁, β₁) · p₂^min(α₂, β₂) · … · pₖ^min(αₖ, βₖ) In parole: prendo i fattori comuni con l'esponente minimo.
🧮 Esempio — MCD(360, 504)
360 = 2³ · 3² · 5 504 = 2³ · 3² · 7 Fattori comuni: 2, 3 Esponente minimo di 2: min(3, 3) = 3 Esponente minimo di 3: min(2, 2) = 2 Il 5 e il 7 non sono comuni → non si prendono MCD(360, 504) = 2³ · 3² = 8 · 9 = 72
🧮 Esempio — MCD(1 080, 1 260, 900)
1 080 = 2³ · 3³ · 5 1 260 = 2² · 3² · 5 · 7 900 = 2² · 3² · 5² Fattori comuni a tutti e tre: 2, 3, 5 min(3, 2, 2) = 2 per il 2 min(3, 2, 2) = 2 per il 3 min(1, 1, 2) = 1 per il 5 MCD(1 080, 1 260, 900) = 2² · 3² · 5 = 4 · 9 · 5 = 180

4Il minimo comune multiplo

Il m.c.m. (o lcm, dall'inglese least common multiple) di due interi positivi a e b è il più piccolo intero positivo che è multiplo di entrambi.

🧮 Esempio — mcm(4, 6)
Multipli di 4: 4, 8, 12, 16, 20, 24, 28, 32, 36, … Multipli di 6: 6, 12, 18, 24, 30, 36, … Multipli comuni: 12, 24, 36, … Il più piccolo è 12 Quindi: mcm(4, 6) = 12

Proprietà immediate

  • mcm(a, b) = mcm(b, a) — commutativa
  • mcm(a, 1) = a per ogni a
  • mcm(a, a) = a
  • Se a | b, allora mcm(a, b) = |b| (il più grande è multiplo del più piccolo)
  • Se a e b sono coprimi, mcm(a, b) = a · b
💡

Perché "minimo"? Perché l'insieme dei multipli comuni è infinito, quindi non ha un massimo, ma ha un minimo (positivo). Il mcm è il "punto di partenza" comune a tutte le sequenze di multipli.

5Calcolo del m.c.m.

📐 Regola
Siano a = p₁^α₁ · p₂^α₂ · … · pₖ^αₖ b = p₁^β₁ · p₂^β₂ · … · pₖ^βₖ Allora: mcm(a, b) = p₁^max(α₁, β₁) · p₂^max(α₂, β₂) · … · pₖ^max(αₖ, βₖ) In parole: prendo TUTTI i fattori (comuni e non) con l'esponente massimo.
🧮 Esempio — mcm(360, 504)
360 = 2³ · 3² · 5 504 = 2³ · 3² · 7 Tutti i fattori: 2, 3, 5, 7 Esponente massimo di 2: max(3, 3) = 3 Esponente massimo di 3: max(2, 2) = 2 Esponente massimo di 5: max(1, 0) = 1 Esponente massimo di 7: max(0, 1) = 1 mcm(360, 504) = 2³ · 3² · 5 · 7 = 8 · 9 · 5 · 7 = 2 520
🔍

Attenzione: nel mcm si prendono anche i fattori che compaiono in uno solo dei numeri. Nel MCD invece solo quelli comuni a tutti.

6Relazione MCD · mcm = a · b

Tra MCD e mcm esiste una delle relazioni più eleganti dell'aritmetica:

📐 Teorema
Per ogni coppia di interi positivi a e b: MCD(a, b) · mcm(a, b) = a · b Equivalentemente: mcm(a, b) = (a · b) / MCD(a, b)
🧮 Dimostrazione (con fattorizzazione)
Sia a = ∏ pᵢ^αᵢ, b = ∏ pᵢ^βᵢ (prodotto sui primi che compaiono in a o b). Per definizione: MCD(a, b) = ∏ pᵢ^min(αᵢ, βᵢ) mcm(a, b) = ∏ pᵢ^max(αᵢ, βᵢ) Allora: MCD(a, b) · mcm(a, b) = ∏ pᵢ^(min(αᵢ, βᵢ) + max(αᵢ, βᵢ)) Ora, per ogni coppia di numeri reali x, y: min(x, y) + max(x, y) = x + y Quindi: MCD(a, b) · mcm(a, b) = ∏ pᵢ^(αᵢ + βᵢ) = ∏ pᵢ^αᵢ · ∏ pᵢ^βᵢ = a · b ✓
🧮 Verifica numerica
a = 24, b = 36 MCD(24, 36) = 12 mcm(24, 36) = 72 MCD · mcm = 12 · 72 = 864 a · b = 24 · 36 = 864 864 = 864 ✓
🚀

Utilità pratica: conoscendo MCD e uno dei due numeri, si calcola il mcm con una sola moltiplicazione e divisione, senza dover rifare la fattorizzazione.

⚠️

Attenzione: la relazione MCD · mcm = a · b vale solo per due numeri! Con tre o più numeri non c'è una formula così semplice.

Esempio: MCD(2, 3, 4) = 1, mcm(2, 3, 4) = 12, ma 1 · 12 = 12 ≠ 2 · 3 · 4 = 24.

7Proprietà formali

MCD e mcm godono di proprietà eleganti, che permettono di semplificare i calcoli e di estenderli a più numeri.

ProprietàMCDmcm
Commutativa MCD(a, b) = MCD(b, a) mcm(a, b) = mcm(b, a)
Associativa MCD(a, MCD(b, c)) = MCD(MCD(a, b), c) mcm(a, mcm(b, c)) = mcm(mcm(a, b), c)
Idempotenza MCD(a, a) = a mcm(a, a) = a
Elemento neutro MCD(a, 0) = a mcm(a, 1) = a
Assorbimento MCD(a, mcm(a, b)) = a mcm(a, MCD(a, b)) = a
Distributiva (rispetto all'altra) MCD(a, mcm(b, c)) = mcm(MCD(a, b), MCD(a, c)) mcm(a, MCD(b, c)) = MCD(mcm(a, b), mcm(a, c))
Moltiplicazione MCD(ka, kb) = k · MCD(a, b) mcm(ka, kb) = k · mcm(a, b)
🔗

Associatività → più numeri: grazie alla proprietà associativa, possiamo calcolare MCD e mcm di più di due numeri applicandoli in modo iterativo:

MCD(a, b, c) = MCD(MCD(a, b), c)

mcm(a, b, c) = mcm(mcm(a, b), c)

8Algoritmo di Euclide

Quando i numeri sono grandi, fattorizzarli è lento. L'algoritmo di Euclide (300 a.C. circa) calcola il MCD con una sequenza di divisioni con resto, senza mai fattorizzare.

📐 Idea dell'algoritmo
Siano a, b ∈ ℕ⁺ con a ≥ b. Dividiamo a per b con resto: a = b · q + r, 0 ≤ r < b Allora: MCD(a, b) = MCD(b, r) Ripetiamo il procedimento con la coppia (b, r). L'ultimo resto non nullo è il MCD.
🧮 Dimostrazione
Basta mostrare che MCD(a, b) = MCD(b, r). (⊆) Se d | a e d | b, allora d | (a − b·q) = r. Quindi d è anche divisore di r. Quindi ogni divisore comune di a e b è anche divisore comune di b e r. (⊇) Viceversa, se d | b e d | r, allora d | (b·q + r) = a. Quindi ogni divisore comune di b e r è anche divisore comune di a e b. I due insiemi di divisori comuni coincidono. Quindi anche il loro massimo coincide: MCD(a, b) = MCD(b, r). ✓
🧮 Esempio — MCD(1 078, 462)
1 078 = 462 · 2 + 154 (resto 154) 462 = 154 · 3 + 0 (resto 0 → stop) Ultimo resto non nullo: 154 MCD(1 078, 462) = 154 # Quanti passi abbiamo fatto? Solo 2! Fattorizzare 1 078 = 2 · 7² · 11 e 462 = 2 · 3 · 7 · 11 sarebbe stato più lungo.
⚡

Efficienza: l'algoritmo di Euclide richiede un numero di passi logaritmico nella dimensione dei numeri. È uno degli algoritmi più efficienti conosciuti, ed è ancora oggi usato nei calcolatori per il calcolo del MCD.

9MCD e mcm di più numeri

Come calcolare MCD e mcm di 3, 4 o più numeri? Le regole si estendono naturalmente.

MCD di più numeri

📐 Regola
Il MCD di più numeri è il prodotto dei fattori primi comuni a TUTTI i numeri, ciascuno preso con il suo esponente MINIMO. MCD(a, b, c) = ∏ pᵢ^min(αᵢ, βᵢ, γᵢ)
🧮 Esempio — MCD(36, 60, 84)
36 = 2² · 3² 60 = 2² · 3 · 5 84 = 2² · 3 · 7 Fattori comuni a tutti: 2, 3 min(2, 2, 2) = 2 per il 2 min(2, 1, 1) = 1 per il 3 5 e 7 non sono comuni a tutti → esclusi MCD(36, 60, 84) = 2² · 3 = 4 · 3 = 12

mcm di più numeri

📐 Regola
Il mcm di più numeri è il prodotto di TUTTI i fattori primi (comuni e non), ciascuno preso con il suo esponente MASSIMO. mcm(a, b, c) = ∏ pᵢ^max(αᵢ, βᵢ, γᵢ)
🧮 Esempio — mcm(12, 18, 20)
12 = 2² · 3 18 = 2 · 3² 20 = 2² · 5 Tutti i fattori: 2, 3, 5 max(2, 1, 2) = 2 per il 2 max(1, 2, 0) = 2 per il 3 max(0, 0, 1) = 1 per il 5 mcm(12, 18, 20) = 2² · 3² · 5 = 4 · 9 · 5 = 180
⚠️

Attenzione: la relazione MCD · mcm = a · b non si estende a più numeri. Per tre numeri, in generale MCD(a,b,c) · mcm(a,b,c) ≠ a · b · c.

10Applicazioni pratiche

MCD e mcm non sono solo "giochi" matematici: sono strumenti utili in tanti contesti.

🔔 Sincronizzazione di eventi

Due eventi periodici (bus, campanelli, semafori) si ritrovano insieme dopo un tempo pari al mcm dei loro periodi.

✂️ Divisioni in parti uguali

Per dividere due quantità in gruppi uguali più grandi possibili (senza avanzi) si usa il MCD.

➗ Somma di frazioni

Per sommare due frazioni si porta tutto al mcm dei denominatori, che è il più piccolo denominatore comune.

🔢 Semplificazione di frazioni

Per ridurre una frazione ai minimi termini si divide numeratore e denominatore per il loro MCD.

📐 Radici

Per semplificare espressioni con radici di indici diversi si usa il mcm degli indici.

🔐 Crittografia RSA

La sicurezza di RSA si basa sull'uso di numeri che sono prodotto di due primi coprimi molto grandi (e quindi sul MCD).

🎯

Come riconoscere quale usare?

  • Se il problema chiede "quando si ritrovano insieme" o "il più piccolo che contiene entrambi" → mcm
  • Se chiede "il più grande che sta in entrambi" o "dividere in gruppi uguali" → MCD

11Cenni alle strutture algebriche

MCD e mcm non sono operazioni "qualsiasi": hanno una struttura algebrica precisa, che si ritrova in molti altri contesti matematici.

📐 Il reticolo dei divisori
Ordiniamo i divisori di un numero n con la relazione di divisibilità: d₁ ≤ d₂ se e solo se d₁ | d₂ Con questa relazione, l'insieme dei divisori di n forma un reticolo distributivo: • MCD(a, b) è l'estremo inferiore (il più grande divisore comune) • mcm(a, b) è l'estremo superiore (il più piccolo multiplo comune) Le proprietà viste prima (associativa, commutativa, assorbimento, distributiva) sono esattamente gli assiomi dei reticoli distributivi.
📐 Nella teoria degli anelli
Nell'anello degli interi ℤ, MCD e mcm corrispondono a: • MCD(a, b) = generatore dell'ideale (a) + (b) • mcm(a, b) = generatore dell'ideale (a) ∩ (b) In un dominio a fattorizzazione unica (UFD) come ℤ, esistono sempre MCD e mcm.
🎓

Perché ci interessa? Perché capire la struttura di MCD e mcm ci permette di estenderli ad altri contesti (polinomi, numeri complessi, anelli a fattorizzazione unica) e di riconoscere quando le stesse proprietà valgono. È il cuore dell'algebra moderna.

12Esempi svolti

Esempio 1 — MCD con fattorizzazione

Calcola MCD(504, 1 320).

Passo 1 → Fattorizzo i due numeri 504 = 2³ · 3² · 7 1 320 = 2³ · 3 · 5 · 11 Passo 2 → Fattori comuni: 2, 3 min(3, 3) = 3 per il 2 min(2, 1) = 1 per il 3 MCD(504, 1 320) = 2³ · 3 = 8 · 3 = 24

Esempio 2 — mcm con fattorizzazione

Calcola mcm(504, 1 320).

Passo 1 → Uso la stessa fattorizzazione 504 = 2³ · 3² · 7 1 320 = 2³ · 3 · 5 · 11 Passo 2 → Tutti i fattori: 2, 3, 5, 7, 11 max(3, 3) = 3 per il 2 max(2, 1) = 2 per il 3 max(0, 1) = 1 per il 5 max(1, 0) = 1 per il 7 max(0, 1) = 1 per l'11 mcm(504, 1 320) = 2³ · 3² · 5 · 7 · 11 = 8 · 9 · 5 · 7 · 11 = 27 720 # Verifica con la relazione: MCD · mcm = 24 · 27 720 = 665 280 a · b = 504 · 1 320 = 665 280 ✓

Esempio 3 — MCD con algoritmo di Euclide

Calcola MCD(45 045, 20 020).

Passo 1 → Divisione con resto 45 045 = 20 020 · 2 + 5 005 Passo 2 → Continuo con (20 020, 5 005) 20 020 = 5 005 · 4 + 0 Passo 3 → Ultimo resto non nullo MCD(45 045, 20 020) = 5 005 # Velocissimo! Fattorizzare sarebbe stato molto più lento.

Esempio 4 — Problema con mcm

Il bus A passa ogni 15 minuti, il bus B ogni 20 minuti. Sono passati insieme alle 8:00. Quando passeranno di nuovo insieme?

Passo 1 → Cerco il mcm dei due periodi 15 = 3 · 5 20 = 2² · 5 mcm(15, 20) = 2² · 3 · 5 = 4 · 3 · 5 = 60 minuti Passo 2 → Aggiungo all'ora iniziale 8:00 + 60 min = 9:00 Risposta: si ritroveranno insieme alle 9:00.

Esempio 5 — Problema con MCD

Vuoi dividere 72 rose e 48 tulipani in mazzi uguali con la stessa composizione. Qual è il numero massimo di mazzi?

Passo 1 → Cerco il MCD dei due numeri 72 = 2³ · 3² 48 = 2⁴ · 3 MCD(72, 48) = 2³ · 3 = 8 · 3 = 24 Passo 2 → Verifica Ogni mazzo avrà: 72 : 24 = 3 rose, 48 : 24 = 2 tulipani Risposta: al massimo 24 mazzi.

Esempio 6 — Somma di frazioni con mcm

Calcola 1/12 + 5/18.

Passo 1 → Trovo il mcm dei denominatori 12 = 2² · 3 18 = 2 · 3² mcm(12, 18) = 2² · 3² = 4 · 9 = 36 Passo 2 → Porta le frazioni a denominatore 36 1/12 = 3/36 (moltiplico per 3) 5/18 = 10/36 (moltiplico per 2) Passo 3 → Sommo 1/12 + 5/18 = 3/36 + 10/36 = 13/36

13Giochi interattivi

Mettiti alla prova con questi giochi rapidi su MCD e mcm!

🎯 MCD con fattorizzazione

Qual è il MCD di 48 e 180?

➕ mcm con fattorizzazione

Qual è il mcm di 12 e 18?

⚡ Relazione fondamentale

Se MCD(a, b) = 6 e mcm(a, b) = 72, quanto vale a · b?

🔢 Coprimi

Qual è il MCD di 8 e 15?

🎨 Problema con MCD

Vuoi dividere 60 caramelle e 45 cioccolatini in scatole uguali. Quante scatole al massimo?

🔔 Problema con mcm

Due fari lampeggiano ogni 4 s e ogni 6 s. Dopo quanti secondi lampeggiano insieme?