Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0$ satisfying the congruence $a^2 + b^2 \equiv -1$(mod $p$). [duplicate]

Let $p > 2$ be prime. Show that there exist integers $a,b \geq 0$ satisfying the congruence $a^2 + b^2 \equiv -1$(mod $p$).

A few things that can be seen instantly: $p \equiv 1$ mod $4$, and I am contemplating using Wilsons theorem: $(p-1)! \equiv -1$ mod $p$.

Alternatively there is the consideration of sets $\{1+a^2 : 0 \leq a \leq \frac{p-1}{2} \}$ and $\{-b^2 : 0 \leq b \leq \frac{p-1}{2} \}$,

Is it true that $1+ a^2 = -b^2$ and hence $a^2 + b^2 \equiv -1$ mod $p$ ? I'm sure this isn't completely correct, nor is it rigorous enough - can anyone tell me the answer?

marked as duplicate by user26486, Ewan Delanoy, wythagoras, Mark Bennet, user147263 May 31 '15 at 16:32

• I don't understand "$p\equiv 1$ mod $4$". – TonyK May 31 '15 at 13:24
Consider those two sets. These are two subsets of $\mathbf{Z}/p\mathbf{Z}$ of order $\frac{p+1}{2}$ each. Since $\mathbf{Z}/p\mathbf{Z}$ has p elements, and the sum of the cardinalities o the two sets is $p+1>p$, then these two sets must intersect. Could you continue?