Let p be an odd prime. Prove that the congruence x2 is congruent to -1 mod p has no solutions for p is congruent to 3 mod 4 and exactly two solutions when p is congruent to 1 mod 4. [Hint: Think of orders.]
Suppose for some then since thus: if then , but since thus .
By Fermat's Little Theorem: and hence i.e. .
So there can be no solutions when .
Suppose , then
Now, by Wilson's Theorem , and since we have , thus and a solution exists.
The fact that there are exactly 2 solutions to follows easily from the fact that if you have then either or
- I suppose you have not gone over quadratics residues, just as a comment this will get much more generalised when you get there.