# Primes of the form $x^2+ny^2$ and congruences.

The answer of following classical problem is surely known, but I can't find a reference

For which positive integer $n$ is the set $S_n$ of primes of the form $x^2+n y^2$ ($x$, $y$ integers) determined by congruences?

A set of prime $S$ is said determined by congruences if there is a positive integer $m$ and a set $A \subset (\mathbb{Z}/m\mathbb{Z})^\ast$ such that a prime $p$ not dividing $m$ is in $S$ if and only if $p$ modulo $m$ is in $A$. There is a natural place to look for this question: the book by Cox "primes number of the form $x^2+ny^2"$". Unfortunately I don't have it, my library doesn't have it, and I can't find it on the internet, except for some preview at Amazon and Google. From the table of content and the preview it seems that the book does not contain the answer to my question (otherwise I wouldn't ask) but it is still possible that the answer be hidden precisely in one of the sporadic pages that amazon doesn't want me to see.

From that book one knows that a prime $p$ is in $S_n$ if and only if it splits in the ring class field $L_n$ of the order $\mathbb{Z}[\sqrt{-n}]$ in the quadratic imaginary field $K_n:=\mathbb{Z}[\sqrt{-n}]$. Therefore the question becomes: is $L_n$ abelian over $\mathbb{Q}$? Now $H_n:=Gal(L_n/K_n)$ is the ring class group of $\mathbb{Z}[\sqrt{-n}]$, hence abelian, and $Gal(L_n/\mathbb{Q})$ is a semi-direct extension of $\mathbb{Z}/2\mathbb{Z}$ by $H_n$, the action of the non-trivial element of $\mathbb{Z}/2\mathbb{Z}$ on $H_n$ being $x \mapsto x^{-1}$. Hence, if I am not mistaken (am I?), the question is equivalent to

For which $n$ is the ring class group $H_n$ killed by $2$?

Thanks for any clue or reference. I am especially interested in the case $n=32$.

-
Although you don't have Cox's book, you can request a copy of it by interlibrary loan. More precisely, your school is a member of the Boston Library Consortium and 10 other schools which belong to it hold a copy of that book. Checking online, the first school on the list which has it is Boston College and their catalog says the book is not currently checked out there. –  KConrad Oct 28 '11 at 3:52
The classical reference for primes of the form x^2 + 32y^2 is the article by Barrucand and Cohn with exactly this title. –  Franz Lemmermeyer Oct 28 '11 at 10:30
Thanks to all, and especially to Will. –  Joël Oct 28 '11 at 14:17

You want the idoneal numbers, http://oeis.org/A000926 and http://en.wikipedia.org/wiki/Idoneal_number

Depending what you mean by 32, the primes represented by $x^2 + 8 y^2$ are, in fact, given by congruences. However, half of those same primes are represented by $x^2 + 32 y^2,$ while the other half are represented by $4 x^2 + 4 x y + 9 y^2.$ The condition saying which are which is not simply congruences.

EDIT: it is possible 32 can be finished by biquadratic reciprocity, in which case it is in print somewhere. For instance, given a prime $p \equiv 1 \pmod 4,$ there is a representation $p = x^2 + 64 y^2$ in integers if and only if $2$ is a fourth power modulo $p.$ In comparison, we get $p = x^2 + 14 y^2$ for $p \neq 2,7$ if and only if $( -14 | p ) = 1$ and $(x^2 + 1)^2 \equiv 8 \pmod p$ has an integer solution (Cox page 115).

Either way, there is a monic irreducible polynomial $f_{32}(z)$ of degree 4 (as $h(-128) = 4$) such that, if an odd prime $p$ does not divide the discriminant of $f_{32}(z),$ then we can write $p = x^2 + 32 y^2$ if and only if $(-2 | p) = 1$ and $f_{32}(z) \equiv 0 \pmod p$ has an integer solution. This is Cox, page 180, Theorem 9.2.

EDIT TOOO: What you want is Lemma 3.10 on page 333 of LIU_WILLIAMS Tamkang Journal of Mathematics, Volume 25, Number 4, Winter 1994. I am going to need to check in various ways, but I already think that $p$ is represented by $x^2 + 32 y^2$ if and only if $p \equiv 1 \pmod 8$ and $(z^2 - 1)^2 + 1 \equiv 0 \pmod p$ has a solution with an integer $z.$ Checking... Yes, this is correct. Theorem 4.1 on the same page, Table right below it. There is a bit of work showing that one root and $p \equiv 1 \pmod 8$ actually shows four linear factors.

-
Depending on what you mean by 32. Nice phrase. –  Chandan Singh Dalawat Oct 28 '11 at 2:33
Thanks, Chandan. –  Will Jagy Oct 28 '11 at 3:13
Note that there are no solutions $z$ with $p \equiv 3 \pmod 4,$ and exactly two solutions (not four) with $p \equiv 5 \pmod 8,$ so the complete factorization $\pmod p$ is two linear terms times a quadratic. –  Will Jagy Oct 28 '11 at 4:36
IIRC the case $n=32$ is explicitly treated in Ireland-Rosen, as well as in Cox. But Joel -- you should buy Cox! It's a wonderful reference as well as being a great source for e.g. undergraduate and masters level projects, and very well-written. –  Kevin Buzzard Oct 28 '11 at 6:57

