Il Massimo Comun Divisore (MCD) è uno dei concetti fondamentali dell’aritmetica e dell’algebra. Trovare il MCD tra due o più numeri è un’operazione essenziale per semplificare le frazioni, risolvere problemi di divisibilità e affrontare numerose applicazioni pratiche. In questa guida completa spieghiamo cos’è il MCD, come calcolarlo con diversi metodi e quando utilizzarlo.

Pronto a fare i calcoli?

Usa il Calcolatore Gratuito

Cos’è il Massimo Comun Divisore (MCD)

Il Massimo Comun Divisore di due o più numeri interi è il più grande numero intero positivo che divide tutti i numeri dati senza resto. In altre parole, è il divisore più grande che i numeri hanno in comune.

Definizione formale: Dati due numeri interi a e b (non entrambi nulli), il MCD(a, b) è il più grande intero positivo d tale che d divide a e d divide b.

Ad esempio, i divisori di 12 sono: 1, 2, 3, 4, 6, 12. I divisori di 18 sono: 1, 2, 3, 6, 9, 18. I divisori comuni sono: 1, 2, 3, 6. Il massimo tra questi è 6, quindi MCD(12, 18) = 6.

Proprietà Fondamentali del MCD

  • Commutatività: MCD(a, b) = MCD(b, a)
  • Associatività: MCD(a, b, c) = MCD(MCD(a, b), c)
  • MCD con 0: MCD(a, 0) = |a| per ogni intero a diverso da zero
  • MCD con 1: MCD(a, 1) = 1 per ogni intero a
  • Numeri coprimi: se MCD(a, b) = 1, i numeri a e b si dicono coprimi (o primi tra loro)
  • Positività: il MCD è sempre un numero positivo

Metodo 1: Scomposizione in Fattori Primi

Il metodo classico per calcolare il MCD consiste nel scomporre ciascun numero in fattori primi e poi prendere il prodotto dei fattori comuni con l’esponente minore.

Procedimento

  1. Scomporre ciascun numero in fattori primi
  2. Identificare i fattori primi comuni a tutti i numeri
  3. Per ogni fattore comune, prendere quello con l’esponente più piccolo
  4. Moltiplicare tra loro i fattori selezionati

Esempio: MCD(60, 90)

Scomposizione in fattori primi:

  • 60 = 2² x 3 x 5
  • 90 = 2 x 3² x 5

Fattori comuni con esponente minore:

  • 2: presente con esponente 2 e 1 → prendiamo 2¹
  • 3: presente con esponente 1 e 2 → prendiamo 3¹
  • 5: presente con esponente 1 e 1 → prendiamo 5¹

MCD(60, 90) = 2 x 3 x 5 = 30

Esempio: MCD(84, 120, 168)

Scomposizione:

  • 84 = 2² x 3 x 7
  • 120 = 2³ x 3 x 5
  • 168 = 2³ x 3 x 7

Fattori comuni a tutti e tre: 2 (esponente minimo: 2) e 3 (esponente minimo: 1). Il 5 compare solo nel 120 e il 7 non compare nel 120.

MCD(84, 120, 168) = 2² x 3 = 4 x 3 = 12

Metodo 2: Algoritmo di Euclide

L’algoritmo di Euclide è il metodo più elegante ed efficiente per calcolare il MCD di due numeri. Risale al III secolo a.C. (Elementi di Euclide, Libro VII) ed è considerato uno dei più antichi algoritmi matematici ancora in uso.

Principio

L’algoritmo si basa sulla proprietà: MCD(a, b) = MCD(b, a mod b), dove “a mod b” indica il resto della divisione di a per b. Si applica ripetutamente questa proprietà fino a ottenere resto zero.

Procedimento

  1. Dividere il numero maggiore per il minore e calcolare il resto
  2. Sostituire il numero maggiore con il minore e il minore con il resto
  3. Ripetere fino a ottenere resto 0
  4. Il MCD è l’ultimo resto non nullo (ovvero il divisore dell’ultima divisione)

Esempio: MCD(252, 105)

Passo Divisione Quoziente Resto
1 252 ÷ 105 2 42
2 105 ÷ 42 2 21
3 42 ÷ 21 2 0

Il resto è diventato 0, quindi MCD(252, 105) = 21 (l’ultimo divisore).

Esempio: MCD(462, 1071)

Passo Divisione Quoziente Resto
1 1071 ÷ 462 2 147
2 462 ÷ 147 3 21
3 147 ÷ 21 7 0

MCD(462, 1071) = 21

Perché l’Algoritmo di Euclide È Superiore

L’algoritmo di Euclide è preferibile alla scomposizione in fattori primi per diversi motivi:

  • Efficienza: funziona in tempo logaritmico, molto più veloce della fattorizzazione (che è un problema computazionalmente difficile)
  • Numeri grandi: applicabile anche a numeri enormi per i quali la fattorizzazione sarebbe impraticabile
  • Semplicità di implementazione: richiede solo divisioni con resto successive

MCD e MCM: Relazione Fondamentale

Il MCD (Massimo Comun Divisore) e il mcm (minimo comune multiplo) sono strettamente legati dalla seguente relazione:

MCD(a, b) x mcm(a, b) = a x b

Da cui si ricava:

mcm(a, b) = (a x b) / MCD(a, b)

Questa relazione è estremamente utile perché consente di calcolare il mcm una volta noto il MCD (calcolabile efficientemente con Euclide).

Esempio

Calcolare il mcm di 12 e 18:

  • MCD(12, 18) = 6 (calcolato in precedenza)
  • mcm(12, 18) = (12 x 18) / 6 = 216 / 6 = 36

