1. Limited time only! Sign up for a free 30min personal 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!

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


    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


    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


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