# Product of GCD and LCM

## Theorem

$\lcm \set {a, b} \times \gcd \set {a, b} = \size {a b}$

where:

$\lcm \set {a, b}$ denotes the lowest common multiple of $a$ and $b$
$\gcd \set {a, b}$ denotes the greatest common divisor of $a$ and $b$.

## Proof 1

It is sufficient to prove that $\lcm \set {a, b} \times \gcd \set {a, b} = a b$, where $a, b \in \Z_{>0}$.

 $\displaystyle d$ $=$ $\displaystyle \gcd \set {a, b}$ $\displaystyle \leadsto \ \$ $\displaystyle d$ $\divides$ $\displaystyle a b$ $\displaystyle \leadsto \ \$ $\, \displaystyle \exists n \in \Z_{>0}: \,$ $\displaystyle a b$ $=$ $\displaystyle d n$

 $\displaystyle d \divides a$ $\land$ $\displaystyle d \divides b$ $\displaystyle \leadsto \ \$ $\, \displaystyle \exists u, v \in \Z: \,$ $\displaystyle a = d u$ $\land$ $\displaystyle b = d v$ $\displaystyle \leadsto \ \$ $\displaystyle d u b = d n$ $\land$ $\displaystyle a d v = d n$ $\displaystyle \leadsto \ \$ $\displaystyle n = b u$ $\land$ $\displaystyle n = a v$ $\displaystyle \leadsto \ \$ $\displaystyle a \divides n$ $\land$ $\displaystyle b \divides n$

Now we have $a \divides m \land b \divides m \implies m = a r = b s$.

Also, by Bézout's Lemma we have $d = a x + b y$.

So:

 $\displaystyle m d$ $=$ $\displaystyle a x m + b y m$ $\displaystyle$ $=$ $\displaystyle b s a x + a r b y$ $\displaystyle$ $=$ $\displaystyle a b \paren {s x + r y}$ $\displaystyle$ $=$ $\displaystyle d n \paren {s x + r y}$

So:

$m = n \paren {s x + r y}$

Thus:

$n \divides m \implies n \le \size m$

while:

$a b = d n = \gcd \set {a, b} \times \lcm \set {a, b}$

as required.

$\blacksquare$

## Proof 2

Let $a = g m$ and $b = g n$, where $g = \gcd \set {a, b}$ and $m$ and $n$ are coprime.

The existence of $m$ and $n$ are proved by Integers Divided by GCD are Coprime.

Since $a = g m \divides g m n$ and $b = g n \divides g m n$, $g m n$ is the LCM of $a$ and $b$.

Then it follows that:

$\lcm \set {a, b} \times \gcd \set {a, b} = g m n \times g = g m \times g n = \size {a b}$

$\blacksquare$

## Proof 3

Let $d := \gcd \set {a, b}$.

Then by definition of the GCD, there exist $j_1, j_2 \in \Z$ such that $a = d j_1$ and $b = d j_2$.

Because $d$ divides both $a$ and $b$, it must divide their product:

$\exists l \in \Z$ such that $a b = d l$

Then we have:

 $\displaystyle d l$ $=$ $\, \displaystyle \paren {d j_1} b \,$ $\, \displaystyle =\,$ $\displaystyle a \paren {d j_2}$ $\displaystyle \leadsto \ \$ $\displaystyle l$ $=$ $\, \displaystyle j_1 b \,$ $\, \displaystyle =\,$ $\displaystyle a j_2$

showing that $a \divides l$ and $b \divides l$.

That is, $l$ is a common multiple of $a$ and $b$.

Now it must be shown that $l$ is the least such number.

Let $m$ be any common multiple of $a$ and $b$.

Then there exist $k_1, k_2 \in \Z$ such that $m = a k_1 = b k_2$.

$\exists x, y \in \Z: d = a x + b y$

So:

 $\displaystyle m d$ $=$ $\displaystyle m a x + m b y$ $\displaystyle$ $=$ $\displaystyle \paren {b k_2} a x + \paren {a k_1} b y$ $\displaystyle$ $=$ $\displaystyle a b \paren {b k_2 + a k_1}$ $\displaystyle$ $=$ $\displaystyle d l \paren {b k_2 + a k_1}$

Thus:

$m = l \paren {b k_2 + a k_1}$

that is, $l \divides m$.

Hence by definition of the LCM:

$\lcm \set {a, b} = l$

In conclusion:

$a b = d l = \gcd \set {a, b} \cdot \lcm \set {a, b}$

$\blacksquare$

## Proof 4

Let:

 $\displaystyle m$ $=$ $\displaystyle {p_1}^{k_1} {p_2}^{k_2} \dotsm {p_r}^{k_r}$ $\displaystyle n$ $=$ $\displaystyle {p_1}^{l_1} {p_2}^{l_2} \dotsm {p_r}r^{l_r}$
$\lcm \set {m, n} = p_1^{\max \set {k_1, l_1} } p_2^{\max \set {k_2, l_2} } \dotsm p_r^{\max \set {k_r, l_r} }$
$\gcd \set {m, n} = p_1^{\min \set {k_1, l_1} } p_2^{\min \set {k_2, l_2} } \dotsm p_r^{\min \set {k_r, l_r} }$

From Sum of Maximum and Minimum, for all $i \in \set {1, 2, \ldots, r}$:

$\min \set {k_i, l_i} + \max \set {k_i, l_i} = k_i + l_i$

Hence:

 $\displaystyle \gcd \set {m, n} \times \lcm \set {m, n}$ $=$ $\displaystyle p_1^{k_1 + l_1} p_2^{k_2 + l_2} \dotsm p_r^{k_r + l_r}$ $\displaystyle$ $=$ $\displaystyle p_1^{k_1} p_1^{l_1} p_2^{k_2} p_2^{l_2} \dotsm p_r^{k_r} p_r^{l_r}$ $\displaystyle$ $=$ $\displaystyle p_1^{k_1} p_2^{k_2} \dotsm p_r^{k_r} \times p_1^{l_1} p_2^{l_2} \dotsm p_r^{l_r}$ $\displaystyle$ $=$ $\displaystyle m n$

$\blacksquare$