MCD e mcm

MCD e mcm: che cosa sono e come si calcolano

Il massimo comun divisore (MCD) di due o più numeri interi è il più grande numero che li divide tutti senza resto. Il minimo comune multiplo (mcm) è il più piccolo numero positivo che è multiplo di tutti. Sono due facce della stessa scomposizione: il MCD guarda ciò che i numeri hanno in comune, il mcm guarda ciò che serve per contenerli tutti.

Con 24, 36 e 60 il MCD è 12 (si divide 24, 36 e 60 senza avanzi, e nessun numero più grande lo fa) e il mcm è 360 (è multiplo di tutti e tre, e nessun multiplo comune più piccolo esiste).

Il metodo della scomposizione in fattori primi

È il metodo che si impara alle medie e resta il più trasparente. Si scompone ogni numero nel prodotto dei suoi fattori primi, poi:

• MCD: si moltiplicano solo i primi comuni a tutti i numeri, ciascuno con l'esponente più piccolo fra quelli osservati.
• mcm: si moltiplicano tutti i primi che compaiono anche in uno solo dei numeri, ciascuno con l'esponente più grande.

Esempio completo con 12 e 18: 12 = 2² × 3 e 18 = 2 × 3². I primi comuni sono 2 e 3; con l'esponente minimo danno MCD = 2 × 3 = 6; con l'esponente massimo danno mcm = 2² × 3² = 36. La tabella degli esponenti qui sopra fa esattamente questo conto, colonna per colonna.

L'algoritmo di Euclide

Scomporre in fattori primi è facile finché i numeri sono piccoli; con numeri grandi diventa il collo di bottiglia. L'algoritmo di Euclide arriva al MCD senza scomporre niente: si divide il maggiore per il minore e si ricomincia con il divisore e il resto, finché il resto è zero. L'ultimo divisore è il MCD.

Su 48 e 18: 48 = 18 × 2 + 12, poi 18 = 12 × 1 + 6, poi 12 = 6 × 2 + 0. Il MCD è 6, in tre divisioni. È un procedimento che risale al Libro VII degli Elementi di Euclide e resta oggi uno degli algoritmi più usati nel software: il numero di divisioni cresce come il logaritmo dei numeri, quindi anche su numeri enormi finisce in pochissimi passi.

La relazione fra MCD e mcm

Per due numeri vale sempre MCD(a, b) × mcm(a, b) = a × b. Da qui si ricava il mcm in un passaggio solo: mcm(a, b) = a × b / MCD(a, b). Il calcolo qui sopra divide prima e moltiplica dopo — a / MCD × b — perché il prodotto a × b può diventare molto grande inutilmente.

Attenzione: la relazione vale solo per due numeri. Con tre o più numeri MCD × mcm non è il prodotto: con 4, 6 e 9 il MCD è 1 e il mcm è 36, mentre il prodotto è 216. Con più numeri si procede a coppie, come nella tabella «Da due numeri a…» qui sopra.

Numeri coprimi

Due numeri sono coprimi (o primi fra loro) quando il loro MCD è 1: non condividono nessun fattore primo. Non serve che siano numeri primi: 15 e 28 sono coprimi pur essendo entrambi composti (15 = 3 × 5, 28 = 2² × 7). Per due numeri coprimi il mcm è semplicemente il prodotto: mcm(15, 28) = 420. Una frazione è ridotta ai minimi termini esattamente quando numeratore e denominatore sono coprimi.

A che cosa servono davvero

• Ridurre una frazione: si divide numeratore e denominatore per il loro MCD. 84/126 ha MCD 42 e diventa 2/3 in un colpo solo, senza semplificare a tentativi.
• Sommare frazioni: il denominatore comune «giusto» è il mcm dei denominatori. Per 5/12 + 7/18 il mcm è 36 (non 216, che è il prodotto): si arriva a 15/36 + 14/36 = 29/36 senza dover semplificare alla fine.
• Eventi periodici: due autobus che partono ogni 12 e ogni 18 minuti ripartono insieme ogni 36 minuti; due ingranaggi con 12 e 18 denti tornano nella posizione iniziale dopo 36 denti, cioè 3 giri del primo e 2 del secondo.
• Confezioni e gruppi: con 24 penne, 36 matite e 60 gomme si possono comporre al massimo 12 sacchetti identici (MCD), ciascuno con 2 penne, 3 matite e 5 gomme.
• Piastrelle e formati: il lato della piastrella quadrata più grande che riveste una parete 360 × 240 cm senza tagli è il MCD dei due lati, cioè 120 cm.
• Crittografia: RSA sceglie un esponente pubblico coprimo con (p−1)(q−1) e ricava la chiave privata con l'algoritmo di Euclide esteso, cioè con l'identità di Bézout che questo strumento mostra.

Identità di Bézout, in una riga

Per ogni coppia di interi a e b esistono due interi x e y tali che a·x + b·y = MCD(a, b): è l'identità di Bézout, e i coefficienti si ottengono «srotolando» all'indietro le divisioni di Euclide. Con 240 e 46 si ha 240 × (−9) + 46 × 47 = 2. Ne discende il criterio per le equazioni diofantee: ax + by = c ha soluzioni intere se e solo se il MCD di a e b divide c.

Casi limite e convenzioni

• MCD(a, a) = a e mcm(a, a) = a: un numero è divisore e multiplo di sé stesso.
• Se a divide b, allora MCD = a e mcm = b. Per 6 e 24: MCD 6, mcm 24.
• MCD(a, 1) = 1 e mcm(a, 1) = a per qualunque a.
• Lo zero si comporta in modo particolare: ogni numero divide 0, quindi MCD(a, 0) = a, mentre il mcm con 0 non è definito come numero positivo. Questo strumento lavora sugli interi positivi e ignora gli zeri.
• I divisori comuni di due numeri sono esattamente i divisori del loro MCD, e i multipli comuni sono esattamente i multipli del loro mcm: non esiste nulla «in mezzo».

Perché qui i numeri grandi restano esatti

Il mcm cresce in fretta e la formula a × b / MCD passa per un prodotto che può superare 9.007.199.254.740.991, il più grande intero rappresentabile esattamente in virgola mobile. Oltre quella soglia un normale calcolatore JavaScript comincia ad arrotondare senza dirlo: mcm(123.456.789, 987.654.321) vale 13.548.070.123.626.141, ma la formula con i numeri decimali restituisce 13.548.070.123.626.140 — sbagliato di uno, senza nessun avviso. Questo strumento lavora in aritmetica intera esatta (BigInt), quindi la cifra finale è sempre quella giusta.

Domande che ricorrono

Il MCD può essere più grande del più piccolo dei numeri? No, mai: deve dividerli tutti, quindi al massimo è uguale al minore. Il mcm può essere più piccolo del maggiore? Nemmeno: deve essere multiplo di tutti, quindi al minimo è uguale al maggiore. Si scrive MCD o mcd? In Italia si scrive MCD in maiuscolo e mcm in minuscolo — è la convenzione dei libri di testo, non un errore di stampa.