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)

Please help!

Printable View

- Jun 5th 2007, 09:14 AMtttcomraderLCM 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)

Please help! - Jun 5th 2007, 09:19 AMThePerfectHacker
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 AMThePerfectHackerQuote:

Originally Posted by**Neils Henrik Abel**

---

$\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 AMtttcomrader
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 AMThePerfectHacker
- Jun 5th 2007, 12:01 PMtttcomrader
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 PMThePerfectHacker
- Jun 5th 2007, 12:43 PMtttcomrader
Oh, I missed that last part, now I fully understand it, thanks!