Il minimo comune multiplo

Parlando della ricorsione, abbiamo già definito il concetto di numero primo e illustrato il metodo ricorsivo per il calcolo del Massimo Comun Divisore. Con questo post riprendiamo l’argomento dei numeri primi con il calcolo del minimo comune multiplo.

Il minimo comune multiplo è dato dal

prodotto di tutti i fattori primi comuni e non presi una sola volta col massimo esponente.

In questo modo si costruisce il più piccolo numero intero multiplo di entrambi i termini. Ad esempio, il minimo comune multiplo di 18 e 12, così fattorizzati:

18 = 2x3x3
12 = 2x2x3

è dato da:

36 = 2x2x3x3

Infatti, nei fattori dell’mcm è presente il  2, preso con il massimo esponente, cioé 2×2 (appare nel 12) e 3, sempre preso con il massimo esponente, cioé 3×3 (appare in 18).

Troviamo ora un modo per calcolare l’mcm usando i ferri del mestiere della nostra borsa del matematico. Prendiamo due numeri non primi (non è necessario) A e B: sappiamo che questi sono composti dal prodotto di numeri primi, i cosiddetti fattori. E’ il Teorema Fondamentale dell’Aritmetica.

Usiamo la stessa notazione già definita per elencare i fattori di dei due numeri A e B:

F(A) = {A1 M A2}
F(B) = {B1 M B2}

dove F è la funzione che restituisce l’elenco dei fattori di un numero e  A1, A2, B1, B2 sono insiemi di fattori non comuni, ed M è l’insieme dei fattori comuni di A e B, cioé il massimo comun divisore o MCD.

Se uniamo tutti i fattori di A e B otteniamo ovviamente i fattori del prodotto:

F(A x B) = {A1 M A2 B1 M B2 }

Ma la definizione di mcm prevede che si prendano i fattori comuni e non comuni una sola volta: dobbiamo quindi eliminare il secondo gruppo di fattori comuni, M. Sappiamo dal post precedente che M è proprio pari all’MCD, per definizione.

Ora, se l’unione di tutti i fattori restituisce il prodotto di A e B, per rimuovere i fattori di M dobbiamo semplicemente dividere, da cui la regola:

mcm(A, B) = A x B / MCD(A, B)

Torniamo all’esempio, e cacoliamo l’mcm di 18 e 12:

mcm(18,12) = 12 x 18 / MCD(12, 18) = 12 x 18 / 6 = 36

Interessante, no ? Abbiamo ridotto le operazioni su numeri interi ad operazioni sugli insiemi, cioé sui fattori degli stessi numeri interi. Tenete a mente questo fatto: ridurre problemi di matematica alla teoria degli insiemi è uno strumento potentissimo.

Ci ritorneremo.