# Proving that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\ (mod\ p)$

How can I prove that for every prime number $p$ there exist $a,b \in \mathbb{Z}$ such that $-1 \equiv a^2+b^2\pmod p$?

If $p=2$ then $-1=1$ so $-1=1^2+0^2$. Now when $p>2$, let $S$ be the set of squares of $\Bbb Z/p$. Then $|S|={p+1\over 2}$. Now consider the set $-1-S = \{-1-s: S\in S\}$. This has the same cardinality, and since
$$|S|+|-1-S|>p$$
it must be that there is an element in their intersection, call it $c$ then $a^2=c$ for some $a$ since $c\in S$. But also there is $b$ so that $c= -1-b^2$ since $c\in -1-S$. So
$$a^2=-1-b^2\iff a^2+b^2=-1.$$
Note: there is nothing special about $-1$, in face every element works with this argument and so all things mod $p$ are the sum of two squares.
Hint: The case $p=2$ is trivial. For odd $p$, use $\frac{p+1}{2}+\frac{p+1}{2}>p$.