# Modular Arithmetic proofs (multiplication and addition mod n)

1. Sep 7, 2011

### Elwin.Martin

1. The problem statement, all variables and given/known data
Let n be a fixed positive integer greater than 1. If a (mod n) = a' and b (mod n) = b', prove that (a+b) (mod n) = (a'+b') (mod n) and that (ab) (mod n) = (a'b') (mod n)

2. Relevant equations
When a = qn + r
a mod n = r

3. The attempt at a solution
(a'+b') (mod n) = (a (mod n) + b (mod n)) (mod n)
= ((a+b) (mod n)) (mod n)
= (a+b) (mod n)
(a'b') (mod n) = (a (mod n) * b (mod n)) (mod n)
= ((ab) mod n) mod n
= (ab) mod n

Is this a valid approach? My reasoning is that if we treat mod n as an operation on a number, then we can mod n twice and we should get the same thing since any remainder divided by the same number should yield the same number.

I know that my work isn't very rigorous and I didn't really apply the definition I have directly, can anyone point me in another direction if this is the wrong approach?

Elwin

2. Sep 7, 2011

### SammyS

Staff Emeritus
You might want to show this in a more rigorous way.

3. Sep 7, 2011

### Elwin.Martin

Sorry if this is a bit silly to ask, but how does one show modular arithmetic operations rigorously in general? My text is a bit casual when discussing the material and the closest thing there is to a definition in this section is that "when a = nq+r where q is the quotient and r is the remainder then a mod n = r." Is this all I need then, or is there some formal definitions for additions/multiplication etc. that I'm missing?

Elwin

4. Sep 7, 2011

### SammyS

Staff Emeritus
I have to admit that I was thinking of something called 'congruence mod n', which is somewhat different, although closely related. You will probably cover it soon, if you haven't already done so.

The 'mod' you have here appears to be a mathematical operation. You're right that a (mod n) = r means that a = qn +r for some integers, q and r, furthermore, 0 ≤ r < n. Note: this means that 0 ≤ a (mod n) < n, since (a (mod n)) = r.

It's not necessarily true that (a (mod n) + b (mod n)) = (a + b) (mod n).

Yes, 0 ≤ a (mod n) < n and 0 ≤ b (mod n) < n, but all that tells you is that 0 ≤ a (mod n) + b (mod n) < 2n .

Use qa , qb ra & rb & see what you can come up with.

You will have to look at two cases:

(Case 1) 0 ≤ a (mod n) + b (mod n) < n

(Case 2) n ≤ a (mod n) + b (mod n) < 2n

5. Sep 7, 2011

### Elwin.Martin

It's not necessarily true that (a (mod n) + b (mod n)) = (a + b) (mod n).
^
Okay, I've got that part now.
0 ≤ a (mod n) + b (mod n) < 2n
Since we're dealing with integers, is it worth strengthening this statement?
0 ≤ a (mod n) + b (mod n) ≤ 2n-2 since a (mod n) ≤ n - 1 & b (mod n) ≤ n - 1
Or is that not true?

6. Sep 9, 2011

### SammyS

Staff Emeritus
(Sorry, I've been traveling rhe last two days.)

Yes, it's true, but not important.