Existence of Lowest Common Multiple

Theorem

Let $a, b \in \Z: a b \ne 0$.

The lowest common multiple of $a$ and $b$, denoted $\operatorname{lcm} \left\{{a, b}\right\}$, always exists.

Proof

• We prove its existence thus:

$a b \ne 0 \implies \left\vert{a b}\right\vert \ne 0$

Also $\left\vert{a b}\right\vert = \pm a b = a \left({\pm b}\right) = \left({\pm a}\right) b$.

So it definitely exists, and we can say that $0 < \operatorname{lcm} \left\{{a, b}\right\} \le \left\vert{a b}\right\vert$.

• Now we prove it is the lowest. That is: $a \backslash n \land b \backslash n \implies \operatorname{lcm} \left\{{a, b}\right\} \backslash n$.

Let $a, b \in \Z: a b \ne 0, m = \operatorname{lcm} \left\{{a, b}\right\}$.

Let $n \in \Z: a \backslash n \land b \backslash n$.

We have:

• $n = x_1 a = y_1 b$;
• $m = x_2 a = y_2 b$.

As $m > 0$, we have:

	\(\displaystyle \)	\(\displaystyle n\)	\(=\)	\(\displaystyle m q + r: 0 \le r < \left\vert{m}\right\vert = m\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle r\)	\(=\)	\(\displaystyle n - m q\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 1 \times n + \left({-q}\right) \times m\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle r\)	\(=\)	\(\displaystyle x_1 a + \left({-q}\right) x_2 a\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle y_1 b + \left({-q}\right) y_2 b\)	\(\displaystyle \)
	\(\displaystyle \implies\)	\(\displaystyle a\)	\(\backslash\)	\(\displaystyle r\)	\(\displaystyle \)
	\(\displaystyle \land\)	\(\displaystyle b\)	\(\backslash\)	\(\displaystyle r\)	\(\displaystyle \)

Since $r < m$, and $m$ is the smallest positive common multiple of $a$ and $b$, it follows that $r = 0$.

So $\forall n \in \Z: a \backslash n \land b \backslash n: \operatorname{lcm} \left\{{a, b}\right\} \backslash n$, that is $\operatorname{lcm} \left\{{a, b}\right\}$ divides any common multiple of $a$ and $b$.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 23 \gamma$