Modular Arithmetic Proof: How to Solve with Help | Homework Statement

[JPanthon]

Homework Statement

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


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

Homework Equations

Modular arithmetic rules.

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

 

[I like Serena]

Hi JPanthon!

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.

 

[JPanthon]

Hi JPanthon!

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.

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?

 

[I like Serena]

In math, (a mod n) means the set of "a plus any integer times n", also denoted as: $\bar a = \{ a + q n| q \in \mathbb Z \}$
(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+q₁n, add it to b+q₂n, and show that it can be written as (a+b)+q₃n.

 

[JPanthon]

In math, (a mod n) means the set of "a plus any integer times n", also denoted as: $\bar a = \{ a + q n| q \in \mathbb Z \}$
(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+q₁n, add it to b+q₂n, and show that it can be written as (a+b)+q₃n.

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

 

[epenguin]

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:

It's more philosophical than the computational math you're probably used to, so don't feel like you're wasting time by just carefully thinking about the problem without writing anything down. Hope that helps.

 

[epenguin]

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.

 

[I like Serena]

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.