Let $D$ be a square free integer. I am looking at primes representable as $x^2+Dy^2$, where $x,y\in\mathbb Z$. I wonder whether it is always true that this set of primes is the union of finitely many arithmetic progressions intersected with the set of all primes?


This looks like a classical questions but I could never find an answer. It is certainly true if $\mathbb Z[\sqrt D]$ is a principal ideal domain. I think I had a proof in the case of class number two but I cannot remember it. It is of course true if one looks at norms of ideals rather than norms of elements but this is not what I want. 



primes represented by a binary form
EDIT: evidently the Cox book is now print-on-demand, at [WILEY](http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471190799.html) 


There are two situations where a positive integral form represents all the primes (at least those that do not divide the discriminant) given by arithmetic progressions. On situation, appropriate for your $x^2 + n y^2,$ is when $n$ is an idoneal number, which is when there is only one class per genus. This includes the case of only one genus, but also such thngs as $x^2 + 5 y^2,$ where the other class of that discriminant is in a different genus, $2 x^2 + 2 x y + 3 y^2.$ Note that we also know exactly what primes are represented by the second form. 


It is also good enough when a genus of two classes is simply one class and its opposite, as in $3 x^2 \pm 2 x y + 5 y^2.$ Either form represents all primes with certain values modulo 56. Note that this cannot happen with the principal genus. 


In general, there are elaborate conditions on what primes are represented by the principal form. Typical for class number 3: (Gauss) a prime $p \equiv 1 \pmod 3$ is represented by $x^2 + 27 y^2 $ if and only if 2 is a cubic residue $\pmod p,$ which is to say that $z^3 -2$ factors into three distinct linear factors $\pmod p.$ A prime $p > 3$ with $(-44 | p) =1$ is represented by $x^2 + 11 y^2$ if and only if $z^3 + z^2 -z+1 $ factors into three distinct linear factors $\pmod p.$ For all the class number three discriminants, see K. S. Williams and R. H. Hudson, Acta Arithmetica, vol. **57** (1991) pages 131-153, *Representation of primes by the principal form of the discriminant $-D$ when the classnumber $h(-D)$ is 3* 


For classnumber 4: (Gauss) a prime is represented by $x^2 + 64 y^2$ if and only if 2 has four distinct fourth roots $\pmod p,$ which is to say that $z^4 -2$ factors into four distinct linear factors $\pmod p.$ Note that $p \equiv 1 \pmod 8$ anyway. A prime $p > 3$ with $(-56 | p) =1$ is represented by $x^2 + 14 y^2$ if and only if $z^4 + 2z^2 -7 $ factors into four distinct linear factors $\pmod p.$ For all the class number four discriminants,see K. S. Williams and D.Liu, Tamkang Journal of Mathematics, vol. **25** (1994) pages 321-334, *Representation of primes by the principal form of negative discriminant $\Delta$ when $h(\Delta)$ is 4* 


For a table with all discriminants from $-3$ to $-451,$ all class numbers mixed together, see pages 539-542 in *Advanced Topics in Computational Number Theory* by Henri Cohen, 1999. The table is called "Discriminants and Hilbert class fields of imaginary quadratic fields." The polynomial given tells you, once a prime is represented by the principal genus of a discriminant, what polynomial must factor completely for the prime to be represented by the principal form itself. This table gives the polynomials $f\_n(x)$ promised in Theorem 9.2 on page 180 of *Primes of the form $x^2 + n y^2$* by David A. Cox, [AMAZON](http://rads.stackoverflow.com/amzn/click/0471190799) 


If you cannot find the two articles or the wonderful Cohen table, email me. My websites are currently down, some of it is usually posted there. The thing about Cohen's table is that it is difficult to find a polynomial that works, it is incredibly difficult to find one with small coefficients, compare some articles by Kaltofen and Yui.


