# LCM problem

• June 5th 2007, 09:14 AM
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)

• June 5th 2007, 09:19 AM
ThePerfectHacker
Quote:

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)$.
• June 5th 2007, 10:07 AM
ThePerfectHacker
Quote:

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$
• June 5th 2007, 11:13 AM
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?
• June 5th 2007, 11:27 AM
ThePerfectHacker
Quote:

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.
Quote:

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$.
• June 5th 2007, 12:01 PM
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!
• June 5th 2007, 12:40 PM
ThePerfectHacker
Quote:

I don't understand how a|bc and c|a would implies (a/c)|b.

What are you talking about? I proved the theorem above. Do you understand it?
• June 5th 2007, 12:43 PM