If a number is divisible by two others, then it's divisible by their lcm

Question

Prove that if $c$ is a common multiple of $a$ and $b$, then $c$ is a multiple of $\operatorname{lcm}(a,b)$

Nobody in my class has found a way to do it. Whatever I try, I always come to the conclusion that I need the exact same thing I'm trying to prove...to finish my proof.

Our instructor gave a hint though, saying 'if $c$ is a counterexample, then $c-\operatorname{lcm}(a,b)$ is a counterexample'. Unfortunately, I don't understand the hint. I tried to execute induction and proof by contradiction, but nothing leads anywhere.

Answer 1

To prove is that every common multiple of $a,b$ is a multiple of the lcm.

Suppose $d=lcm(a,b)$ and $d \nmid c$ then we have $c=dx+y$ with $0\lt y \lt d$

So $y=c-dx$ and $a,b|(c-dx)$ which is a contradiction with the assumption that $d$ is the lcm.

Answer 2

An alternative, but equivalent, constructive proof: Let $A\triangleq\{m_1, m_2, \cdots\}$ be the set of all common multiples of $a$ and $b$, with $m_1<m_2<\cdots$. We'll show that $m_k=k\cdot m_1$, where $m_1$ is obviously the lcm, and $k\ge 1.$

Proof: Consider $m_2$ first. Since $m_1$ and $m_2$ are both common multiples of $a$ and $b$, clearly so is $m_2-m_1$, i.e. $m_2-m_1\in A$. It follows that $m_2-m_1=m_1$, as $m_2$ is the smallest element in $A$ that's greater than $m_1$. Hence $m_2=2m_1$. By the same token, $m_3-m_2=m_4-m_3=\cdots=m_1$, implying $m_k=k\cdot m_1$.