1. Not finding help here? Sign up for a free 30min 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!

Prove if a=b(mod n) then a^2=b^2(mod n)

  1. Jul 22, 2012 #1
    1. The problem statement, all variables and given/known data

    This is a question from the book I'm studying called 'Mathematical Proofs: A transition to advanced mathematics'

    2. Relevant equations

    Let a, b, n be integers, with n≥2. Prove that if a[itex]\equiv[/itex]b(mod n), then a2[itex]\equiv[/itex]b2(mod n).

    3. The attempt at a solution

    Following the examples I assumed that I'd start by stating that since a[itex]\equiv[/itex]b(mod n), then a-b=nx... but from this point I'm stuck.

    Any help much appreciated.
     
    Last edited: Jul 22, 2012
  2. jcsd
  3. Jul 22, 2012 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    In other words, n divides a-b. Does n divide a2-b2?
     
  4. Jul 22, 2012 #3
    Yeah. I know its simple but I just don't know how to think about it.
     
  5. Jul 22, 2012 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Are you saying you still don't know how to think about it after my hint? Can you answer my question in the hint?
     
  6. Jul 22, 2012 #5
    LCKurtz has probably provided the most direct way to think about it if you happen to know the well known factorization of the expression a2-b2, but alternatively you could think of it this way:

    You have already stated that a-b=nx, or a=nx+b, for some integer x.

    Can you find an integer, say y, such that a2=ny+b2 ?
     
  7. Jul 22, 2012 #6
    I was saying that I could see that it looks pretty obvious that if n divides a-b, it will divide a2-b2, but that I didn't know how to prove it.

    Using oay's hint about factorisation I've got a2-b2=(a+b)(a-b) and since n divides a-b, n therefore divides a2-b2 but this is looking very different to the examples in the book.

    OK, after a pause to try again I think I've got it (with the help of oay's other hint):

    Assume n divides a-b, then a=nx+b. Therefore a2=(nx+b)2=n2x2+2bnx+b2=n(nx2+2bx)+b2. Since a2=n(nx2+2bx)+b2 and nx2+2bx is an integer, a2-b2=n(nx2+2bx). Therefore a2[itex]\equiv[/itex]b2(mod n).

    Is that right?
     
  8. Jul 22, 2012 #7
    Spot on! :smile:
     
  9. Jul 22, 2012 #8
    Great! Thank you both for your help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove if a=b(mod n) then a^2=b^2(mod n)
  1. Mod-2 function? (Replies: 2)

Loading...