MCD e mcm: calcoli alternativi e veloci

Per trovare il massimo comune divisore (MCD) e il minimo comune multiplo (mcm) non occorre sempre scomporre tutti i numeri in fattori primi. Le divisioni successive di Euclide permettono di calcolare rapidamente il MCD; da questo si ricava subito il mcm. Gli stessi due strumenti funzionano anche quando i numeri sono tre o più. In questo articolo consideriamo interi positivi.

Che cosa cerchiamo?

Il MCD è il più grande intero positivo che divide tutti i numeri dati. Il mcm è il più piccolo intero positivo che è multiplo di tutti. Per esempio, se due eventi si ripetono ogni 24 e 36 minuti, il primo istante positivo in cui coincidono di nuovo è il loro mcm; il MCD, invece, indica la misura più grande con cui si possono dividere entrambe le durate in parti intere uguali.

MCD rapido: divisioni successive

Calcoliamo MCD(84,132). Dividiamo il maggiore per il minore e sostituiamo la coppia con divisore e resto, fino a ottenere resto zero:

132 = 84 × 1 + 48
84 = 48 × 1 + 36
48 = 36 × 1 + 12
36 = 12 × 3 + 0

L’ultimo resto non nullo è 12, quindi MCD(84,132) = 12. Il motivo è che i divisori comuni di due numeri sono esattamente i divisori comuni del divisore e del resto: MCD(A,B) = MCD(B,A mod B).

Tre formule da ricordare

Per interi positivi A, B e C:

mcm(A,B) = A × B / MCD(A,B)
MCD(A,B,C) = MCD(C,MCD(A,B))
mcm(A,B,C) = mcm(C,mcm(A,B))

Si lavora su due numeri alla volta; l’ordine dei numeri non cambia il risultato.

Dal MCD al mcm senza nuova scomposizione

Con la prima formula, mcm(84,132) = 84 × 132 / 12 = 84 × 11 = 924. Conviene dividere prima di moltiplicare: i numeri intermedi restano più piccoli. Il controllo è immediato: 924 / 84 = 11 e 924 / 132 = 7.

Perché funziona? In una scomposizione in primi, il MCD prende per ogni primo l’esponente minore e il mcm quello maggiore. La somma di minimo e massimo è la somma dei due esponenti di partenza: perciò MCD(A,B) × mcm(A,B) = A × B.

Un esempio completo con tre numeri

Prendiamo 24, 36 e 50. Per il MCD procediamo a coppie: MCD(24,36) = 12, poi MCD(50,12) = 2. Dunque MCD(24,36,50) = 2.

Per il mcm, prima mcm(24,36) = 24 × 36 / 12 = 72. Poi MCD(72,50) = 2 e mcm(50,72) = 50 × 72 / 2 = 1800. Dunque mcm(24,36,50) = 1800: infatti 1800 / 24 = 75, 1800 / 36 = 50 e 1800 / 50 = 36.

Scorciatoie utili e un errore da evitare

• Se un numero è multiplo dell’altro, il MCD è il più piccolo e il mcm il più grande: MCD(18,72) = 18 e mcm(18,72) = 72.
• Se il MCD è 1, i numeri sono coprimi e il mcm è il prodotto: mcm(35,64) = 35 × 64 = 2240.
• La formula per due numeri non diventa A × B × C / MCD(A,B,C) per tre numeri. Nel nostro esempio darebbe 21600, non 1800. Bisogna applicare la formula a coppie.

Prova tu

Trova MCD e mcm di 18, 30 e 42 usando soltanto coppie successive.

La strategia è sempre la stessa: prima trova rapidamente il MCD con i resti; poi usa il prodotto diviso per il MCD; con tre o più numeri ripeti il procedimento a coppie.