Given a quadratic polynomial $ax^2 + bx + c$, with $a$, $b$ and $c$ being integers, is there a characterization of all primes $p$ for which the equation
$$ax^2 + bx + c \equiv 0 \pmod p$$
has solutions?
I have seen it mentioned that it follows from quadratic reciprocity that the set is precisely the primes in some arithmetic progression, but the statement may require some tweaking. The set of primes modulo which $1 + \lambda = \lambda^2$ has solutions seems to be $$5, 11, 19, 29, 31, 41, 59, 61, 71, 79, 89, 101, 109, 131, 139, 149, 151, 179, 181, 191, 199, \dots$$ which are ($5$ and) the primes that are $1$ or $9$ modulo $10$.
(Can the question also be answered for equations of higher degree?)
Best Answer
All but finitely many of the primes can be characterized by quadratic reciprocity. First handle the primes $p$ dividing $a$ (there is a solution if and only if $c \equiv 0 \bmod p$ or $b \not \equiv 0 \bmod p$). Next handle $p = 2$ (using the fact that $x^2 \equiv x \bmod 2$, so there is a solution if and only if $c$ is even or $a + b$ is odd).
For all remaining primes, complete the square to obtain $$\left( 2ax + b \right)^2 = b^2 - 4ac.$$
It follows that a solution exists if and only if $\left( \frac{b^2 - 4ac}{p} \right) = 1$, and the conditions for this to occur are given by quadratic reciprocity. (You get a congruence condition, but you also need to take into account all the primes dividing $b^2 - 4ac$.)
The situation for polynomials of higher degree is considerably more complicated (and I'll warn you in advance that I'm far from an expert in these matters, so take everything I say with a grain of salt). First, reduce WLOG to the irreducible case. If the Galois group of the polynomial is abelian, then by Kronecker-Weber the polynomial splits over some cyclotomic extension, so the way the polynomial factors modulo a prime is determined (again up to finitely many exceptions) by congruence conditions; this is all a part of the edifice of class field theory. I have been told that Artin reciprocity provides the appropriate generalization of quadratic reciprocity here but I don't know the details.
If the Galois group of the polynomial is non-abelian then the primes are not determined by congruence conditions. One can say some things about their statistical distribution using Chebotarev's density theorem but to actually characterize them is the subject of ongoing research and a part of what the Langlands program is supposed to do. At this MO question an example is given relating a specific modular form to roots modulo primes of the polynomial $x^3 - x - 1$ (or maybe the minimal polynomial of a primitive element of its splitting field instead).