Results 1 to 13 of 13

Math Help - Quadratic Residues & Legendre symbol

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Quadratic Residues & Legendre symbol

    Let p be an odd prime. Prove that x^2 2 (mod p) has solutions if and only if p 1 or 7 (mod 8).

    The related materials in the section are quadratic residues, and the Legendre symbol, but I can't figure out how to prove this.

    Any help is appreciated!


    [also under discussion in math links forum]
    Last edited by kingwinner; February 28th 2010 at 04:13 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Use Gauss's lemma! It's a direct application.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    How?
    But we are asked to do a PROOF in this problem...!?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by kingwinner View Post
    Let p be an odd prime. Prove that x^2 2 (mod p) has solutions if and only if p 1 or 7 (mod 8).

    The related materials in the section are quadratic residues, and the Legendre symbol, but I can't figure out how to prove this.

    Any help is appreciated!


    [also under discussion in math links forum]
    How?
    But we are asked to do a PROOF in this problem...!?
    Sounds like you're using the Niven textbook. I did this exercise last fall, and it gave be some trouble too. It is indeed proved by Gauss's lemma.

    Just do a case-by-case proof that x^2\equiv 2\pmod{p} has a solution given that p\equiv 1, then p\equiv 3, then p\equiv 5, and finally p\equiv 7\pmod{8}. Since those are the only possibilities (even numbers won't work), the conclusion will follow.

    Consider Gauss's lemma, and let a=2, and observe that each i\in\{2,4,6,\cdots,p-1\} is its own least positive residue modulo p. Let n denote the number of integers in the set

    \left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}.

    Then by Gauss's lemma, \left(\frac{2}{p}\right)=(-1)^n.

    Now comes the tricky part: Let m denote the number of even positive integers less than p/2. Then n=[(p-1)/2]-m. But what is m? Well, m=(p-1)/4 iff (p-1)/4 is an integer; overwise m=(p-3)/4.

    This is the framework that we use for each case. Let's try one in particular...

    Suppose p\equiv 3\pmod{8}. Then \frac{p-1}{4} is not an integer, which means m=\frac{p-3}{4}, and therefore

    n=\frac{p-1}{4}-m=\frac{p-1}{2}-\frac{p-3}{4}=\frac{p+1}{4}.

    Since p\equiv 3\pmod{8}, if follows that n=\frac{p+1}{4} is odd, which means

    \left(\frac{2}{p}\right)=(-1)^n=-1.

    Therefore x^2\equiv 2\pmod{p} has no solution whenever p\equiv 3\pmod{8}, and we move on to the next case.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    It's such a tricky question...

    So you showed that p 3(mod 8) => no solution

    How can we prove that THERE IS a solution when e.g. p 7 (mod 8)? What do we have to show?

    Also, in this question, we are asked to prove IF AND ONLY IF, right? So how can we prove the "converse" direction?

    Thanks for helping!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by kingwinner View Post
    It's such a tricky question...

    So you showed that p 3(mod 8) => no solution

    How can we prove that THERE IS a solution when e.g. p 7 (mod 8)? What do we have to show?

    Also, in this question, we are asked to prove IF AND ONLY IF, right? So how can we prove the "converse" direction?

    Thanks for helping!
    It's the same method, only with a different conclusion.

    Suppose p\equiv 1\pmod{8}. Then \frac{p-1}{4} is an integer, which means

    n=\frac{p-1}{4}-m=\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}.

    And since \frac{p-1}{4} is even then \left(\frac{2}{p}\right)=(-1)^n=1.

    So x^2\equiv 2\pmod{p} has a solution.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by hatsoff View Post
    It's the same method, only with a different conclusion.

    Suppose p\equiv 1\pmod{8}. Then \frac{p-1}{4} is an integer, which means

    n=\frac{p-1}{4}-m=\frac{p-1}{2}-\frac{p-1}{4}=\frac{p-1}{4}.

    And since \frac{p-1}{4} is even then \left(\frac{2}{p}\right)=(-1)^n=1.

    So x^2\equiv 2\pmod{p} has a solution.
    OK. But for "if and only if" statements, I think we have to prove BOTH directions, right?

    So far we've only showed one direction.
    How can we prove (conversely) that
    x^2 2 (mod p) has solutions => p 1 or 7 (mod 8) ?

    thanks.
    Last edited by kingwinner; March 1st 2010 at 05:18 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by kingwinner View Post
    OK. But for "if and only if" statements, I think we have to prove BOTH directions, right?

    So far we've only showed one direction.
    How can we prove (conversely) that
    x^2 2 (mod p) has solutions => p 1 or 7 (mod 8) ?

    thanks.
    If we prove there are no solutions for p\equiv 3,5\pmod{8}, then it follows that there may only be solutions if p\equiv 1,7\pmod{8} (because p is odd).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by hatsoff View Post
    If we prove there are no solutions for p\equiv 3,5\pmod{8}, then it follows that there may only be solutions if p\equiv 1,7\pmod{8} (because p is odd).
    Oh, yes, that's proof by contrapositive.

    Thank you!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by hatsoff View Post
    Sounds like you're using the Niven textbook. I did this exercise last fall, and it gave be some trouble too. It is indeed proved by Gauss's lemma.

    Just do a case-by-case proof that x^2\equiv 2\pmod{p} has a solution given that p\equiv 1, then p\equiv 3, then p\equiv 5, and finally p\equiv 7\pmod{8}. Since those are the only possibilities (even numbers won't work), the conclusion will follow.

    Consider Gauss's lemma, and let a=2, and observe that each i\in\{2,4,6,\cdots,p-1\} is its own least positive residue modulo p. Let n denote the number of integers in the set

    \left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}.

    Then by Gauss's lemma, \left(\frac{2}{p}\right)=(-1)^n.
    Now I've acutally read this and Gauss' lemma more carefully, and I have a question.

    In our problem, the list of the residues are {2,4,6,...,p-1}, note that they are all even, but then Gauss' lemma says: let n be the number of these residues that are greater than p/2.

    However, in your proof, you said that n is the number of integers in \left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}. But how do you know that (p+1)/2 is even? and why is (p+3)/2 even?

    Thanks for clarifying!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by kingwinner View Post
    Now I've acutally read this and Gauss' lemma more carefully, and I have a question.

    In our problem, the list of the residues are {2,4,6,...,p-1}, note that they are all even, but then Gauss' lemma says: let n be the number of these residues that are greater than p/2.

    However, in your proof, you said that n is the number of integers in \left\{\frac{p+1}{2},\frac{p+3}{2},\cdots,p-1\right\}. But how do you know that (p+1)/2 is even? and why is (p+3)/2 even?

    Thanks for clarifying!
    Oops.... Yes, I meant to write "let n denote the number of even integers" in that set. Sorry for the confusion.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Smile

    Quote Originally Posted by hatsoff View Post
    Now comes the tricky part: Let m denote the number of even positive integers less than p/2. Then n=[(p-1)/2]-m. But what is m? Well, m=(p-1)/4 iff (p-1)/4 is an integer; overwise m=(p-3)/4.
    Sorry, one more question...

    Can you explain in more detail why m=(p-1)/4 iff (p-1)/4 is an integer; otherwise m=(p-3)/4 ? I don't understand this part.

    Thanks a lot!
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2008
    Posts
    410
    Quote Originally Posted by kingwinner View Post
    Sorry, one more question...

    Can you explain in more detail why m=(p-1)/4 iff (p-1)/4 is an integer; otherwise m=(p-3)/4 ? I don't understand this part.

    Thanks a lot!
    Let me put it this way:

    m= the number of even positive integers <p/2;

    (p-1)/2= the number of even positive integers <p;

    n= the number of even positive integers between p/2 and p.

    Therefore \frac{p-1}{2}=m+n, or, n=\frac{p-1}{2}-m.

    Now, if \frac{p-1}{2} is odd, then how many even positive integers are <p/2? How about if \frac{p-1}{2} is even?

    The answer, of course, is that if \frac{p-1}{2} is odd, then there are \frac{p-3}{4} positive even integers <p/2. But if \frac{p-1}{2} is even, then there are \frac{p-1}{4} positive even integers <p/2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic Residue/Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 20th 2010, 06:55 PM
  2. [SOLVED] Legendre Symbol
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: October 31st 2010, 10:01 AM
  3. Legendre symbol
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: April 12th 2010, 06:57 PM
  4. Legendre Symbol and Quadratic Reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 25th 2010, 09:31 AM
  5. Legendre Symbol (5/p)
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: December 11th 2009, 04:37 AM

Search Tags


/mathhelpforum @mathhelpforum