# Math Help - LCM problem

1. ## LCM problem

Q: Prove if a|k, b|k, then lcm(a,b)|k.

(Hint: LCM of non-zero intergers a and b is the smallest postive integer m such that a|m, b|m)

Q: Prove if a|k, b|k, then lcm(a,b)|k.

(Hint: LCM of non-zero intergers a and b is the smallest postive integer m such that a|m, b|m)

Say these are positive integers.
---
$a|c \mbox{ and }b|c$.

Use this to show that,
$ab | cd$ where $d=\gcd(a,b)$.

Then that means,
$\left( \frac{ab}{d} \right) | c$

But,
$\frac{ab}{d} =\mbox{lcm}(a,b)$.

3. Originally Posted by Neils Henrik Abel
Use this to show that,
$ab | cd$ where $d=\gcd(a,b)$.
Here are the all the details if you need them.
---
$a|c \Rightarrow c = ak \ \exists \ k\in \mathbb{Z}$
$b|c \Rightarrow c = bj \ \exists \ j \in \mathbb{Z}$

Let $d=\gcd(a,b)$ then that means:
$d = ax+by \ \exists \ x,y\in \mathbb{Z}$

Now, by the above statements,
$cd = c(ax+by) = acx + bcy = abjx+abky = ab(jx+ky) \Rightarrow ab|cd$

Definition: Let $a|b$. For $a\not =0$ we define $\frac{b}{a} = c$ so that $b=ac$.

Theorem: Let $a|bc$ and $c|a \mbox{ with }c\not =0$. Then $\left( \frac{a}{c} \right) | b$.

Proof: Again, just follow the definitions.
$a|bc \Rightarrow bc = ka \ \exists \ k\in \mathbb{Z}$
$c|a \Rightarrow a=cj \ \exists \ j \in \mathbb{Z} \mbox{ and } j = \frac{a}{c}$
Substitute second equation into first,
$bc = kcj$
Since $c\not =0$ we have,
$b=kj \Rightarrow j | b \Rightarrow \left( \frac{a}{c}\right) | b$

4. The k that you use in your proof with c = ak, is that the same k as the one given in the problem?

And how does the lcm = m fit in this?

The k that you use in your proof with c = ak, is that the same k as the one given in the problem?
No. I used different letters.
And how does the lcm = m fit in this?
Because I show that,
$\left(\frac{ab}{d} \right) | c$
But,
$\frac{ab}{d} = \frac{ab}{\gcd(a,b)} = \mbox{lcm}(a,b)$.

Thus, $\mbox{lcm}(a,b)|c$.

6. I understand this proof, but would you mind proving the theorem? I don't understand how a|bc and c|a would implies (a/c)|b.

thanks so much!