Even though some of the main ideas have been pointed out above, I will try to add (in all modesty) a complete answer.

The following outline comes from my master thesis and further develops some of the ideas in David Cox's book Primes of the form $x^2+ny^2$.

$\color{red}{\text{PART 1: Preliminary results on the genus field.}}$

Lemma: Given a number field $K$, there is a one-to-one correspondence between unramified Abelian extensions $M$ of $K$ and subgroups $H$ of the ideal class group $C(\mathcal{O}_K)$. Furthermore, if the extension $K \subset M$ corresponds to the subgroup $H \subset C(\mathcal{O}_K)$, then the Artin map induces an isomorphism $$C(\mathcal{O}_K)/H \xrightarrow{\sim} \mathrm{Gal}(M/K)$$

Proof. See Corollary 5.21 in Cox for the details.

Definition: The genus field $M$ is the unramified Abelian extension of $K$ corresponding to the subgroup $C(\mathcal{O}_K)^2 \subset C(\mathcal{O}_K)$.

Possibly there are other definitions for the genus field, but it can be shown that the above definition implies the following characterization:

Theorem: Let $K$ be an imaginary quadratic field of discriminant $d_K$. Let $\mu$ be the number of primes dividing $d_k$ and let $p_1, \ldots, p_r$ be the odd primes dividing $d_K$. (So that $\mu=r$ or $r+1$ according to whether $d_K \equiv 0 \textrm{ or } 1 \bmod{4}$). Set $p_i^*=(-1)^{(p_i-1)/2}p_i$. Then:

• The genus field of $K$ is the maximal unramified extension of $K$ which is an Abelian extension of $\mathbb{Q}$.
• The genus field $M$ of $K$ is $K(\sqrt{p_1^*}, \ldots, \sqrt{p_r^*})$ and $[M:\mathbb{Q}]=2^{\mu}$.

Proof. See Theorem 6.1 in Cox for the details.

$\color{red}{\text{PART 2: When is the Genus field equal to the HCF?}}$

Lemma 1: The Hilbert class field $L$ of $K=\mathbb{Q}(\sqrt{-n})$ is Abelian and Galois over $\mathbb{Q}$ (besides being Galois over $K$) if and only if the genus field equals the Hilbert class field

Proof. It can be shown that $[G,G]=C(\mathcal{O}_K)^2$ with $G=\mathrm{Gal}(L/\mathbb{Q})$ (see Theorem 6.1 in Cox). So if $\mathrm{Gal}(L/\mathbb{Q})$ is Abelian then $C(\mathcal{O}_K)^2=1$ and via Galois theory of unramified Abelian extensions this gives: $$C(\mathcal{O}_K)/1 \xrightarrow{\sim} \mathrm{Gal}(M/K)$$ But the left hand side corresponds to $\mathrm{Gal}(L/K)$ via Artin Reciprocity, so that $$[L:K]=|\mathrm{Gal}(L/K)| = |\mathrm{Gal}(M/K)|=[M:K]$$ Since we already know that $M \subset L$, we actually have $M = L$.

Before we continue, we recall the following result:

Lemma 2: Let $K$ be an imaginary quadratic field and let $L$ be Hilbert class field of $K$. Then $L$ is a Galois extension of $\mathbb{Q}$, and its Galois group can be written as a semidirect product $$\mathrm{Gal}(L/\mathbb{Q}) \cong \mathrm{Gal}(L/K) \rtimes (\mathbb{Z}/2\mathbb{Z})$$ where the nontrivial element of $\mathbb{Z}/2\mathbb{Z}$ acts on $\mathrm{Gal}(L/K)$ by sending $\sigma$ to its inverse element $\sigma^{-1}$.

Proof. See p122 in Cox for the details.

Lemma 3: Let $H$ and $K$ be two finite groups. Then $H\rtimes_\theta K$ is abelian if and only if $H$ and $K$ are abelian and $\theta$ is the trivial homomorphism.

Proof. Sufficiency is obvious. For necessity, if $\theta$ is nontrivial, then some $k\in K$ maps to some $\operatorname{id}\ne \theta_k\in \operatorname{Aut}(H)$, which means that $\theta_k(h)\ne h$ for some $h\in H$. Thus $hk=k\theta_k(h)\ne kh$, so we have two elements that do not commute.

Theorem 1: The Hilbert class field $L$ of $K=\mathbb{Q}(\sqrt{-n})$ is Abelian if and only if $CL(K) \cong (\mathbb{Z}/2\mathbb{Z})^r$ for some $r \geq 0$.

