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

Homework Help: Divisibility proof

  1. Sep 18, 2006 #1
    I'm having trouble with this question, I need to prove or disprove this statement: If c divides (a+b), but c does not divide a, then c does not divide b.

    what i have so far is ck = (a+b) where k is some integer. Next I have a=ck-b and b=ck-a. I tried doing things like a = ck-(ck-a) but that got me nowhere. Any ideas? Thanks in advance.
     
  2. jcsd
  3. Sep 19, 2006 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If c divides b, try writing b in terms of c, then go back to a=ck-b
     
  4. Sep 19, 2006 #3

    HallsofIvy

    User Avatar
    Science Advisor

    Try proof by contradiction: Suppose c does divide b. Then b= cn for some n so c= a+ cn. What does a equal? Why is that a contradiction?
     
  5. Sep 19, 2006 #4
    Thanks for the help. I think theres a problem though, shouldn't C = (a+b)n for some integer n? Instead of c= a + cn, it should be c divides a + cn.

    I tried the following c = (a +cn)k where k is another integer, so
    a = (c/k) - cn but I can't figure out where to go from there. Thanks
     
  6. Sep 19, 2006 #5

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Orikon, there's a small typo in Halls' post.

    c divides b => nc = b
    c divides a+b => kc = a+b = a+nc {not the other way round}

    So what can you say about a?
     
  7. Sep 20, 2006 #6
    so,
    kc = a + nc
    a = kc - nc
    a = c(k-n)

    which means c must also be divisible by a when c is divisible by b. That's the contrapositive of the original statement, so it must be true, right? :biggrin: Thank you so much!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook