IT

Calcolare MCD e mcm di più numeri

L'MCD (massimo comune divisore) e il mcm (minimo comune multiplo) si calcolano di solito per due numeri. Per un elenco di più numeri vale lo stesso principio: si riduce l'elenco per coppie successive, applicando l'algoritmo euclideo a ogni passaggio. Tanti numeri quanti servono, separati da una virgola o uno spazio.

L'elenco di numeri

Numeri interi positivi

Da 2 a 20 numeri interi strettamente positivi, separati da virgola o spazio.

I termini con un asterisco, alla prima comparsa, sono spiegati nel glossario in fondo alla pagina.

M.C.D. e m.c.m.: i due nomi della scuola e che cosa misurano

Alle scuole medie il massimo comune divisore si incontra quasi sempre scritto M.C.D., con i puntini. Stessa abitudine per il minimo comune multiplo: m.c.m. Al liceo, e in qualunque testo un po' più adulto, i puntini cadono: MCD* e mcm*. È la stessa coppia di oggetti. Cambia solo la grafia.

L'MCD di un elenco è il più grande intero positivo che divide tutti i numeri dati. Il mcm è il più piccolo intero positivo che è multiplo di ciascuno. Per 12, 18 e 30 — i valori di partenza di questa pagina — l'MCD vale 6 e il mcm vale 180. Il 6 entra in tutti e tre; nulla di più grande lo fa. Il 180 è multiplo di tutti e tre; nulla di più piccolo lo è.

Nella rubrica di aritmetica le due nozioni tornano ovunque: a ridurre una frazione, a trovare un denominatore comune, a decidere se due interi «non hanno niente in comune». Il resto della matematica le eredita senza rivederle. Qui si calcolano su un elenco, non solo su una coppia.

Scomposizione in fattori primi: esponente minimo, esponente massimo

In prima media la strada abituale non è Euclide. Si scompone ciascun intero in fattori primi e si confrontano gli esponenti. L'MCD tiene, per ogni primo, l'esponente minimo. Il mcm tiene il massimo. Un primo che compare in una sola scomposizione sparisce dall'MCD e resta nel mcm.

24, 36 e 60, tre numeri da quaderno:

  • 24 = 23 × 3
  • 36 = 22 × 32
  • 60 = 22 × 3 × 5
  • MCD = 22 × 3 = 12
  • mcm = 23 × 32 × 5 = 360

Si legge in un colpo. Resta comodo finché gli interi stanno sotto qualche migliaio. Oltre, scomporre 999.983 non è un esercizio: è una caccia. L'algoritmo di Euclide* chiude in pochi resti, senza nominare un solo primo. Questa pagina segue Euclide apposta. La scomposizione resta il disegno che spiega perché il risultato è quello; Euclide è lo strumento che lo trova.

L'algoritmo di Euclide, resto dopo resto, fino allo zero

Si divide il maggiore per il minore. Il quoziente non serve. Resta il resto. Poi si ripete con il vecchio minore e quel resto. Quando il resto è zero, l'ultimo divisore usato è l'MCD.

Ogni riga è della forma a = q·b + r, con 0 ≤ r < b. Poi a diventa b e b diventa r. Una coppia un po' più lunga del solito: 252 e 198.

  1. 252 = 1·198 + 54
  2. 198 = 3·54 + 36
  3. 54 = 1·36 + 18
  4. 36 = 2·18 + 0

L'ultimo resto non nullo è 18. Quindi MCD(252, 198) = 18. Quattro passaggi, e si è già finito.

a = q·b + r  (si ripete fino a r = 0; l'ultimo resto non nullo è l'MCD)

Perché non può durare all'infinito? I resti sono interi non negativi, e ciascuno è strettamente minore del divisore precedente. Una successione strettamente decrescente di interi ≥ 0 si ferma. Arriva allo zero. Di solito in poche divisioni. Questa pagina le scrive tutte, coppia dopo coppia, per un elenco da 2 a 20 interi positivi.

Più di due numeri: si riduce a coppie, l'ordine è indifferente

L'MCD di tre numeri non è un terzo congegno. È il più grande intero positivo che li divide tutti, e l'associatività basta a calcolarlo con l'operazione a due argomenti.

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

mcm(a, b, c) = mcm(mcm(a, b), c)

Si prendono i primi due, si calcola, si incorpora il successivo. L'ordine dell'elenco non conta: l'operazione è anche commutativa. Per il mcm, a ogni piega si riusa l'identità a due numeri:

mcm(a, b) = a · b ÷ MCD(a, b)

Con 14, 21 e 35: MCD(14, 21) = 7, poi MCD(7, 35) = 7. Dai multipli, mcm(14, 21) = 42 e mcm(42, 35) = 210. Il 7 divide tutti e tre; nulla di più grande lo fa; 210 è il minimo comune multiplo. Un elenco di venti numeri sono diciannove di queste riduzioni — proprio quello che fa il calcolatore, mostrando ogni a = q·b + r. Nell'aggiornare il mcm si divide prima di moltiplicare, così il prodotto intermedio non si gonfia senza motivo.

L'identità MCD(a, b) × mcm(a, b) = a × b, d'altronde, non sopravvive a tre argomenti. Per 2, 4 e 8 si ha MCD = 2, mcm = 8, prodotto 64, e 2 × 8 = 16 ≠ 64. Vale solo a coppie.

Numeri primi tra loro: quando l'MCD vale 1

Due interi si dicono primi tra loro, o coprimi*, quando il loro unico divisore comune positivo è 1. Nessuno dei due deve essere primo. 9 e 16 lo sono; 25 e 14 pure; 35 e 8 anche. 8 e 9 stanno nel programma di seconda media proprio per questo: due potenze di primi distinti, MCD uguale a 1.

Due interi consecutivi lo sono sempre. Qualsiasi divisore comune di n e n+1 dividerebbe la loro differenza, che è 1. Basta questo. In pratica, 14 e 15, 100 e 101, 998 e 999: sempre MCD = 1.

Su un elenco, «coprimi nel complesso» significa MCD(a, b, c, …) = 1. Non è la stessa cosa che «coprimi a due a due». 6, 10 e 15 hanno MCD 1 come terna, ma MCD(6, 10) = 2. Un MCD globale pari a 1 non vieta che qualche coppia condivida ancora un fattore.

Ridurre una frazione ai minimi termini

Una frazione è ridotta ai minimi termini quando numeratore e denominatore sono divisi per il loro MCD. Nient'altro. Il calcolatore di frazioni lo fa da sé; qui si vede da dove arriva il divisore.

252/198, la coppia di poco fa: MCD = 18, quindi

252 / 198 = (252 ÷ 18) / (198 ÷ 18) = 14 / 11

14 e 11 sono coprimi: la frazione non si muove più. Se l'MCD era 1 fin dall'inizio, era già irriducibile. È un test, non solo una ricetta. I criteri di divisibilità aiutano a scovare a mano i fattori piccoli (2, 3, 5, 9); l'MCD chiude il lavoro, anche quando il fattore comune è 17 o 41.

Dividere per un divisore comune che non è l'MCD lascia il lavoro a metà. 48/18 diviso 2 dà 24/9, e 24/9 si semplifica ancora. Serve arrivare all'MCD (6) per ottenere 8/3.

Il minimo comune denominatore

Sommare 1/6 + 1/8 + 1/10 chiede prima un denominatore comune. Qualsiasi multiplo comune di 6, 8 e 10 va bene (240, 480…). Il più economico è il loro mcm: a scuola si chiama minimo comune denominatore.

mcm(6, 8, 10) = 120, da cui 20/120 + 15/120 + 12/120 = 47/120. Poi l'MCD di 47 e 120 vale 1, quindi la somma è già irriducibile. MCD e mcm si passano il lavoro: uno allinea i denominatori, l'altro stringe il risultato.

Lo stesso gesto serve a confrontare due frazioni senza passarle in decimale — o a farlo col prodotto in croce della regola del tre — o a mediare tempi scritti come frazioni d'ora. Resta che il mcm non è solo affare di orari e ingranaggi: è lo strumento quotidiano delle frazioni.

Cicli che si riallineano: orari, ingranaggi, campanelle

Il mcm risponde a una domanda concreta: quando questi cicli tornano a coincidere?

Un tram ogni 8 minuti, un autobus ogni 12, entrambi in capolinea alle 8:00. Si rivedono insieme dopo mcm(8, 12) = 24 minuti, alle 8:24. Tre semafori da 10, 15 e 18 secondi sono verdi insieme ogni mcm(10, 15, 18) = 90 secondi. Due ruote dentate da 14 e 21 denti tornano allineate dopo 42 denti — stesso conto, altro mestiere.

La campanella di una scuola che suona ogni 50 minuti e un intervallo di 20 minuti coincidono ogni mcm(50, 20) = 100 minuti. Oltre due periodi si piega a coppie, come sopra. Se i tempi non sono interi (ogni 2,5 min e ogni 4), prima si passa a un'unità comune — qui, mezzi minuti: 5 e 8. Il calcolatore accetta solo interi strettamente positivi; quella conversione va fatta a monte, prima di incollare l'elenco.

