LCM Divides Common Multiple

From ProofWiki
Jump to navigation Jump to search

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