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: Proving remainders?

  1. Sep 27, 2012 #1
    1. The problem statement, all variables and given/known data
    I have to prove "If a is congruent a (mod b) then a and b have the same remainders when divided by n.
    I'm in a intro to proof class and we havent gone into much detail about this topic. In fact this is the first proof dealing with remainders I have to prove. Not sure if i did it right though?

    2. Relevant equations

    3. The attempt at a solution

    Here is my proof:
    Assume n|(a-b) implies ns=a-b where sεZ. Let a=nk+r1 where 0≤n<n. This means that ns=nk+r1-b then nk-ns+r1=b where n(k-s)+r1. Since k-sεZ then a and b both share the same remainder.
    Last edited: Sep 27, 2012
  2. jcsd
  3. Sep 27, 2012 #2


    Staff: Mentor

    What is the exact problem statement? Your statement seems to be missing some important parts. What you have doesn't make any sense.

    How can n < n?
  4. Sep 27, 2012 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    First of all, the statement of your problem,
    "If a is congruent a (mod b) then a and b have the same remainders"​
    Doesn't make sense.

    After looking at your proof, I suspect that the problem reads something like:
    If a ≡ b (mod n), then a and b have the same remainders upon division by n .​

    Your proof the following error, probably a typo.

    Let a=nk+r1 where 0≤n<n. should be: Let a=nk+r1 where 0 ≤ r1 < n.

    Are you starting your proof by Assuming n|(a-b) ? You should instead say that n|(a-b) is what it means for a ≡ b (mod n) .

    My other question to you is, what allows you to state, "Let a=nk+r1 ..." ? You should probably mention what allows you to state that.
  5. Sep 27, 2012 #4
    Assume n≡a (mod b) which means n|(a-b). n|(a-b) implies ns=a-b where sεZ. Since a is divided by n then a=nk+r1 where 0≤r1<n where r1 represents the remainder. This means that ns=nk+r1-b = nk-ns+r1=b where n(k-s)+r1=b. Since k-sεZ then a and b both share the same remainder.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook