• Support PF! Buy your school textbooks, materials and every day products Here!

Modular Arithmetic Proof, Help Needed

  • Thread starter JPanthon
  • Start date
  • #1
20
0

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
 

Answers and Replies

  • #2
I like Serena
Homework Helper
6,577
176
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:
 
  • #3
20
0
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:
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?
 
  • #4
I like Serena
Homework Helper
6,577
176
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.
 
  • #5
20
0
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.
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
 
  • #6
epenguin
Homework Helper
Gold Member
3,724
765
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.
 
  • #7
epenguin
Homework Helper
Gold Member
3,724
765
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.
 
  • #8
I like Serena
Homework Helper
6,577
176
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.
 

Related Threads on Modular Arithmetic Proof, Help Needed

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
22
Views
9K
  • Last Post
Replies
2
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
23
Views
2K
Top