Existence of solution in finite field . Show that a solution always exists for $X^2+Y^2 = -1$ in any finite field $\mathbb{Z}_p$.
For $p$'s of the form $4n +1$, it's easy to prove that by taking $Y =0$. I couldn't figure out how to tackle the other case.
 A: Write your equation as $X^2 = -1-Y^2 \pmod{p}$ and use the pigeonhole principle. Note that $x \mapsto x^2 \pmod{p}$ assumes $ \frac{p+1}{2}$ many different values. This method even shows that $-1$ can be replaced with an arbitrary value.
A: There is an overkilling solution, using the Chevalley-Warning Theorem.  Let $q$ be a prime power.  The polynomial $X^2+Y^2+Z^2 \in \mathbb{F}_q[X,Y,Z]$ has one root $(X,Y,Z)=(0,0,0)$.  The degree of this polynomial is $2$, which is less than the number of variables (namely, $3$).  By the Chevalley-Warning Theorem, it has another root $(X,Y,Z)=(x,y,z)$.  Without loss of generality, assume that $z\neq 0$, which means that we can divide $x$, $y$, and $z$ by $z$.  Hence, we can assume also that $z=1$.  This means $x^2+y^2+1=0$ in $\mathbb{F}_q$.
A: The cases $p=2,3,5,7$ can be handled by inspection. For $p \ge 11$ we can even show that any non-$0$ member of $Z_p$ is equal to $a^2+b^2$ for some non-zero $a,b$, with $a^2 \ne b^2$. Proof: Let $S= \{ {x^2 | 0 \ne x \in Z_p} \}$, let $T=(Z_p - S) - \{ 0 \}$, let $ A= \{ y+z | y,z \in S , y \ne z\ \} - \{ 0 \}$. Observe that if $c \in S \cap A$ then $S=cS \subset A$, and if $d \in  T \cap A$ then $T=dS \subset A$,and since $S \cup T=Z_p- \{ 0 \}$, it suffices to show $$T \cap A \ne \phi \ne S \cap A.$$First,suppose instead,  that $T \cap A = \phi$, so $A \subset S$, so $5=2^2+1^2 \in A \cap S$. (Recall $p \ge 11$ so $5 \ne 0 \ne 2$ mod $p$).But then for $5 \le n \le p-1$ we have $$n \in S \cap A \implies n \in S \implies n+1=n+1^2 \in A \implies n+1 \in S \cap A$$ ,so the only non-squares of
 $Z_p$ lie among $\{ 2,3 \}$ which implies $p  \le 5$, a contradiction.Therefore $$T \cap A \ne \phi .$$ Second, to show that $S \cap A \ne \phi$, we have ( modulo $p$) $3^2 \ne 0 \ne 4^2$ and $3^2+4^2=5^2 \ne 0$ and $4^2-3^2=9 \ne 0$.
