# LCM problem

• Jun 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)

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

Originally Posted by tttcomrader
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.
---
$\displaystyle a|c \mbox{ and }b|c$.

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

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

But,
$\displaystyle \frac{ab}{d} =\mbox{lcm}(a,b)$.
• Jun 5th 2007, 10:07 AM
ThePerfectHacker
Quote:

Originally Posted by Neils Henrik Abel
Use this to show that,
$\displaystyle ab | cd$ where $\displaystyle d=\gcd(a,b)$.

Here are the all the details if you need them.
---
$\displaystyle a|c \Rightarrow c = ak \ \exists \ k\in \mathbb{Z}$
$\displaystyle b|c \Rightarrow c = bj \ \exists \ j \in \mathbb{Z}$

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

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

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

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

Proof: Again, just follow the definitions.
$\displaystyle a|bc \Rightarrow bc = ka \ \exists \ k\in \mathbb{Z}$
$\displaystyle c|a \Rightarrow a=cj \ \exists \ j \in \mathbb{Z} \mbox{ and } j = \frac{a}{c}$
Substitute second equation into first,
$\displaystyle bc = kcj$
Since $\displaystyle c\not =0$ we have,
$\displaystyle b=kj \Rightarrow j | b \Rightarrow \left( \frac{a}{c}\right) | b$
• Jun 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?
• Jun 5th 2007, 11:27 AM
ThePerfectHacker
Quote:

Originally Posted by tttcomrader
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,
$\displaystyle \left(\frac{ab}{d} \right) | c$
But,
$\displaystyle \frac{ab}{d} = \frac{ab}{\gcd(a,b)} = \mbox{lcm}(a,b)$.

Thus, $\displaystyle \mbox{lcm}(a,b)|c$.
• Jun 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!
• Jun 5th 2007, 12:40 PM
ThePerfectHacker
Quote:

Originally Posted by tttcomrader
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?
• Jun 5th 2007, 12:43 PM