# representing primes as $x^{2}+ny^{2}$

###### Theorem 1 (Fermat).

An odd prime $p$ can be written $p=x^{2}+y^{2}$ with $x,y\in\mathbb{Z}$ 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\mid k^{2}+1$. Working in $\mathbb{Z}[i]$ we have $k^{2}+1=(k+i)(k-i)$. Then $p\mid k^{2}+1$, but $p$ does not divide either factor since $p\nmid k$. Hence $p$ is not prime. Since $\mathbb{Z}[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}=\textrm{N}(p)=\textrm{N}(a+bi)\textrm{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. ∎

There are more elementary proofs of $\Leftarrow$, but one can try to generalize the given 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\mid k^{2}+n$ (i.e. that $\left(\frac{-n}{p}\right)=1$). Then in $\mathbb{Z}[\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 $\mathbb{Z}[\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 $\mathbb{Z}[\sqrt{-n}]$ is a UFD. It is known that the only imaginary quadratic rings $\mathbb{Q}(\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 $\mathbb{Z}[\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 $\mathbb{Q}(\sqrt{n})$ is not $\mathbb{Z}[\sqrt{-n}]$, so $\mathbb{Z}[\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 cases $n=3$ and $n=7$ can be dealt with by the following relatively simple argument (which, as you can see, does not generalize further): Corollary 6 in the article on representation of integers by equivalent integral binary quadratic forms states that if $p$ is an odd prime not dividing $n$, then $\left(\frac{-n}{p}\right)=1$ if and only if $p$ is represented by a primitive form (http://planetmath.org/IntegralBinaryQuadraticForms) of discriminant    (http://planetmath.org/RepresentationOfIntegersByEquivalentIntegralBinaryQuadraticForms) $-4n$. So if there is only one reduced form (http://planetmath.org/ReducedIntegralBinaryQuadraticForms) with that (which must perforce be the $x^{2}+ny^{2}$), then we are done. But $h(-4n)=1\iff n=1,2,3,4,7$ (see this article (http://planetmath.org/ThereIsAUniqueReducedFormOfDiscriminant4nOnlyForN12347)). $n=1$ and $n=2$ were dealt with above. $n=4$ is the form $x^{2}+4y^{2}$, and if an odd prime $p$ can be written $p=x^{2}+4y^{2}$, then clearly we have also $p=x^{2}+(2y)^{2}$; conversely, if $p=x^{2}+y^{2}$, then either $x$ or $y$ is even, so that also $p=x^{2}+2(y^{\prime})^{2}$. Thus $n=4$ has the same set of solutions as $n=1$. But we do get two new cases, $n=3$ and $n=7$, for which have shown that $p$ is representable as $x^{2}+ny^{2}$ if and only if $\left(\frac{-n}{p}\right)=1$, i.e. $-n$ is a square $\mod p$. We have thus proven

###### Theorem 2.

If $n=1$, $2$, $3$, $4$, or $7$, then an odd prime $p$ can be written as $p=x^{2}+ny^{2}$ with $x$, $y\in\mathbb{Z}$ if and only if

 $\left(\frac{-n}{p}\right)=1$

i.e. if and only if $-n$ is a square $\mod p$.

References

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

Title representing primes as $x^{2}+ny^{2}$ RepresentingPrimesAsX2ny2 2013-03-22 15:49:28 2013-03-22 15:49:28 rm50 (10146) rm50 (10146) 17 rm50 (10146) Theorem msc 11A41 ThuesLemma2