Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Suggestion for proof

  1. Sep 23, 2004 #1
    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. jcsd
  3. Sep 23, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

    There's a nice proof using the fundemental theorem of algebra.
  4. Sep 23, 2004 #3
    I'm sorry NateTG, I don't follow. Can you please elaborate?
  5. Sep 23, 2004 #4
    I think you might mean Fundamental Theorem of Arithmetic.
  6. Sep 23, 2004 #5


    User Avatar
    Science Advisor
    Homework Helper

    Yep. Sorry. Apparently I need to sleep more.
  7. Sep 23, 2004 #6
    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.
  8. Sep 23, 2004 #7


    User Avatar
    Science Advisor
    Homework Helper

    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.
  9. Sep 23, 2004 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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]
    Last edited: Sep 23, 2004
  10. Sep 24, 2004 #9
    I knew it was something trivial I didn't see. Thanks NateG and Goku.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook