What Steps Can Solve This Modular Arithmetic Proof?

[kramer733]

Homework Statement

Question 1.

http://people.math.carleton.ca/~mezo/A2math1102-11.pdf

Homework Equations

r1 = a modn
r2 = b modn
r = (a+b) modn

The Attempt at a Solution

I used the division algorithm

So:

a = (q1)n + r1
b = (q2)n + r2
(a+b) = (q3)n + r

i isolated for r1 and r2 to get more equations

r1 = a - (q1)n
r2 = b - (q2)n
r = (a+b) - (q3)n

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

I then added a and b together to get the following:

a+b = r1+r2 + n(q1+q2)

After that, i`m completely lost.

This is for question 1 by the way. I've been toying around with this question for 15 hours and i still can't do anything with it. I thought i proved it before but then i realized it wasn't a proof. Please help. I'm dying.
Also another thing that I'm having trouble with is 3. I don't understand why it's worth 10 marks. All i see is me setting equation 1 and 2 equal to each other. I don't understand what's so special about that.

 

[micromass]

Homework Statement

Question 1.

http://people.math.carleton.ca/~mezo/A2math1102-11.pdf

Homework Equations

r1 = a modn
r2 = b modn
r = (a+b) modn

The Attempt at a Solution

I used the division algorithm

So:

a = (q1)n + r1
b = (q2)n + r2
(a+b) = (q3)n + r

Substitute a and b from the first and second equation in the third equation. What do you get??

i isolated for r1 and r2 to get more equations

r1 = a - (q1)n
r2 = b - (q2)n
r = (a+b) - (q3)n

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

I then added a and b together to get the following:

a+b = r1+r2 + n(q1+q2)

After that, i`m completely lost.

This is for question 1 by the way. I've been toying around with this question for 15 hours and i still can't do anything with it. I thought i proved it before but then i realized it wasn't a proof. Please help. I'm dying.

 

[kramer733]

(q1)n+(q2)n + r1 + r2 = (q3)n+r

Is this what you meant?

 

[micromass]

(q1)n+(q2)n + r1 + r2 = (q3)n+r

Is this what you meant?

Yes, that is good. Now rearrange a bit and you got the proof!

 

[kramer733]

Yes, that is good. Now rearrange a bit and you got the proof!

I don't think it's that obvious to me. To be honest, I've already tried doing that and I'm not sure but maybe i don't truly know how mods truly work. if i isolated for r1 + r2, then i'd get the following:

r1 + r2 = n(q3 - q2 - q1) + r

r1 = amodn
r2 = bmodn
r = (a+b)modn

I'm not exactly sure how it works i guess. Could you help me? It'd be greatly appreciated.

 

[micromass]

Well, a=b (mod n) if there is a q such that qn=a-b. Agreed??

Well, you've shown now that r1 + r2 - r = n(q3 - q2 - q1). Doesn't this prove it?

 

[kramer733]

Well, a=b (mod n) if there is a q such that qn=a-b. Agreed??

Well, you've shown now that r1 + r2 - r = n(q3 - q2 - q1). Doesn't this prove it?

To be honest, i don't really understand why a=b (mod n) if there is a q such that qn = a-b"

Where'd that come from? Could you explain please? I'm sorry but it's really just not that obvious to me.

 

[micromass]

To be honest, i don't really understand why a=b (mod n) if there is a q such that qn = a-b"

Where'd that come from? Could you explain please? I'm sorry but it's really just not that obvious to me.

What is the definition of a=b (mod n) ?

 

[kramer733]

What is the definition of a=b (mod n) ?

a = q1n + a

You mean that?

 

[micromass]

a = q1n + a

You mean that?

Don't you mean a=q_1 n+b??

Well, that's the same thing I posted, no?? Just rearrange, and you get a-b=qn...

 

[kramer733]

Don't you mean a=q_1 n+b??

Well, that's the same thing I posted, no?? Just rearrange, and you get a-b=qn...

Actually i don't know but i think i posted it wrong. shouldn't it be ,

b = qn + a, a = bmodn. That's how our professor wrote it in the form as atleast. Now I'm confused.I also really don't see how r1 + r2 - r = n(q3 - q2 - q1) proves it. Like I just don't see what this result means in relation to a-b=qn. Like it's telling us to prove (a+b)modn = (amodn+bmodn)modn. I'm just not seeing the connection