LCM Divides Common Multiple

From ProofWiki

Jump to: navigation, 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 \backslash n, b \backslash n$.

Then:

$\operatorname{lcm} \left\{{a, b}\right\} \backslash n$

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

Let $m = \operatorname{lcm} \left\{{a, b}\right\}$.

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

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

$n = km + r$

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

Then since $r = n - km$, using $a \backslash n$ and $a \backslash m$, we have $a \backslash r$.

Similarly, we also have $b \backslash r$.

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

But this contradicts $r < m$ because $m$ is the least common multiple of $a$ and $b$.

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

$\blacksquare$