Use Gauss's lemma! It's a direct application.
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]
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.How?
But we are asked to do a PROOF in this problem...!?
Just do a case-by-case proof that has a solution given that , then , then , and finally . Since those are the only possibilities (even numbers won't work), the conclusion will follow.
Consider Gauss's lemma, and let , and observe that each is its own least positive residue modulo . Let denote the number of integers in the set
.
Then by Gauss's lemma, .
Now comes the tricky part: Let denote the number of even positive integers less than . Then . But what is ? Well, iff is an integer; overwise .
This is the framework that we use for each case. Let's try one in particular...
Suppose . Then is not an integer, which means , and therefore
.
Since , if follows that is odd, which means
.
Therefore has no solution whenever , and we move on to the next case.
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!
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 . But how do you know that (p+1)/2 is even? and why is (p+3)/2 even?
Thanks for clarifying!
Let me put it this way:
the number of even positive integers ;
the number of even positive integers ;
the number of even positive integers between and .
Therefore , or, .
Now, if is odd, then how many even positive integers are ? How about if is even?
The answer, of course, is that if is odd, then there are positive even integers . But if is even, then there are positive even integers .