# Product of GCD and LCM/Proof 5

## 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 $r, s\in \Z$ such that $a = d r$ and $b = d s$.

Let $m = \dfrac {a b} d$.

Then:

$m = a s = r b$

which makes $m$ a common multiple of $a$ and $b$.

Let $c \in \Z_{>0}$ be a common multiple of $a$ and $b$.

Let us say that:

$c = a u = b v$

From Bézout's Identity:

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

Then:

 $\ds \dfrac c m$ $=$ $\ds \dfrac {c d} {a b}$ $\ds$ $=$ $\ds \dfrac {c \paren {a x + b y} } {a b}$ $\ds$ $=$ $\ds \dfrac c b x + \dfrac c a y$ $\ds$ $=$ $\ds v x + n y$

That is:

$m \divides c$

where $\divides$ denotes divisibility.

$m \le c$

Hence by definition of the LCM:

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

In conclusion:

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

and the result follows.

$\blacksquare$