Theorem (Fermat). An odd prime $p$ can be written $p=x^2+y^2$ with $x,y\in\Ints$ , if and only if $p \equiv 1 \pmod 4$ .

Proof $\Rightarrow$ : This direction is obvious. Since $p$ is odd, exactly one of $x,y$ is odd. If (say) $x$ is odd and $y$ is even, then $x^2\equiv 1\pmod 4$ and $y^2\equiv 0\pmod 4$ .
$\Leftarrow$ : Since $p \equiv 1 \pmod 4$ , by Euler's Criterion we have that $\left(\frac{-1}{p}\right)=1$ where $\left(\frac{n}{p}\right)$ is the Legendre symbol. Choose $k$ such that $p|k^2+1$ . Working in $\Ints[i]$ we have $k^2+1=(k+i)(k-i)$ . Then $p|k^2+1$ , but $p$ does not divide either factor. Hence $p$ is not prime. Since $\Ints[i]$ is a UFD, it follows that $p$ is not irreducible either, so we can write $p=(a+bi)(c+di)$ , where neither factor is a unit (i.e. neither factor has norm $1$ ). Taking norms, we get $$ p^2=\mbox{N}(p)=\mbox{N}(a+bi)\mbox{N}(c+di)=(a^2+b^2)(c^2+d^2 $$ Since neither factor has norm $1$ , we must have $p=a^2+b^2=c^2+d^2$ , so $p$ is the sum of two squares.

One can try to generalize this proof for arbitrary $n$ . When can $p$ be written as $x^2+ny^2, n>0$ ? By analogy with the proof for $n=1$ , suppose we find $k$ such that $p|k^2+n$ (i.e. that $\left(\frac{-n}{p}\right)=1$ ). Then in $\Ints[\sqrt{-n}]$ , it follows that $k^2+n=(k+\sqrt{-n})(k-\sqrt{-n})$ , so again $p$ is not prime since it does not divide either factor. If $\Ints[\sqrt{-n}]$ is a UFD, then $p$ is not irreducible either. We can then write as before $p=(a+b\sqrt{-n})(c+d\sqrt{-n})$ and, taking norms, we get the same result: $p=a^2+nb^2=c^2+nd^2$ .

This argument relies on two things: first, that $-n$ is a square $\mod p$ (i.e. that $\left(\frac{-n}{p}\right)=1$ ); second, that $\Ints[\sqrt{-n}]$ is a UFD. It is known that the only imaginary quadratic rings $\Rats(\sqrt{-n})$ that are UFDs are those for $n=1,2,3,7,11,19,43,67,163$ , and the only $n$ in that set for which $\Ints[\sqrt{-n}]$ is the ring of integers are $n=1,2$ .

So for $n=1,2$ , and $p$ an odd prime, $p=x^2+ny^2$ if and only if $\left(\frac{-n}{p}\right)=1$ , while for the other $n$ ($3,\,7,\,11,\,19,\,43,\,67,\,163$ ), the ring of integers of $\Rats(\sqrt{n})$ is not $\Ints[\sqrt{-n}]$ , so $\Ints[\sqrt{-n}]$ is not integrally closed and thus is not a UFD and hence this proof will not work for those values of $n$ .

The result that $p=x^2+ny^2$ if and only if $\left(\frac{-n}{p}\right)=1$ holds for several values of $n$ other than $1$ and $2$ , but the proofs take other paths. See [Cox] for a complete discussion of this fascinating question.

References

Cox, D.A. ``Primes of the Form $x^2 + ny^2$ : Fermat, Class Field Theory, and Complex Multiplication'', Wiley 1997.