Prove If LCM(a,b) = c and a|k and b|k then c|k.

Question

Prove If LCM(a,b) = c and a|k and b|k then c|k.

I know that c divides a and b if c = Least Common Multiple of a and b.

I also know that c divides all multiples of a and b.

I just am not sure how to go about proving it.

Answer 1

I will use this notation: if $p$ is any prime and $r\geq 2$ is a natural number, then $\mu_p(r)$ is the power that $p$ is raised to in the prime factorization of $r$. For example, $\mu_5(150)=2$ and $\mu_2(21)=0$.

We shall show that for each $p^n$ that divides $c$, (where $p$ is a prime and $n$ is a natural number) $p^n$ also divides $k$.

Indeed, if $p^n$ divides $c$, then $\mu_p(c)\geq n$, but $\mu_p(c)=\max\{\mu_p(a),\mu_p(b)\}$. Thus, $p^n$ divides $a$ or $b$. Since $a$ and $b$ divide $k$, $p^n$ also divides $k$.

Now, we have $\mu_p(k)\geq\mu_p(c)$, and this is true for every prime $p$. This means that $c$ divides $k$.

Answer 2

By the Division Algorithm, $k=qc+r$ where $0\le r<c$.

Then $a|k$ and $a|c\implies a|r$, $\;\;$and $\;\;$$b|k$ and $b|c\implies b|r$.

Since $r$ is a common multiple of $a$ and $b$ with $r<c$, $r=0$.