How to prove that at least one solution to $x^2 + y^2 \equiv -1 \pmod p$ exists? [duplicate]
The result is clear for $p=2$, so let $p$ be odd.
For $i=0$ to $\frac{p-1}{2}$, the numbers $i^2$ are distinct modulo $p$. Let $S$ be this set of numbers. Then $S$ has $\frac{p+1}{2}$ elements.
Similarly, let $T$ be the set of numbers of the shape $-j^2-1$, where $j$ ranges from $0$ to $\frac{p-1}{2}$. Then $T$ contains $\frac{p+1}{2}$ numbers that are distinct modulo $p$.
The sum of the cardinalities of $S$ and $T$ is $p+1$. Thus by the Pigeonhole Principle there exist $i$, $j$ such that $i^2\equiv -j^2-1\pmod{p}$. This completes the proof.