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

    Mark44

    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

    SammyS

    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