$x^2+y^2=p$ has a solution in $\mathbb{Z}$

Question

Show that $x^2+y^2=p$ has a solution in $\mathbb{Z}$ if and only if $ p≡1 \mod 4$. Thnx, if someone can help

Answer 1

My favorite way of doing this:

$\mathbb{Z}[i]$ is a UFD, so this has a solution iff $\mathbb{Z}[i]/(p)$ is not an integral domain. But $\mathbb{Z}[i]$ is constructed via a quotient, so you can show it's isomorphic to $\mathbb{Z}_p[t]/(x^2 + 1)$, where I'm using $\mathbb{Z}_p$ to denote $\mathbb{Z}/p\mathbb{Z}$. Now, if this new ring is not an integral domain, then $x^2 + 1$ must factor into linear factors over $\mathbb{Z}/p\mathbb{Z}$. So, there is $x$ in the finite field such that $x^2 = -1$. So why is this being solvable equivalent to $p \equiv 1 \pmod 4$?

$(\Rightarrow)$ What does $x^4 = 1$ say about the group $(\mathbb{Z}/p\mathbb{Z})^*$?

$(\Leftarrow)$ This direction is harder! But note that since $x^2 - 1 = 0$ can only have two solutions, $-1$ is the only order 2 element of $(\mathbb{Z}/p\mathbb{Z})^*$ (The other is, of course 1. Unless $-1 = 1$, in which case $p =2$ and this can be handled separately.)

Answer 2

Hints:

$$\begin{align*}\bullet&\;\;\;\Bbb Z_p:=\Bbb Z/p\Bbb Z\;\;\text{is a field whenever $\;p\;$ is a prime}\\ \bullet&\;\;\;\text{Doing arithmetic modulo $\;p\;$ :}\;x^2+y^2=p=0\;\wedge\;\;xy\neq 0\iff\left(\frac xy\right)^2=-1\\ \bullet&\;\;\;\left|\;\Bbb Z_p^*\;\right|=p-1\\{}\\ \bullet&\;\;\;\exists\; a\in \Bbb Z_p^*\;\;s.t.\;\;a^2=-1\iff p=1\pmod 4\end{align*}$$