Prove That GCD(a,b) = 1 Implies LCM(a,b) = ab

[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?

 

[NateTG]

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

 

[Yoss]

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

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

 

[Yoss]

I think you might mean Fundamental Theorem of Arithmetic.

 

[NateTG]

I think you might mean Fundamental Theorem of Arithmetic.

Yep. Sorry. Apparently I need to sleep more.

 

[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.

 

[NateTG]

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

 

[Gokul43201]

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

[tex] (a,b) = \prod_i p_i^{min(k_i,l_i)} ~~[/tex] and

[tex] ((a,b)) = \prod_i p_i^{max(k_i,l_i)}~~ [/tex] where

[tex] a = \prod_i p_i^{k_i} ~~[/tex] and

[tex] b = \prod_i p_i^{l_i} [/tex]

 

[Yoss]

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

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