# Thread: least common multiple and division theorem

1. ## least common multiple and division theorem

Q: (We denote the least common multiple of a and b by [a,b] or lcm[a,b])

Give a proof by contradiction that if a positive integer n is a common multiple of a and b then [a,b] divides n.

(Hint: Use the division theorem. If [a,b] does not divide n then n=[a,b]q+r where 0<r<[a,b]. Now prove that r is a common multiple of a and b.)

My proof that r is a common multiple of a and b:
r=n-[a,b]q
n=au=av
[a,b]=m=ax=by

r=a(u-xq)=b(v-yq)

Is that correct? Also, how does r being a common multiple of a and b provide a contradiction?

2. What you did is correct save for a typo.

$
r = n - {\text{lcm}}\left( {a,b} \right) \cdot q
$

Okay you know that $
r
$
is a common multiple of $a$ and $b$. We have $0\le r<\text{lcm}(a,b)$ (1) by the definition of the remainder.

Now remember the definition of Least Common Multiple. $\text{lcm}(a,b)=
\min \left\{ {x \in \mathbb{Z}^ + /x = \dot a \wedge x = \dot b} \right\}
$
(2) In other words, it is the smallest positive integer such that it is a multiple of both $a$ and $b$.

So in our case, if $r >0$ then $r$ is positive integer which is a common multiple of $a$ and $b$, and in fact smaller (1) than the smallest positive integer satisfying this (2)! This is a contradiction!

Thus it must be -only case remaining- $r=0$ which is indeed a common multiple of $a$ and $b$