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: Congruences of quadratic residues

  1. Aug 9, 2010 #1
    Hi,

    I'm slowly reading through the book What is Mathematics which asks the following question at the end of its quadratic residues section. I'm not sure how to begin it really, so any hints/suggestions would be greatly appreciated.

    1. The problem statement, all variables and given/known data
    We have seen that [tex] x^{2} \equiv (p - x)^{2} \pmod p [/tex]. Where p is a prime > 2 and x is not divisible by p
    Show that these are the only congruences among the numbers [tex]1^{2}, 2^{2}, 3^{2},...,(p-1)^{2}[/tex]

    2. Relevant equations
    [tex] (p-x)^{2} = p^{2} - 2px + x^{2}\equiv x^{2} \pmod p [/tex]

    3. The attempt at a solution
    No idea..

    thanks in advance,
    babak
     
  2. jcsd
  3. Aug 9, 2010 #2
    I think we have to define what the author means by "the only congruences among the numbers [itex]1^{2}, 2^{2}, 3^{2},...,(p-1)^{2}[/itex]." I'd say that he means something like:

    If a,b [itex]\in[/itex] {1, 2, ..., p-1}, a [itex]\neq[/itex] b and [itex]a^2 \equiv b^2 (mod p)[/itex], then a = p-b.

    Can you prove that?

    Petek
     
  4. Aug 10, 2010 #3
    Hi Petek,

    Thanks the response. I'm not sure how atm but will give it ago hehe

    cheers
    babak
     
  5. Aug 22, 2010 #4
    Hi Petek,

    Heres what I've come up with, what do you think ?

    [tex]a^{2} \equiv b^{2} \pmod p[/tex]
    [tex]a^{2} - b^{2}\equiv 0 \pmod p[/tex]
    [tex](a-b)(a+b)\equiv 0 \pmod p[/tex]

    [tex](a-b)\equiv 0 \pmod p \texttt{ or } (a+b)\equiv 0 \pmod p[/tex]
    [tex]a+b=p \texttt{ or } a-b=p [/tex]

    [tex]a=p-b \texttt{ as } a\in \left \{ 1, 2,...,p-1 \right \} \texttt{ hence } a<p[/tex]

    thanks alot,
    babak
     
  6. Aug 22, 2010 #5
    Looks good!
     
  7. Aug 22, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    That IS a good start. But it's a little sloppy. i) Where did you use that p is prime? ii) If a and b are in {1...p-1} it's pretty unlikely that a-b=p, don't you think? Can you elaborate a little?
     
    Last edited: Aug 22, 2010
  8. Aug 23, 2010 #7
    Hi Dick,

    Thanks for your comments.

    i) The product [tex](a-b)(a+b)\equiv 0 \pmod p[/tex] is divisible by the prime p only if one of the factors is, so either [tex]a-b\equiv 0[/tex] or [tex]a+b\equiv 0 \pmod p[/tex] must be divisible by p.

    ii) I chose [tex]a+b=p[/tex] as [tex]a \in \left \{1,..,p-1 \right \}[/tex] so will always be < p but with [tex]a-b=p, a=p+b[/tex] which is >p, which isn't possible.

    What do you think ?

    cheers
    babak
     
  9. Aug 23, 2010 #8

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    In your middle term here
    is it not fairly obvious to you that

    p2 - 2px = 0 (mod p) (identity)

    since p is a factor of that bit?
     
  10. Aug 23, 2010 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    i) is right on. ii) is still a little funny. If a number is divisible by p then it must have the form k*p where k is a integer, right? If a and b are in {1...p-1} and a+b is divisible by p then a+b=p, since it can't be 0 and it can't be as large as 2*p. And if a-b is divisible by p shouldn't a-b=0?
     
  11. Aug 30, 2010 #10
    Hi,

    Okay thanks, think I see what you're saying. Is it enough to say..

    since [tex](a+b)(a-b)\equiv 0 \pmod p[/tex] then
    [tex]a+b=np[/tex] or [tex]a-b=kp[/tex] where [tex]a, b \in \left \{ 1, ..., p-1 \right \}[/tex]
    if [tex]a-b=kp[/tex] then [tex]a-b[/tex] will always be < p and hence k is 0. While [tex] 0 < a+b < 2p [/tex]. Hence n is 1 as we've already said that a-b=0.

    Pretty much just re-written what you said before I guess hehe. Am not too sure about the logic for getting to n=1 though..

    cheers!
    babak
     
  12. Aug 31, 2010 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    a+b is a multiple of p. Since it's also between 0 and 2p that means it's equal to p, right? I'm not sure what you are not sure about.
     
  13. Aug 31, 2010 #12
    Riteo dont worry, was just confusing my self hehe.

    thanks for all your help!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook