Equation $x^2 + y^2 + 1 = 0$ (mod $p$)

Question

How to prove that equation $x^2 + y^2 + 1 = 0$ (mod $p$) has roots?

Hints are acceptable.

Answer 1

Hint: Let $p$ be an odd prime. Note that $x^2$ takes on $\frac{p+1}{2}$ distinct values modulo $p$, and so does $-(y^2+1)$. Now use the Pigeonhole Principle.