1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help me with algebra proof

  1. Sep 28, 2011 #1
    1. The problem statement, all variables and given/known data

    Question 1.


    2. Relevant equations

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

    3. The attempt at a solution

    I used the division algorithm


    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. jcsd
  3. Sep 28, 2011 #2
    Substitute a and b from the first and second equation in the third equation. What do you get??

  4. Sep 28, 2011 #3
    (q1)n+(q2)n + r1 + r2 = (q3)n+r

    Is this what you meant?
  5. Sep 28, 2011 #4
    Yes, that is good. Now rearrange a bit and you got the proof!!
  6. Sep 28, 2011 #5
    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.
  7. Sep 28, 2011 #6
    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?
  8. Sep 28, 2011 #7
    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.
  9. Sep 28, 2011 #8
    What is the definition of a=b (mod n) ????
  10. Sep 28, 2011 #9
    a = q1n + a

    You mean that?
  11. Sep 28, 2011 #10
    Don't you mean [itex]a=q_1 n+b[/itex]??

    Well, that's the same thing I posted, no?? Just rearrange, and you get [itex]a-b=qn[/itex]...
  12. Sep 28, 2011 #11
    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 [itex]a-b=qn[/itex]. 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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook