Product of GCD and LCM/Proof 2

From ProofWiki
Jump to navigation Jump to search

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

It follows that:

$a = g m \divides g m n$

and:

$b = g n \divides g m n$

So $g m n$ is a common multiple of $a$ and $b$.


Hence there exists an integer $g k \le g m n$ that is divisible by both $a$ and $b$.

Then:

\(\ds a\) \(=\) \(\ds g m\)
\(\ds \leadsto \ \ \) \(\ds g m\) \(\divides\) \(\ds g k\)
\(\ds \leadsto \ \ \) \(\ds m\) \(\divides\) \(\ds k\)


\(\ds b\) \(=\) \(\ds g n\)
\(\ds \leadsto \ \ \) \(\ds g n\) \(\divides\) \(\ds g k\)
\(\ds \leadsto \ \ \) \(\ds n\) \(\divides\) \(\ds k\)


As $g k \le g m n$, it follows that:

$k \le m n$

But $m, n$ are coprime.

So:

\(\ds \map \lcm {m, n}\) \(=\) \(\ds m n\)
\(\ds \leadsto \ \ \) \(\ds k\) \(\not <\) \(\ds m n\)
\(\ds \leadsto \ \ \) \(\ds k\) \(=\) \(\ds m n\)
\(\ds \leadsto \ \ \) \(\ds g k\) \(=\) \(\ds g m n\)
\(\ds \) \(=\) \(\ds \map \lcm {a, b}\)
\(\ds \leadsto \ \ \) \(\ds \lcm \set {a, b} \times \gcd \set {a, b}\) \(=\) \(\ds g m n \times g\)
\(\ds \) \(=\) \(\ds g m \times g n\)
\(\ds \) \(=\) \(\ds \size {a b}\)

$\blacksquare$