1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

GCD and LCM Proof Help Needed

  1. Oct 13, 2008 #1
    I am *totally* blanking on how to even begin on this one.

    I need to prove that the gcd(a,b) | lcm[a,b].


    I know that means that a| lcm[a,b] and that b | lcm[a,b]
    but I don't really know where to go from there.

    I think a small kickstart is all I really need for now. :)

    Thanks!
     
  2. jcsd
  3. Oct 13, 2008 #2

    Vid

    User Avatar

    prime factorization
     
  4. Oct 13, 2008 #3
    I guess I need help that much more basic. As I don't have any real clue, w/o googling that term, what prime factorization is.
     
  5. Oct 13, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Use the definition 0f "lcm" and "gdc".
     
  6. Oct 13, 2008 #5
    Here's what I have so far. C = gcd(a,b) and X = lcm[a,b]

    the lcm of [a,b] means that x | a and x | b.
    The gcd means that C | X.

    I have written a in terms of a = some integer times x. same thing with b.

    but I don't know where to go from there.
     
  7. Oct 13, 2008 #6
    Did I say something dumb and scary everyone away? ;)
     
  8. Oct 13, 2008 #7
    Sorry for barging in the topic, but it seems that you need to recheck your definitions precisely.
     
  9. Oct 13, 2008 #8
    To the best of my knowledge they are correct. Would you mind saying that exactly is incorrect? I've been trying to figure out that the whole time. ;)
     
  10. Oct 13, 2008 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    a | lcm(a,b) and b | lcm(a,b). Not necessarily the reverse.
     
  11. Oct 13, 2008 #10
    Any hints on how that integrates into the problem? As you can see, I've extremely confused.
     
  12. Oct 13, 2008 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If i | j and j | k then i | k. Use that.
     
  13. Oct 13, 2008 #12
    Let me see where you're going with this.

    i is the GCD? k is the LCM?
    But what would be J?

    I've always extremely disliked proofs because of the "abstract" and non concrete answers they always give. Too much open interpretation for me in my math. ;)
     
  14. Oct 13, 2008 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think you have two choices for j. You can flip a coin if you want. You'll be right either way. :)
     
  15. Oct 13, 2008 #14
    I am never sure what to assume is ok "to assume" and what isn't. Can I just write?

    a | lcm(a,b)
    gcd(a,b) | a

    so gcd(a,b) | lcm(a,b)

    That makes sense to me and is what I wanted to write a hour or two ago. But I convinced myself that it was wrong.
     
  16. Oct 13, 2008 #15

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I'd be interested to know how you convinced yourself it was wrong. You must be very persuasive.
     
  17. Oct 13, 2008 #16
    Well I thought there was something I need to write that a | lcm(a,b)
    and that gcd(a,b) | a

    Thought if you say it outloud it seems d'uh easy huh?

    Here's the next one I guess I'll try to tackle now that I'm "on a roll". ;)

    gcd(a,a+2) = {2 if a even, 1 if a is odd}

    wish me luck!
     
  18. Oct 13, 2008 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Good thing you look up the definitions. That's all the justification you need. Good luck on the next one.
     
  19. Oct 13, 2008 #18
    Here's what I got for the even odd one so far.

    Taking the even case:
    even means a = 2k where k is some integer.

    where x is the GCD:
    x | 2k
    x | 2k + 2

    by a theorem, this means that x | 2k + 2k + 2 or x | 4k + 2

    After this I don't where to go.
     
  20. Oct 13, 2008 #19

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If x | 2k then either x | 2 or x | k. 2k+2=2*(k+1). So if x | 2*(k+1) then either x | 2 or x | (k+1). Can x divide both k AND k+1?
     
  21. Oct 14, 2008 #20
    I see what you're saying but how does that prove the answer HAS to be 2?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: GCD and LCM Proof Help Needed
  1. GCD and LCM (Replies: 2)

Loading...