Calcolatore MCD e mcm: algoritmo di Euclide, coprimi, scomposizione

Calcola MCD e mcm di due o più numeri interi con algoritmo di Euclide esteso, identità di Bézout, scomposizione in fattori primi e test di coprimalità.

Parametri di calcolo
Questo calcolatore ti è stato utile?

Massimo comun divisore e minimo comune multiplo

Il massimo comun divisore MCD(a, b) (in inglese gcd, greatest common divisor) di due interi non entrambi nulli è il più grande intero positivo che divide sia a sia b senza resto. Il minimo comune multiplo mcm(a, b) (lcm, least common multiple) è il più piccolo intero positivo che è multiplo sia di a sia di b. Per convenzione MCD(0, 0) = 0 e mcm(0, x) = 0. Per ogni coppia di interi a, b vale la relazione fondamentale: MCD(a, b) · mcm(a, b) = |a · b|.

Algoritmo di Euclide

L'algoritmo di Euclide, descritto negli Elementi (Libro VII, circa 300 a.C.), calcola MCD(a, b) con sole divisioni successive con resto: MCD(a, b) = MCD(b, a mod b), fino a MCD(x, 0) = |x|. Esempio: MCD(252, 105) = MCD(105, 42) = MCD(42, 21) = MCD(21, 0) = 21. L'algoritmo termina in O(log(min(a, b))) passi e la sua complessità è legata alla successione di Fibonacci: il caso peggiore si verifica con numeri consecutivi di Fibonacci.

Algoritmo di Euclide esteso e identità di Bézout

L'algoritmo di Euclide esteso trova non solo MCD(a, b) = d ma anche due interi s, t tali che d = a · s + b · t (identità di Bézout). Questi coefficienti sono fondamentali in crittografia (RSA, calcolo dell'inverso moltiplicativo modulo n) e nella risoluzione di equazioni diofantee lineari ax + by = c (ammettono soluzione intera se e solo se MCD(a, b) | c).

Formula per il mcm

Il minimo comune multiplo si calcola efficientemente dal MCD: mcm(a, b) = |a · b| / MCD(a, b). In questo modo si evita di enumerare i multipli. Esempio: mcm(12, 18) = 12 · 18 / MCD(12, 18) = 216 / 6 = 36. Per tre o più numeri si applica la formula ricorsivamente: mcm(a, b, c) = mcm(mcm(a, b), c). Idem per il MCD: MCD(a, b, c) = MCD(MCD(a, b), c).

Scomposizione in fattori primi

Una via alternativa al calcolo di MCD e mcm è la scomposizione in fattori primi. Se a = p₁^α₁ · p₂^α₂ · ... e b = p₁^β₁ · p₂^β₂ · ..., allora MCD(a, b) = ∏ pᵢ^min(αᵢ, βᵢ) e mcm(a, b) = ∏ pᵢ^max(αᵢ, βᵢ). È il metodo più intuitivo ma inefficiente per numeri molto grandi: la fattorizzazione è un problema computazionalmente hard, alla base della sicurezza di RSA.

Numeri coprimi

Due interi a, b si dicono coprimi (o primi tra loro) se MCD(a, b) = 1. Questa condizione è cruciale in teoria dei numeri: il teorema cinese del resto richiede moduli coprimi; la funzione di Eulero φ(n) conta gli interi in [1, n] coprimi con n; l'inverso moltiplicativo a⁻¹ mod n esiste se e solo se MCD(a, n) = 1. Esempi di coppie coprime: (8, 15), (9, 28), (13, 100).

Proprietà del MCD

  • Commutatività: MCD(a, b) = MCD(b, a).
  • Associatività: MCD(MCD(a, b), c) = MCD(a, MCD(b, c)).
  • Identità: MCD(a, 0) = |a|; MCD(a, 1) = 1.
  • Distributiva: MCD(ka, kb) = |k| · MCD(a, b) per k ≠ 0.
  • Riduzione frazioni: una frazione p/q è ridotta ai minimi termini se e solo se MCD(p, q) = 1.

Come usare il calcolatore

Inserisci due o più numeri interi separati da virgola (es. 12, 18, 24). Il calcolatore restituisce MCD e mcm, mostra i passaggi dell'algoritmo di Euclide, individua i coefficienti di Bézout s, t (solo per due input), calcola la scomposizione in fattori primi di ciascun numero e verifica la coprimalità. Accetta interi positivi o negativi di qualsiasi grandezza (limitato da Number.MAX_SAFE_INTEGER in JavaScript: ±2^53 − 1).

Applicazioni

