Ultimo aggiornamento: 2026-05-13

Due relazioni fondamentali tra interi

Ogni coppia di interi positivi condivide due numeri speciali: il più grande intero che li divide entrambi esattamente (il massimo comun divisore, MCD) e il più piccolo intero che è multiplo di entrambi (il minimo comune multiplo, MCM). Insieme, descrivono come due numeri sono aritmeticamente correlati.

Prendiamo ad esempio 12 e 8:

• I divisori comuni di 12 e 8 sono 1, 2 e 4. Il più grande è 4.
• I multipli comuni di 12 e 8 sono 24, 48, 72, …. Il più piccolo è 24.

Come l'algoritmo di Euclide calcola il MCD

Il metodo più antico — e tuttora il più veloce in pratica — per trovare il MCD è l'algoritmo di Euclide, descritto nei suoi Elementi intorno al 300 a.C. La proprietà chiave è:

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

dove $a \bmod b$ è il resto della divisione di $a$ per $b$. Il procedimento si ripete finché il resto non diventa zero; l'ultimo valore diverso da zero è il MCD.

Esempio: MCD(48, 18)

Passo	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0

L'ultimo resto diverso da zero è 6, quindi MCD(48, 18) = 6.

L'algoritmo è notevolmente efficiente: il numero di passi non supera mai cinque volte il numero di cifre del più piccolo dei due numeri.

L'identità MCD–MCM

Una volta noto il MCD, il MCM si ricava con un'unica formula:

$\text{MCM}(a, b) = \frac{a \times b}{\text{MCD}(a, b)}$

Non è una coincidenza: è un teorema che discende dalla fattorizzazione unica in numeri primi. Rappresentando ogni intero come prodotto di potenze di numeri primi, il MCD prende l'esponente minimo per ciascun primo e il MCM prende il massimo. Il loro prodotto ricostruisce sempre $a \times b$.

Esempio: MCM(12, 8)

$\text{MCD}(12, 8) = 4, \quad \text{MCM}(12, 8) = \frac{12 \times 8}{4} = 24$

Verifica: $4 \times 24 = 96 = 12 \times 8$. ✓

Applicazioni pratiche

Semplificare le frazioni

Per ridurre $\dfrac{a}{b}$ ai minimi termini, si dividono numeratore e denominatore per $\text{MCD}(a, b)$. Ad esempio, $\dfrac{12}{8}$ si semplifica in $\dfrac{3}{2}$ perché $\text{MCD}(12, 8) = 4$.

Sommare le frazioni

Per calcolare $\dfrac{1}{12} + \dfrac{1}{8}$ occorre il minimo denominatore comune, che è $\text{MCM}(12, 8) = 24$:

$\frac{1}{12} + \frac{1}{8} = \frac{2}{24} + \frac{3}{24} = \frac{5}{24}$

Cicli e periodi

Se due eventi si ripetono ogni $a$ giorni e ogni $b$ giorni, torneranno a coincidere dopo $\text{MCM}(a, b)$ giorni. È per questo che il MCM compare nei rapporti di trasmissione degli ingranaggi, nella periodicità dei motivi di piastrellatura e nei problemi di calendario (quando due cicli celesti si riallineano?).

Crittografia

L'algoritmo di Euclide è un'operazione primitiva fondamentale nella crittografia RSA: il MCD serve a verificare che l'esponente della chiave scelto sia coprimo con la funzione di Eulero del modulo.

Casi particolari

• MCD(a, 0) = a per qualsiasi intero positivo $a$: è il caso base dell'algoritmo di Euclide e discende direttamente dalla definizione.
• Numeri coprimi: MCD = 1 e MCM = a × b. Per esempio MCD(7, 13) = 1, MCM(7, 13) = 91.
• Numeri uguali: MCD(n, n) = n e MCM(n, n) = n.

Riferimento rapido

Proprietà	Formula
Algoritmo di Euclide	$\gcd(a, b) = \gcd(b,\ a \bmod b)$
MCM dal MCD	$\text{MCM}(a,b) = \dfrac{a \times b}{\text{MCD}(a,b)}$
Identità	$\text{MCD}(a,b) \times \text{MCM}(a,b) = a \times b$
Semplificare una frazione	dividere numeratore e denominatore per il MCD
Denominatore comune	usare il MCM dei due denominatori

Domande frequenti (FAQ)

Che cos'è il massimo comun divisore?

Il massimo comun divisore (MCD) di due interi è il più grande intero positivo che li divide entrambi senza resto. Ad esempio, MCD(12, 8) = 4 perché 4 è il numero più grande che divide esattamente sia 12 che 8.

Che cos'è il minimo comune multiplo?

Il minimo comune multiplo (MCM) di due interi è il più piccolo intero positivo divisibile da entrambi. Ad esempio, MCM(12, 8) = 24 perché 24 è il numero più piccolo che è multiplo sia di 12 che di 8.

Qual è la relazione tra MCD e MCM?

Per due qualsiasi interi positivi a e b vale: MCD(a, b) × MCM(a, b) = a × b. Ciò significa che è possibile ricavare uno dall'altro: MCM = a × b ÷ MCD. È proprio questa relazione a giustificare il calcolo congiunto delle due grandezze.