Differenze tra MCD e mcm

Caratteristica MCD mcm
Definizione Più grande divisore comune Più piccolo multiplo comune
Scomposizione Fattori comuni con esponente minimo Tutti i fattori con esponente massimo
Risultato Sempre ≤ del più piccolo dei numeri Sempre ≥ del più grande dei numeri
Uso principale Semplificare frazioni Denominatore comune

Applicazioni Pratiche del MCD

1. Semplificazione delle Frazioni

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

Esempio: semplificare 84/120

  • MCD(84, 120) = 12
  • 84/120 = (84 ÷ 12) / (120 ÷ 12) = 7/10

2. Problemi di Suddivisione

Problema: un giardiniere ha 48 rose rosse e 36 rose bianche. Vuole creare bouquet identici usando tutte le rose, con il massimo numero di bouquet possibile. Quanti bouquet può fare?

  • MCD(48, 36) = 12
  • Può creare 12 bouquet, ciascuno con 4 rose rosse e 3 rose bianche

3. Piastrellatura

Problema: una stanza misura 360 cm x 480 cm. Qual è il lato della piastrella quadrata più grande che copre esattamente il pavimento senza tagli?

  • MCD(360, 480) = 120
  • La piastrella può avere lato massimo di 120 cm (3 piastrelle in larghezza x 4 in lunghezza = 12 piastrelle totali)

4. Ingranaggi e Periodità

Se due ingranaggi hanno rispettivamente 60 e 45 denti, il MCD(60, 45) = 15 indica che gli stessi denti torneranno a combaciare ogni 15 posizioni. Questo è rilevante per il calcolo dell’usura e della sincronizzazione meccanica.

5. Crittografia (Cenno)

L’algoritmo RSA, alla base della crittografia moderna, utilizza il MCD e l’algoritmo di Euclide esteso per generare chiavi crittografiche. Due numeri sono adatti come componenti della chiave solo se il loro MCD rispetta determinate condizioni.

Il MCD in Programmazione

L’algoritmo di Euclide si traduce elegantemente in codice. Ecco la versione ricorsiva e iterativa:

Versione ricorsiva (pseudocodice):

funzione mcd(a, b): se b = 0, restituisci a; altrimenti restituisci mcd(b, a mod b)

Versione iterativa (pseudocodice):

funzione mcd(a, b): finché b diverso da 0, calcola resto = a mod b, poi a = b, b = resto; restituisci a

La versione iterativa è generalmente preferita in programmazione perché non rischia overflow dello stack per numeri molto grandi.

MCD di Più di Due Numeri

Grazie alla proprietà associativa, il MCD di tre o più numeri si calcola procedendo a coppie:

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

Esempio: MCD(24, 36, 60)

  1. MCD(24, 36): usando Euclide, 36 ÷ 24 = 1 resto 12, poi 24 ÷ 12 = 2 resto 0 → MCD = 12
  2. MCD(12, 60): 60 ÷ 12 = 5 resto 0 → MCD = 12

Quindi MCD(24, 36, 60) = 12

Tabella Riepilogativa: MCD di Coppie Comuni

a b MCD(a, b) Metodo rapido
6 8 2 Entrambi pari
12 18 6 Scomposizione: 2×3
15 25 5 Entrambi multipli di 5
24 36 12 Euclide: 36-24=12, 24/12=0
7 11 1 Entrambi primi: coprimi
100 75 25 Scomposizione: 5²
48 180 12 Euclide
17 51 17 51 = 3 x 17

Domande Frequenti (FAQ)

Qual è la differenza tra MCD e mcm?

Il MCD è il più grande numero che divide tutti i numeri dati, mentre il mcm è il più piccolo numero che è divisibile per tutti i numeri dati. Il MCD si usa per semplificare le frazioni, il mcm per trovare il denominatore comune.

Il MCD di due numeri primi è sempre 1?

Sì, se i due numeri sono primi diversi tra loro, il MCD è sempre 1 perché ciascuno ha come divisori solo 1 e sé stesso. Se i due numeri primi sono uguali (ad esempio MCD(7,7)), il risultato è il numero stesso.

Come si calcola il MCD di numeri negativi?

Il MCD è sempre definito come un numero positivo. Per numeri negativi, si prendono i valori assoluti: MCD(-12, 18) = MCD(12, 18) = 6.

Il MCD può essere uguale a uno dei numeri dati?

Sì, quando uno dei numeri è divisore dell’altro. Ad esempio, MCD(5, 15) = 5, perché 5 divide sia 5 che 15.

Quando due numeri sono coprimi?

Due numeri sono coprimi (o primi tra loro) quando il loro MCD è 1. Questo non significa che siano numeri primi: ad esempio, 8 e 15 non sono primi, ma MCD(8, 15) = 1, quindi sono coprimi.

L’algoritmo di Euclide funziona sempre?

Sì, l’algoritmo di Euclide termina sempre in un numero finito di passi e produce sempre il risultato corretto. Si dimostra che il numero di passi è al massimo proporzionale al logaritmo del numero più piccolo, rendendolo estremamente efficiente anche per numeri molto grandi.

A cosa serve il MCD nella vita quotidiana?

Il MCD si utilizza per suddividere oggetti in gruppi uguali (organizzazione di eventi, distribuzione equa), per determinare dimensioni di piastrelle o moduli che si adattano perfettamente a superfici date, per semplificare rapporti e proporzioni e per sincronizzare eventi periodici (orari, cicli produttivi).