# LCM Divides Common Multiple

## Theorem

Let $a, b \in \Z$ such that $a b \ne 0$.

Let $n$ be any common multiple of $a$ and $b$.

That is, let $n \in \Z: a \divides n, b \divides n$.

Then:

- $\lcm \set {a, b} \divides n$

where $\lcm \set {a, b}$ is the lowest common multiple of $a$ and $b$.

In the words of Euclid:

*If two numbers measure any number, the least number measured by them will also measure the same.*

(*The Elements*: Book $\text{VII}$: Proposition $35$)

## Proof

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

Then $a \divides m$ and $b \divides m$ by definition.

Suppose $n$ is some other common multiple of $a$ and $b$ such that $m \nmid n$ ($m$ does not divide $n$).

Then from the Division Theorem:

- $n = k m + r$

for some integer $k$ and with $0 < r < m$.

Then since $r = n - k m$, using $a \divides n$ and $a \divides m$:

- $a \divides r$

Similarly:

- $b \divides r$

Then $r$ is a common multiple of $a$ and $b$.

But we have that $r < m$.

This contradicts the fact that $m$ is the lowest common multiple of $a$ and $b$.

So, by contradiction, it follows that $m \divides n$.

$\blacksquare$

## Historical Note

This proof is Proposition $35$ of Book $\text{VII}$ of Euclid's *The Elements*.

## Sources

- 1926: Sir Thomas L. Heath:
*Euclid: The Thirteen Books of The Elements: Volume 2*(2nd ed.) ... (previous) ... (next): Book $\text{VII}$. Propositions - 1971: Allan Clark:
*Elements of Abstract Algebra*... (previous) ... (next): Chapter $1$: Properties of the Natural Numbers: $\S 23 \gamma$