Suggestion for proof

1. Sep 23, 2004

Yoss

Let a and b be natural numbers and LCM(a,b) = m.
Prove that if GCD(a,b) = 1, then LCM(a,b) = ab.

What I got so far was that since b|LCM(a,b), then b*k = LCM(a,b) for some natural number k. I know I need to show that k </= a and k >/= a so I get a = k. And show that b*k = ba = LCM(a,b).

I can get a </= k:

Since LCM(a,b) = m, then a|m and b|m. Since LCM(a,b) = m = b*k, then a|bk. <And by the Euclid's Lemma, if a|bc and GCD(a,b) = 1, then a|c>. So
a|k. So a*j = k for some natural number j, and therefore a </= k.

I'm sure I have to derive that a >/= k by the antecedent. I'm trying to use the property that GCD(a,b) = 1 = a*x + b*y for some integers x and y by showing that k|a. But I'm stuck.

Any suggestions? Thanks

Edit: Maybe I should have posted this in Number Theory. Mod, can you move it if you think it should be there?

Last edited: Sep 23, 2004
2. Sep 23, 2004

NateTG

There's a nice proof using the fundemental theorem of algebra.

3. Sep 23, 2004

Yoss

I'm sorry NateTG, I don't follow. Can you please elaborate?

4. Sep 23, 2004

Yoss

I think you might mean Fundamental Theorem of Arithmetic.

5. Sep 23, 2004

NateTG

Yep. Sorry. Apparently I need to sleep more.

6. Sep 23, 2004

Yoss

Am I even on the right track? It feels like I'm missing some trivial property that I need to solve this. Can anyone suggest something, and perhaps how to apply the FTA to this? Thanks.

7. Sep 23, 2004

NateTG

Yeah, I think you're almost there.
You're trying to prove that $$a \geq k$$, right?
You might want to use the fact that $$LCM(a,b) \leq ab$$ since $$ab$$ is obviously a common multiple.

8. Sep 23, 2004

Gokul43201

Staff Emeritus
Also, the more general result :(a,b)*((a,b)) = ab where () is GCD, (( )) is LCM follows directly from

$$(a,b) = \prod_i p_i^{min(k_i,l_i)} ~~$$ and

$$((a,b)) = \prod_i p_i^{max(k_i,l_i)}~~$$ where

$$a = \prod_i p_i^{k_i} ~~$$ and

$$b = \prod_i p_i^{l_i}$$

Last edited: Sep 23, 2004
9. Sep 24, 2004

Yoss

I knew it was something trivial I didn't see. Thanks NateG and Goku.