4.5 Lowest common multiples

In this section we shall take a brief look at common multiples.

The set of positive common multiples of $a$ and $b$ is non-empty (as it contains $|ab|$, for example), so it has a smallest element. This observation enables us to make the following important definition.

The following result links the highest common factor and the lowest common multiple of two natural numbers.

Proof. Let $d=\mathrm{hcf}(a,b)$, and write $a=d\alpha$ and $b=d\beta$, where $\alpha,\beta\in\mathbb{N}$. Corollary 4.4.6 and Theorem 4.2.17 imply that there are integers $r$ and $s$ such that $r\alpha+s\beta=1$. We shall show that $ab/d$ is the lowest common multiple of $a$ and $b$. Since

we see that $ab/d\in\mathbb{N}$ and that $ab/d$ is a common multiple of $a$ and $b$.

Suppose that $c\in\mathbb{N}$ is a common multiple of $a$ and $b$. Then $c=ma$ and $c=nb$ for some $m,n\in\mathbb{N}$, and we have

Hence $ab/d$ divides $c$. Since $c$ is positive, this implies that $ab/d\leqslant c$, and so $ab/d$ is the smallest positive common multiple of $a$ and $b$, that is, the lowest common multiple of $a$ and $b$. Moreover, (4.5) shows that $ab/d$ divides any common multiple of $a$ and $b$. $\Box$

Thus the common multiples of $a$ and $b$ are precisely the multiples of their lowest common multiple, just as their common factors are precisely the factors of their highest common factor. Note that since replacing $a$ or $b$ with its negative has no effect on the set of common multiples, and thus does not change the lowest common multiple, this result easily extends to any $a,b\in\mathbb{Z}\setminus\{0\}$.