MCD e mcm compaiono in molti contesti pratici: semplificazione di frazioni (dividendo numeratore e denominatore per il loro MCD), sincronizzazione di eventi periodici (due lampade che lampeggiano ogni 12 s e 18 s coincidono ogni mcm = 36 s), crittografia (RSA, ElGamal), schedulazione di processi, teoria musicale (rapporti armonici). In informatica il gcd appare anche nel calcolo della permutazione ciclica minima e nella generazione di sequenze pseudo-casuali.

Un algoritmo di 2300 anni

L'algoritmo di Euclide compare nel VII libro degli Elementi (circa 300 a.C.) ed è considerato il più antico algoritmo non banale ancora in uso. La sua efficienza è notevole: il numero di passi non supera cinque volte il numero di cifre del numero minore (teorema di Lamé, 1844), e il caso peggiore si verifica con due numeri di Fibonacci consecutivi. Donald Knuth lo ha definito "il nonno di tutti gli algoritmi".

Dove lavorano MCD e mcm oggi

L'aritmetica del MCD è ovunque nella tecnologia: la crittografia RSA sceglie esponenti coprimi con la funzione di Eulero del modulo e calcola gli inversi con l'Euclide esteso; i riduttori meccanici usano ruote con numeri di denti coprimi per distribuire uniformemente l'usura; i processori e le trasmissioni digitali sfruttano il mcm per sincronizzare segnali periodici. Nella didattica italiana MCD e mcm restano il primo incontro con la teoria dei numeri fin dalla scuola media, e tornano nei corsi universitari di algebra e crittografia dei Politecnici.

Aggiornato a luglio 2026

Domande frequenti

Come funziona l'algoritmo di Euclide?

Si divide il numero maggiore per il minore e si sostituisce il maggiore con il resto, ripetendo finché il resto è zero: l'ultimo divisore non nullo è il MCD. Per 48 e 18: 48 = 18·2 + 12, poi 18 = 12·1 + 6, infine 12 = 6·2 + 0, quindi MCD = 6. Il calcolatore mostra tutti i passaggi della divisione.

Che relazione c'è tra MCD e mcm?

Per due numeri vale l'identità MCD(a,b) × mcm(a,b) = a × b. Con 48 e 18: il MCD è 6, quindi mcm = 48·18/6 = 144. Il calcolatore usa proprio questa identità, che però vale solo per le coppie: con tre o più numeri il risultato si ottiene iterando il calcolo coppia per coppia sull'intera lista.

Cosa significa che due numeri sono coprimi?

Coprimi (o primi tra loro) significa MCD = 1: non condividono alcun fattore primo, come 8 e 15. Non serve che siano numeri primi: 8 = 2³ e 15 = 3·5 sono entrambi composti, eppure coprimi. La coprimalità è alla base della funzione di Eulero e della crittografia RSA che protegge le comunicazioni online.

A cosa serve l'identità di Bézout?

Garantisce che esistano interi x e y tali che ax + by = MCD(a,b): per 48 e 18 si ha 6 = 48·(−1) + 18·3. Il calcolatore li ricava con l'algoritmo di Euclide esteso. È lo strumento con cui si calcolano gli inversi modulari, cuore dell'aritmetica modulare, dei codici correttori e della crittografia a chiave pubblica.

Come si calcolano MCD e mcm con la scomposizione in fattori primi?

Si scompongono i numeri: il MCD prende i fattori comuni con l'esponente minimo, il mcm tutti i fattori con l'esponente massimo. Per 48 = 2⁴·3 e 18 = 2·3²: MCD = 2·3 = 6 e mcm = 2⁴·3² = 144. Il metodo è ottimo a scuola ma lento sui numeri grandi, dove l'algoritmo di Euclide resta imbattibile.

A cosa serve il mcm nella pratica?

A sommare frazioni con il minimo denominatore comune, a sincronizzare eventi periodici (due autobus che passano ogni 12 e 18 minuti coincidono ogni mcm = 36 minuti) e a progettare ingranaggi e cicli di manutenzione. Il MCD serve invece a semplificare le frazioni e a suddividere quantità in parti uguali massime.

Il calcolatore accetta più di due numeri?

Sì: puoi inserire quanti numeri vuoi, separati da virgola, spazio o punto e virgola. MCD e mcm vengono calcolati iterativamente su tutta la lista; i passaggi di Euclide e l'identità di Bézout sono mostrati per la prima coppia. Gli eventuali segni negativi vengono ignorati usando il valore assoluto.

Formula

MCD(a,b) via Euclide: gcd(a,b)=gcd(b, a mod b); gcd(a,0)=|a|. mcm(a,b)=|a·b|/gcd(a,b). Identità di Bézout: gcd(a,b)=a·s+b·t.

Commenti (0)

Ancora nessun commento. Sii il primo!