# 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}\phantom{\rule{veryverythickmathspace}{0ex}}\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\phantom{\rule{veryverythickmathspace}{0ex}}(mod4)$ and ${y}^{2}\equiv 0\phantom{\rule{veryverythickmathspace}{0ex}}(mod4)$.

$\Leftarrow $: Since $p\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(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}+4{y}^{2}$, and if an odd prime $p$ can be written $p={x}^{2}+4{y}^{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 |