Proof. From the two previous lemmas it follows that $\mathrm{Gal}(L/\mathbb{Q})$ is abelian if $\mathrm{Gal}(L/K)$ is abelian, and $\sigma$ acts trivially. The last condition is only possible if for every element of $\sigma \in \mathrm{Gal}(L/K)$ we have $\sigma=\sigma^{-1}$. But this means that $\sigma^2=1$ for every $\sigma$, such that $\mathrm{Gal}(L/K)$ must be an elementary abelian $2$-group (i.e. of the form $\mathbb{Z}/2\mathbb{Z}^r$ for some $r \geq 0$). Under these assumption, the second requirement, that $\mathrm{Gal}(L/K)$ must be abelian, is automatically satisfied. Because of Artin reciprocity we now have that $$CL(K) \cong \mathrm{Gal}(L/K) \cong (\mathbb{Z}/2\mathbb{Z})^r$$ and we are done.

Definition: Let $K=\mathbb{Q}(\sqrt{-n})$ be an imaginary quadratic field. Then we call the positive integer $n$ a convenient number if the class group of $K$ is an abelian $2$-group, i.e. $CL(K)=(\mathbb{Z}/2\mathbb{Z})^r$ for some $r \geq 0$.

But which numbers $n$ are convenient numbers? Euler discovered that the following 65 idoneal numbers are convenient numbers.

Weinberger proved in 1973 that at most one other convenient number can exist, and that if the generalized Riemann hypothesis holds, then the list is complete.

Combining Lemma 1 and Theorem 1, we have:

Theorem 2: The genus field equals the Hilbert Class field of $K=\mathbb{Q}(\sqrt{-n})$ if and only if the class group of $K$ is an abelian $2$-group if and only if $n$ is one of Euler's 65 idoneal numbers or Weinberger's (conjectured, unique) 66th number.

$\color{red}{\text{PART 3: Primes of the form$x^2+ny^2$and congruence relations.}}$

Another curious fact of Euler's idoneal numbers is that they are very closely related to situations in which congruences can be used to express the necessary and sufficient conditions for a prime to be of the form $p=x^2+ny^2$. More specifically,

Theorem 3: Let $n$ be a convenient number. Then the necessary and sufficient conditions for a prime to be expressed as $p=x^2+ny^2$ can be stated by congruence relations.

Before we can prove this claim we need the following lemma

Lemma 4: Let $n$ be one of Euler's 65 convenient numbers such that the genus field of $K=\mathbb{Q}(\sqrt{-n})$ equals the Hilbert class field. Since the genus field is given by $$M=K(\sqrt{p_1^*}, \sqrt{p_2^*}, \ldots, \sqrt{p_n^*})$$ the HCF can be written as a composite of quadratic fields $$L=K_0 K_1 K_2 \cdots K_n$$ with $K_i=\mathbb{Q}(\sqrt{p_i^*}$) for $i \geq 1$, and $K_0=K$. Moreover, a prime $p$ splits completely in $L$ if and only if it splits completely in all of the $K_i$.

and the following major result

Theorem 4: A prime can be represented as $p=x^2+ny^2$ if and only if the prime $p$ splits completely in the HCF of $\mathbb{Q}(\sqrt{-n})$.

Proof. See Theorem 5.26 in Cox.

We can now start proving Theorem 3:

Proof. If $n$ is one of Euler's 65 convenient numbers, then Lemma 4 argues that the HCF can be written as the composite field of extensions $\mathbb{Q}(\sqrt{p_i^*})$ over $\mathbb{Q}$ and that a prime splits completely over the composite field if and only if it splits completely over all the fields $\mathbb{Q}(\sqrt{p_i^*})$. So, Theorem 4 can now be reread as follows: a prime can be expressed in the form $p=x^2+ny^2$ iff $p$ splits completely in the HCF iff $p$ splits completely over all the $K_i$. Using Dedekind's theorem on the splitting behavior in quadratic extensions, this just means that $\left(d_{K_i}/p\right)=1$ for all $i$. Each condition gives us a congruence relation. Taking the different congruences together, we can conclude that the necessary and sufficient conditions can be expressed by congruence relations.

Corollary: Let $n$ be a convenient number. Let $q_i$, for $i=1, \ldots, r$ be the odd divisors of $n$ and set $q^* = (-1)^{(q-1)/2}$. Then $$p=x^2+ny^2 \Leftrightarrow \left( \frac{-n}{p} \right) = 1 \textrm{ and } \left( \frac{q_1^*}{p} \right) = \left( \frac{q_2^*}{p} \right) = \cdots = \left( \frac{q_r^*}{p} \right) = 1$$

Example. The above theory gives us a very easy way to find congruence relations when $n$ is a convenient number: just take any number Euler's list and find the divisors, .e.g. \begin{eqnarray*} p=x^2+93y^2 &\Leftrightarrow& \left( \frac{-93}{p} \right) = \left( \frac{-3}{p} \right) = \left( \frac{-31}{p} \right) = 1 \\ &\Leftrightarrow& p \equiv 1, 25, 49, 97, 109, 121, 133, 157, \\ && \ \ \ \ \ \ \ 169, 193, 205, 253, 289, 349, 361 \mod{372} \end{eqnarray*}

-
Hi I stumbled across this old answer it is very interesting, can one get a copy(electronic) of your master's thesis ? –  Rene Schipperus Oct 1 '14 at 12:16