Primes of the form $x^2 + ny^2$: necessary and sufficient condition not in terms of a "modulo equation"? For particular cases ($n=1,2,3$) we can find an "elementary" necessary and sufficient condition, i.e.
$$p = x^2 + y^2 \Leftrightarrow p \equiv 1 \mod 4$$
$$p = x^2 + 2y^2 \Leftrightarrow p \equiv 1,3 \mod 8$$
$$p = x^2 + 3y^2 \Leftrightarrow p =3 \textrm{ or  } p \equiv 1 \mod 3$$
However, the general case, as proven in David Cox's book, gives a polynomial expression:

How can I argue that it is impossible to find a more "elementary" modulo expression? 
 A: This is not easy to prove; it relies on class field theory.
This MO question and its answers give an explanation.  The point is that (for all but finitely many $p$), we can write $p = x^2 + n y^2$ iff $p$ splits in the Hilbert Class Field of $\mathbb Q(\sqrt{-n})$,
and so we get a congruence condition iff the HCF is abelian over $\mathbb Q$.
This fails e.g. for $n = 23$.  (In this case the polynomials $f_{23}(x)$ can be taken to be $x^3 - x - 1$, and the HCF of $\mathbb Q(\sqrt{-23})$ is the $S_3$ extension of $\mathbb Q$ obtained as the splitting field of this polynomial.) 
In this case, one has the following statement: we can write an odd prime $p$,
different from $23$, in the form $x^2 + 23 y^2$ iff the coefficient of 
$q^p$ in $q \prod_{n=1}^{\infty}(1-q^n)(q-q^{23 n})$ equals $2$. (It is always either $-1,0,$ or $2$.)
A: Got me. I think you can prove impossibility by clever use of Chebotarev density, especially Theorem 9.12 on page 188. The density of primes represented by a (positive) form is some $1/k.$ If these were collected in an arithmetic progression, except for a few that divide the discriminant, the progression would need to be $k n + b.$ And I think you can rule that out, at least by experimenting with any specific example; i encourage you to experiment with this, in the examples below.    
Let me give you some examples to chew on.
For odd primes $p \equiv 1 \pmod 3,$ there is an expression in integers $p = u^2 + 27 v^2 $ if and only if $2$ is a cube $\pmod p.$ The others are represented by $4 u^2 \pm 2 u v + 7 v^2.$
For odd primes other than $3$ itself with $p \equiv 1 \pmod 3,$ there is an expression in integers $p = u^2 + u v + 61 v^2 $ if and only if $3$ is a cube $\pmod p.$ The others are represented by $7 u^2 \pm  3 u v + 9 v^2.$
For odd primes other than $23$ with $(p | 23) = 1$ there is an expression in integers $p = u^2 + 23 v^2 $ if and only there are three distinct roots to $ x^3 - x + 1 \equiv 0 \pmod p.$  The others are represented by $3 u^2 \pm  2 u v + 8 v^2.$
For odd primes other than $31$ with $(p | 31) = 1$ there is an expression in integers $p = u^2 + 31 v^2 $ if and only there are three distinct roots to $ x^3 + x + 1 \equiv 0 \pmod p.$  The others are represented by $5 u^2 \pm  4 u v + 7 v^2.$
