representing primes as x2+ny2

Theorem 1 (Fermat).

An odd prime p can be written p=x2+y2 with x,yZ if and only if p1(mod4).


: 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 x21(mod4) and y20(mod4).
: Since p1(mod4), by Euler’s Criterion we have that (-1p)=1 where (np) is the Legendre symbolMathworldPlanetmath. Choose k such that pk2+1. Working in [i] we have k2+1=(k+i)(k-i). Then pk2+1, but p does not divide either factor since pk. Hence p is not prime. Since [i] is a UFD, it follows that p is not irreduciblePlanetmathPlanetmath 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


Since neither factor has norm 1, we must have p=a2+b2=c2+d2, so p is the sum of two squares. ∎

There are more elementary proofs of , but one can try to generalize the given proof for arbitrary n. When can p be written as x2+ny2,n>0? By analogy with the proof for n=1, suppose we find k such that pk2+n (i.e. that (-np)=1). Then in [-n], it follows that k2+n=(k+-n)(k--n), so again p is not prime since it does not divide either factor. If [-n] is a UFD, then p is not irreducible either. We can then write as before p=(a+b-n)(c+d-n) and, taking norms, we get the same result: p=a2+nb2=c2+nd2.

This argumentPlanetmathPlanetmath relies on two things: first, that -n is a square modp (i.e. that (-np)=1); second, that [-n] is a UFD. It is known that the only imaginary quadratic rings (-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 [-n] is the ring of integersMathworldPlanetmath are n=1,2.

So for n=1,2, and p an odd prime, p=x2+ny2 if and only if (-np)=1, while for the other n (3, 7, 11, 19, 43, 67, 163), the ring of integers of (n) is not [-n], so [-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 (-np)=1 if and only if p is represented by a primitive form ( of discriminantPlanetmathPlanetmathPlanetmathPlanetmath ( -4n. So if there is only one reduced form ( with that (which must perforce be the x2+ny2), then we are done. But h(-4n)=1n=1,2,3,4,7 (see this article ( n=1 and n=2 were dealt with above. n=4 is the form x2+4y2, and if an odd prime p can be written p=x2+4y2, then clearly we have also p=x2+(2y)2; conversely, if p=x2+y2, then either x or y is even, so that also p=x2+2(y)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 x2+ny2 if and only if (-np)=1, i.e. -n is a square modp. We have thus proven

Theorem 2.

If n=1, 2, 3, 4, or 7, then an odd prime p can be written as p=x2+ny2 with x, yZ if and only if


i.e. if and only if -n is a square modp.


Cox, D.A. “Primes of the Form x2+ny2: Fermat, Class Field Theory, and Complex MultiplicationMathworldPlanetmath”, Wiley 1997.

Title representing primes as x2+ny2
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