# Help me with algebra proof

1. Sep 28, 2011

### kramer733

1. The problem statement, all variables and given/known data

Question 1.

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

2. Relevant equations

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

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

Last edited: Sep 28, 2011
2. Sep 28, 2011

### micromass

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

3. Sep 28, 2011

### kramer733

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

Is this what you meant?

4. Sep 28, 2011

### micromass

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

5. Sep 28, 2011

### kramer733

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.

6. Sep 28, 2011

### micromass

Staff Emeritus
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?

7. Sep 28, 2011

### kramer733

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.

8. Sep 28, 2011

### micromass

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

9. Sep 28, 2011

### kramer733

a = q1n + a

You mean that?

10. Sep 28, 2011

### micromass

Staff Emeritus
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$...

11. Sep 28, 2011

### kramer733

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

Last edited: Sep 29, 2011