representing primes as $x^2+n{y}^2$

Theorem 1 (Fermat).

An odd prime $p$ can be written $p\mathrm{=}{x}^{\mathrm{2}}\mathrm{+}{y}^{\mathrm{2}}$ with $x\mathrm{,}y\mathrm{\in }\mathrm{Z}$ if and only if $p\mathrm{\equiv }\mathrm{1}\mathrm{(}\mathrm{mod}\mathrm{4}\mathrm{)}$.

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(mod4)$ and $y^2\equiv 0(mod4)$.
$\Leftarrow$: Since $p\equiv 1(mod4)$, 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=\text{N}(p)=\text{N}(a+bi)\text{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+n{y}^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+n{b}^2=c^2+n{d}^2$.

This argument relies on two things: first, that $-n$ is a square $modp$ (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+n{y}^2$ if and only if $\left(\frac{-n}{p}\right)=1$, while for the other $n$ ($3,\mathrm{\hspace{0.17em}7},\mathrm{\hspace{0.17em}11},\mathrm{\hspace{0.17em}19},\mathrm{\hspace{0.17em}43},\mathrm{\hspace{0.17em}67},\mathrm{\hspace{0.17em}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+n{y}^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+n{y}^2$ if and only if $\left(\frac{-n}{p}\right)=1$, i.e. $-n$ is a square $modp$. We have thus proven

Theorem 2.

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

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

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

References

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

Title	representing primes as $x^2+n{y}^2$
Canonical name	RepresentingPrimesAsX2ny2
Date of creation	2013-03-22 15:49:28
Last modified on	2013-03-22 15:49:28
Owner	rm50 (10146)
Last modified by	rm50 (10146)
Numerical id	17
Author	rm50 (10146)
Entry type	Theorem
Classification	msc 11A41
Related topic	ThuesLemma2