Product of GCD and LCM

Theorem

$\operatorname{lcm} \left\{{a, b}\right\} \times \gcd \left\{{a, b}\right\} = \left|{a b}\right|$

where:

• $\operatorname{lcm} \left\{{a, b}\right\}$ is the lowest common multiple of $a$ and $b$
• $\gcd \left\{{a, b}\right\}$ is the greatest common divisor of $a$ and $b$.

Proof

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

	\(\displaystyle \)	\(\displaystyle d = \gcd \left\{ {a, b}\right\}\)	\(\implies\)	\(\displaystyle d \backslash a b\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists n \in \Z_{>0}: a b = d n\)	\(\displaystyle \)

	\(\displaystyle \)	\(\displaystyle \)	\(\)	\(\displaystyle d \backslash a \land d \backslash b\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle \exists u, v \in \Z: a = d u \land b = d v\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle d u b = d n \land a d v = d n\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle n = b u \land n = a v\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\implies\)	\(\displaystyle a \backslash n \land b \backslash n\)	\(\displaystyle \)

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

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

So:

	\(\displaystyle \)	\(\displaystyle m d\)	\(=\)	\(\displaystyle a x m + b y m\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle b s a x + a r b y\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle a b \left({s x + r y}\right)\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle d n \left({s x + r y}\right)\)	\(\displaystyle \)

So $m = n \left({s x + r y}\right)$.

Thus $n \backslash m \implies n \le \left|{m}\right|$, while $a b = d n = \gcd \left\{{a, b}\right\} \times \operatorname{lcm} \left\{{a, b}\right\}$ as required.

$\blacksquare$

Sources

• George E. Andrews: Number Theory (1971): $\S 2.2$: Exercise $4$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23 \gamma$