Given two natural numbers n and m, we have: $\mathbf{n\cdot m = GCD(n,m)\cdot LCM(n,m)}$ (1)

It’s a very interesting and useful relationship: for example several algorithms to calculate GCD of two numbers exist, so that using (1) an algorithm to calculate LCM can be implemented:

$LCM(n,m) = \frac{n\cdot m}{GCD(n,m)}$ (2)

From (1) it follows also:

$GCD(n,m) = \frac{n\cdot m}{LCM(n,m)}$ (3)

Examples

1. Let’s consider numbers 3 and 4, co-prime. We have: $LCM(3,4)=12$; $GCD(3,4)=1$ so $3\cdot 4=LCM(3,4)\cdot GCD(3,4)=12\cdot 1$

2. Let’s consider now the numbers 12 and 90. We have: $LCM(12,90)=180$; $GCD(12,90)=6$ so $12\cdot 90=LCM(12,90)\cdot GCD(12,90)=180\cdot 6$

3. Finally let’s considers the numbers 24 and 30. Decomposing them in prime factors: $24=2^{3}\cdot 3$ and $30=2\cdot 3\cdot 5$. Recall that to evaluate the LCM we must multiply all factors taken once with the maximum exponent: $LCM(24,30)=2^{MAX(3,1)}\cdot 3\cdot 5= 2^{3}\cdot 3\cdot 5= 120$. GCD instead is calculated by multiplying only those factors which are shared by the two numbers taken once with the minimum exponent: $GCD(24,30)=2^{min(3,1)}\cdot 3=2^{1}\cdot 3=6 $. Hence: $LCM(24,30)\cdot GCD(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$.

Proofs

I’ll provide two different proofs.

Proof 1

Let n and m be two natural numbers. Their prime factorization can be conveniently written as follows:

$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 which c factors (Common) are the ones which appear in both n and m factorizations (so they are the same number, k, with same exponents), whereas u factors (Uncommon) are unique for each number.

Proceeding as in the example 3, we have:

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

$LCM(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)

Multiplying equations (6) and (7) we get:

$LCM(n,m)\cdot GCD(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)

Moreover, since we’re dealing with only two numbers,

$ 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)

From (8) and (9) it follows that:

$LCM(n,m)\cdot GCD(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),

and the statement is proven.

Proof 2

Let again n and m be two natural numbers, D be GCD(n,m) and G be LCM(n,m).

We can rewrite (1) as $n\cdot m=G\cdot D$.

Proving (1) equals to prove that:

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

Proving that G – as defined by the second side of (11) – is the LCM(n,m) equals to prove the two following statements:

(a) G is multiple of n and m

(b) There’s no other multiple of n and m which is less than G

To prove (a), since D is a divisor of both n and m, we have:

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

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

from (12) we get $G=\frac{n\cdot m}{D}=\frac{kDm}{D}=km\Rightarrow\textbf{G is multiple of m}$

similarly, from (13) we get $G=\frac{n\cdot m}{D}=\frac{nhD}{D}=hn\Rightarrow\textbf{G is multiple of n}$,

To proof (b), let’s suppose (reductio ad absurdum) that $\exists G'<G : G’=h’n=k’m$, (so that k'<k e h'<h). Defining $D’=\frac{nm}{G’}$, we get:

$\frac{n}{D’}=\frac{G’}{m}=h’\Rightarrow$ D’ divides n

$\frac{m}{D’}=\frac{G’}{n}=k’\Rightarrow$ D’ divides m.

So D’ is a common divisor of n and m.

Furthermore, hypothesis G'<G $\Rightarrow D’=\frac{nm}{G’}>\frac{nm}{G}=D\Rightarrow D’>D \Rightarrow $ D is NOT the GCD, contraddicting initial hypothesis (H).

The contraddiction we got proves the thesis: there are no multiples of n and m less than G, so also (b) is proved.

So G is LCM(n,m).