Modular Arithmetic proofs (multiplication and addition mod n)

[Elwin.Martin]

Homework Statement

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)

Homework Equations

When a = qn + r
a mod n = r

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?

Thank you for your time,
Elwin

 

[SammyS]

...
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.
...

Thank you for your time,
Elwin

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

 

[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?

Thank you for your response,
Elwin

 

[SammyS]

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 q_a , q_b r_a & r_b & 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

 

[Elwin.Martin]

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 q_a , q_b r_a & r_b & 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

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?

 

[SammyS]

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

Yes, it's true, but not important.