Identità di Bézout: una lettura in più dei resti (liceo)

L'identità di Bézout* dice che, per due interi a e b, esistono sempre interi u e v — anche negativi — tali che

a·u + b·v = MCD(a, b)

Per 56 e 42, MCD = 14 e basta u = 1, v = −1: 56·1 + 42·(−1) = 14. I coefficienti si recuperano risalendo i resti (algoritmo di Euclide esteso). Inversi modulari, equazioni diofantee lineari, un pezzo di aritmetica del liceo scientifico: lì servono u e v. Non è materia da scuola media. Compare, di solito, quando l'algebra incontra i numeri interi — lo stesso territorio in cui si risolve un'equazione di secondo grado, solo su un altro oggetto.

Questa pagina non mostra u e v. Si ferma all'MCD, al mcm e ai passi di divisione. I coefficienti di Bézout sono una seconda lettura degli stessi resti, non un risultato del calcolatore.

Quando il mcm di una lista cresce di colpo

L'MCD di una lista non può che calare, o restare fermo, a ogni nuovo numero. Il mcm, al contrario, può saltare di un ordine di grandezza appena entra un intero coprimo con quanto già accumulato.

mcm(8, 9, 5, 7, 11) = 27.720, e nessuno dei cinque supera 11. Con venti interi sotto il milione il mcm può uscire dal comodo, anche se questa pagina calcola prima mcm / MCD e poi moltiplica, per tenere i prodotti intermedi più bassi. Non è un errore: è la definizione. Un risultato enorme, a conti fatti, segnala spesso periodi espressi in unità diverse — secondi e minuti nello stesso elenco, per dire.

Lo zero, i negativi e i limiti di questa pagina

Per convenzione, MCD(0, n) = n se n > 0. Lo zero è multiplo di ogni intero, quindi i divisori comuni di 0 e n sono esattamente i divisori di n, e il più grande è n. MCD(0, 0) si lascia indefinito: ogni intero divide 0.

Questa calcolatrice rifiuta lo zero e i negativi. Accetta da 2 a 20 interi strettamente positivi, ciascuno sotto 1.000.000. Euclide se la caverebbe con la convenzione di sopra; il mcm no. Ogni multiplo di 0 è 0, e «minimo comune multiplo» diventa un gioco di parole che qui non serve. Peraltro i numeri negativi non cambiano i divisori positivi: MCD(−12, 18) = MCD(12, 18) = 6. Il calcolatore chiede il valore assoluto già in ingresso, e basta.

Quanti passi: Fibonacci e il teorema di Lamé

Euclide è veloce. Il numero di passi cresce come il logaritmo dei numeri, non come i numeri stessi.

Il caso pessimo lo ha fissato Lamé nel 1844: due termini consecutivi della successione di Fibonacci*. Ogni quoziente vale 1, il resto scende il più piano possibile. MCD(13, 8) — F7 e F6 — incatena 5, 3, 2, 1, 0. Cinque resti per due interi piccoli. In ogni caso il numero di divisioni non supera cinque volte il numero di cifre decimali del più piccolo dei due.

Di fatto scomporre prima è quasi sempre la strategia sbagliata per una macchina: Euclide ha già finito prima che salti fuori il primo fattore. I Fibonacci non sono una trappola di questo calcolatore; riempiono solo la tabella dei passi. In sostanza, per un elenco da compito in classe o da officina, i resti stanno in una manciata di righe.

Glossario

MCD
Massimo comune divisore: il più grande intero positivo che divide tutti i numeri di un elenco. Alle scuole medie si scrive spesso M.C.D.
mcm
Minimo comune multiplo: il più piccolo intero positivo che è multiplo di ciascuno dei numeri dati. A scuola, m.c.m.
Algoritmo di Euclide
Procedura che trova l'MCD di due interi sostituendo, a ogni passo, la coppia (a, b) con (b, resto di a ÷ b), fino a resto zero. L'ultimo divisore usato è l'MCD.
Numeri coprimi
Due interi il cui unico divisore comune positivo è 1. Si dicono anche «primi tra loro». Nessuno dei due deve essere un numero primo.
Identità di Bézout
Il fatto che esistano sempre due interi u e v, eventualmente negativi, tali che a·u + b·v sia uguale all'MCD di a e b. Si ricavano risalendo i resti di Euclide.
Successione di Fibonacci
La successione 1, 1, 2, 3, 5, 8, 13… in cui ogni termine è somma dei due precedenti. Due termini consecutivi sono il caso in cui Euclide fa più passi.

Calcolatrici correlate