Congruences among primes modulo which a given polynomial has roots Suppose $f(x)\in\mathbf Z[x]$ is nonconstant. I would like to know if either of the following statements is true.


*

*If $a$ and $b$ are coprime integers (probably with some additional restriction), then there exist infinitely many primes $p$ such that $p\equiv a\bmod b$ and $f(x)$ has a root modulo $p$.

*It is possible choose $a$ and $b$ so that, for every prime $p\equiv a\bmod b$,  $f(x)$ has a root modulo $p$. 
 A: Here's a survey of the possible things that can happen. In regards to your first question, given any polynomial $f(x)$, there is a positive integer $M$ so that if $\gcd(b,M) = 1$, then there are infinitely many primes $p \equiv a \pmod{b}$ for which $f(x)$ has a root modulo $p$. (One can take for $M$ the modulus of the maximal abelian subextension $K/\mathbb{Q}$ of the splitting field of $f(x)$.) It is possible for $M$ to be $1$, in which case statement $1$ is true. On the other hand, there examples that show that some restraint on $b$ is necessary. The example Gerry gave is one. Another is $f(x) = x^{4} - 4x^{2} + 2$, which has a root modulo an odd prime $p$ if and only if $p \equiv 1 \pmod{8}$.
The answer to question 2 is no in general. Let $f(x) = x^5 + 20x + 16$. The splitting field of $f(x)$ over $\mathbb{Q}$ is a Galois extension $K$ with Galois group $A_{5}$. The Chebotarev density theorem applied to the compositum of $K$ with $\mathbb{Q}(e^{2 \pi i / b})$ implies that for any $a$ and $b$ with $\gcd(a,b) = 1$, it is possible to find a prime $p_{1} \equiv a \pmod{b}$ so that $f(x)$ has a root modulo $p_{1}$, and another prime $p_{2} \equiv a \pmod{b}$ so that $f(x)$ does not have a root modulo $p_{2}$. 
On the other hand $f(x) = x^{3} - 2$ has a root modulo every prime $p \equiv 2 \pmod{3}$,
and the polynomial $f(x) = (x^{2} - 2)(x^{2} - 3)(x^{2} - 6)$ has a root modulo every single prime number.
