Dati due numeri Naturali n e m, si ha: $\mathbf{n\cdot m = MCD(n,m)\cdot mcm(n,m)}$ (1)

È una relazione tanto interessante quanto utile: in Informatica, ad esempio, esistono diversi algoritmi per il calcolo del MCD tra due numeri per cui la (1) consente facilmente di implementare un algoritmo che calcoli il mcm:

$mcm(n,m) = \frac{n\cdot m}{MCD(n,m)}$ (2)

Dalla (1) si ricava anche:

$MCD(n,m) = \frac{n\cdot m}{mcm(n,m)}$ (3)

Esempi

1. Consideriamo i numeri 3 e 4, primi tra loro. Si ha: $mcm(3,4)=12$; $MCD(3,4)=1$ quindi $3\cdot 4=mcm(3,4)\cdot MCD(3,4)=12\cdot 1$

2. Consideriamo ora i numeri 12 e 90. Si ha: $mcm(12,90)=180$; $MCD(12,90)=6$ quindi $12\cdot 90=mcm(12,90)\cdot MCD(12,90)=180\cdot 6$

3. Consideriamo i numeri 24 e 30. La loro scomposizione in fattori primi è: $24=2^{3}\cdot 3$ e $30=2\cdot 3\cdot 5$. Ricordiamo che per calcolare il mcm occorre moltiplicare i fattori comuni a 24 e 30 e quelli non comuni, presi una sola volta col massimo esponente: $mcm(24,30)=2^{MAX(3,1)}\cdot 3\cdot 5= 2^{3}\cdot 3\cdot 5= 120$. Il MCD invece si calcola moltiplicando i soli fattori comuni a 24 e 30, presi una sola volta col minimo esponente: $MCD(24,30)=2^{min(3,1)}\cdot 3=2^{1}\cdot 3=6 $. Quindi: $mcm(24,30)\cdot MCD(24,30)=\left [ 2^{MAX(3,1)}\cdot 3\cdot 5\right ]\cdot \left [ 2^{min(3,1)}\cdot 3 \right ]= \left [ 2^{3}\cdot 3\cdot 5 \right ]\cdot \left [ 2^{1}\cdot 3 \right ]=$

$=(2^{3}\cdot 3)\cdot (2\cdot 3\cdot 5)=24\cdot 30=720$.

Dimostrazioni

Fornirò due dimostrazioni della proposizione esposta perché alquanto diverse tra loro.

Dimostrazione 1

Siano dunque n e m due naturali. La loro scomposizione in fattori primi si può scrivere convenientemente come segue:

$n=c_{n_1}^{e_{n_1}}\cdot c_{n_2}^{e_{n_2}}\cdot … \cdot c_{n_k}^{e_{n_k}}\cdot u_{n_1}^{e’_{n_1}}\cdot u_{n_2}^{e’_{n_2}}\cdot … \cdot u_{n_i}^{e’_{n_i}}=\prod_{\alpha =1}^{k}c_{n_\alpha }^{e_{n_{\alpha }}}\cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}}$ (4)

$m=c_{m_1}^{e_{m_1}}\cdot c_{m_2}^{e_{m_2}}\cdot … \cdot c_{m_k}^{e_{m_k}} \cdot u_{m_1}^{e’_{m_1}}\cdot u_{m_2}^{e’_{m_2}}\cdot … \cdot u_{m_j}^{e’_{m_j}} =\prod_{\alpha =1}^{k}c_{m_\alpha }^{e_{m_{\alpha }}}\cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} $ (5)

in cui i fattori indicati con la lettera c (Common) sono i fattori comuni alle scomposizioni di n e m (e dunque sono in numero uguale, k, con esponenti non necessariamente uguali), mentre i fattori indicati con la lettera u (Uncommon) sono non comuni.

Procedendo come nell’esempio 3, si ha:

$MCD(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{min(e_{n_{\alpha }}, e_{m_{\alpha }})}$ (6)

$mcm(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{MAX(e_{n_{\alpha }}, e_{m_{\alpha }})} \cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} $ (7)

Moltiplicando tra loro la (6) e la (7) si ha:

$mcm(n,m)\cdot MCD(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{ min(e_{n_{\alpha }}, e_{m_{\alpha }})+MAX(e_{n_{\alpha }}, e_{m_{\alpha }})} \cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} $ (8)

Peraltro, trattandosi soltanto di due numeri, è chiaro che

$ min(e_{n_{\alpha }}, e_{m_{\alpha }})+MAX(e_{n_{\alpha }}, e_{m_{\alpha }})= e_{n_{\alpha }} + e_{m_{\alpha }}, \forall \alpha \epsilon \left \{1,…,k \right\} $ (9)

Dalla (8) e la (9) si ottiene dunque:

$mcm(n,m)\cdot MCD(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{ e_{n_{\alpha }}+e_{m_{\alpha }}} \cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} = $

$= \prod_{\alpha =1}^{k}c_{n_\alpha }^{e_{n_{\alpha }}}\cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\alpha =1}^{k}c_{m_\alpha }^{e_{m_{\alpha }}}\cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} = n \cdot m$ (10),

come volevasi dimostrare.

Dimostrazione 2

Siano ancora n e m due naturali e sia D il MCD(n,m) e G il mcm(n,m).

Riscriviamo dunque la (1) come $n\cdot m=G\cdot D$.

Dimostrare la (1) equivale quindi a dimostrare che:

(H) $D=MCD(n,m)\Rightarrow$ (T) $G=\frac{nm}{D}=mcm(n,m)$ (11)

Dimostrare che G – così come è definito dal secondo membro della (11) – è il mcm(n,m) equivale a dimostrare le due seguenti affermazioni:

(a) G è multiplo di n e m

(b) Non esistono multipli di n e m minori di G

Per dimostrare l’affermazione (a), poichè D – per l’ipotesi (H) – è divisore sia di n che di m, si ha:

$\exists k\epsilon N_0:n=kD$ (12)

$\exists h\epsilon N_0:m=hD $ (13)

dalla (12) si ricava $G=\frac{n\cdot m}{D}=\frac{kDm}{D}=km\Rightarrow\textbf{G è multiplo di m}$

analogamente, dalla (13) si ricava $G=\frac{n\cdot m}{D}=\frac{nhD}{D}=hn\Rightarrow\textbf{G è multiplo di n}$,

sicché la (a) è dimostrata.

Per provare la (b), supponiamo per assurdo che $\exists G'<G : G’=h’n=k’m$, (sicché k'<k e h'<h). Posto $D’=\frac{nm}{G’}$, si ha:

$\frac{n}{D’}=\frac{G’}{m}=h’\Rightarrow$ D’ è divisore di n

$\frac{m}{D’}=\frac{G’}{n}=k’\Rightarrow$ D’ è divisore di m.

Quindi D’ è divisore comune di n e m.

Peraltro, l’ipotesi G'<G $\Rightarrow D’=\frac{nm}{G’}>\frac{nm}{G}=D\Rightarrow D’>D \Rightarrow $ D non è MCD, contro l’ipotesi iniziale (H).

L’assurdo cui si è pervenuti mostra la tesi: non esistono multipli di n e m minori di G, sicchè anche la (b) è dimostrata.

Quindi G è il mcm(n,m).