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

Modular Arithmetic Proof, Help Needed

  1. Sep 27, 2011 #1
    1. The problem statement, all variables and given/known data

    Suppose a, b, n are integers with n >/= 2
    Prove that:

    (a + b) mod n = ((a mod n) + (b mod n)) mod n

    2. Relevant equations

    Modular arithmetic rules.

    3. The attempt at a solution

    r1 = a(modn)
    => a = q1n + r1

    r2 = bmodn
    => b = q2n + r2

    r1 + r2 = a - q1n + b - q2n
    = (a + b) + (-q1 - q2)n

    Here is where I have no idea where to go. :S
  2. jcsd
  3. Sep 27, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    Hi JPanthon! :smile:

    This is where you are done.
    (a mod n) means "a" plus an integer times "n".
    You have proven that (a mod n) plus (b mod n) equals (a+b) plus an integer times n, which is what you had to prove. :wink:
  4. Sep 27, 2011 #3
    Thank you for your reply :)

    So, "((a mod n) + (b mod n)) mod n" means (a+b) plus an integer times n?

    Could you help me see this?
  5. Sep 27, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    In math, (a mod n) means the set of "a plus any integer times n", also denoted as: [itex]\bar a = \{ a + q n| q \in \mathbb Z \}[/itex]
    (b mod n) means "b plus any integer times n".
    ((a+b) mod n) meant "a+b plus any integer times n".

    It should be clear that if you add the first two, you get something that is the same as the third.

    Edit: The way to prove it, is to write out what (a mod n) means, which is a+q1n, add it to b+q2n, and show that it can be written as (a+b)+q3n.
  6. Sep 27, 2011 #5
    Thank you again. If you would just help me once more.

    It's this part I don't understand: ((a mod n) + (b mod n)) mod n

    I understand how I've proven (a+b)modn = a(modn) + b(modn) ,
    but not a(modn) + b(modn) = ((amodn) + b(modn)) modn
  7. Sep 27, 2011 #6


    User Avatar
    Homework Helper

    Not boasting but frankly this is obvious to me. We'd like it to be obvious to you.

    (a mod n) + (b mod n) means you divide one number a by n and you get a remainder, you divide another number b by n and you get another remainder. The sum of these remainders you'd expect to be the same as what you'd get if you, to save time, divided (a + b) by n.
    Except if this sum turned out equal or bigger than n, in which case to get it (mod n) you'd subtract n from it in that case, so that's your [a (mod n) + b (mod n)](mod n) .

    I hope that's obvious, and if not do what will help you in a lot of cases like this, do a simple example - let for example n be 7. Let a be 8 and b 9. Let a be 13 and b be 12. Then you'll have and example of both cases I just mentioned.

    Notice that the final (mod n) is kind of overpowered. You're only ever going to get zero or one notches above n IYKWIM. Using a simple example to clarify is one technique suggested by Polya in his little book 'How to solve it'. But another thing he says is 'when you've solved the prob the job's not finished'. Think how could you naturally extend this. What about (a + b + c) (mod n)? Or something more general. If you got the habit of thinking that sort of thing right through, you'd begin to feel confident and on top.

    A lot of students here sound to me as if they had their noses one inch in front of the paper with the problem and it intimidates them. Learning is being discussed on another thread, and although exercises and active work are necessary, I tend to agree with this:
  8. Sep 28, 2011 #7


    User Avatar
    Homework Helper

    Later I thought of this simple thing.

    You have been doing modular arithmetic for a long time.

    In ordinary addition of numbers the last digit of a sum is the sum (mod 10).

    Or if you bring together your cents from here and there and you can change every 100c into a dollar bill, then the small change, the coins you have left is the sum (mod 100).

    The theorem is obvious in these cases and so are the extensions I mentioned, or if it isn't try a few examples.
  9. Sep 28, 2011 #8

    I like Serena

    User Avatar
    Homework Helper

    I see epenguin already explained it.

    I'd like to add that the reason you're getting this sort of problem, is due to the following.

    Suppose you need to calculate ((13 + 9) mod 8), with possibly numbers that are much larger.

    What you need to know, is that:
    ((13 + 9) mod 8) = (((13 mod 8) + (9 mod 8)) mod 8) = ((5 + 1) mod 8) = (6 mod 8)

    But of course you can only use this, if you can be sure it is true, which it is.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook