representing primes as $x^2+ny^2$ RepresentingPrimesAsX2ny2 2006-03-30 19:35:17 2006-09-06 14:25:55 Theorem % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here \newcommand{\Ints}{\mathbb{Z}} \newcommand{\Rats}{\mathbb{Q}} \textbf{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$. \textbf{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$. \newline $\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.