# Product of GCD and LCM/Proof 3

## 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

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:

 $\ds d l$ $=$ $\, \ds \paren {d j_1} b \,$ $\, \ds = \,$ $\ds a \paren {d j_2}$ $\ds \leadsto \ \$ $\ds l$ $=$ $\, \ds j_1 b \,$ $\, \ds = \,$ $\ds 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:

 $\ds m d$ $=$ $\ds m a x + m b y$ $\ds$ $=$ $\ds \paren {b k_2} a x + \paren {a k_1} b y$ $\ds$ $=$ $\ds a b \paren {b k_2 + a k_1}$ $\ds$ $=$ $\ds 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$