# 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.

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

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

Now remember the definition of Least Common Multiple. $\displaystyle \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 $\displaystyle a$ and $\displaystyle b$.

So in our case, if $\displaystyle r >0$ then $\displaystyle r$ is positive integer which is a common multiple of $\displaystyle a$ and $\displaystyle 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- $\displaystyle r=0$ which is indeed a common multiple of $\displaystyle a$ and $\displaystyle b$