Fix $f(x)\in\mathbb Z[x]$ a polynomial. For a given prime $p,$ we say $p$ is a "prime divisor" of $f$ if and only if $p$ divides $f(k)$ for some $k\in\mathbb Z.$ It is known that nonconstant $f$ have infinitely many prime divisors, and one can even exhibit polynomials $f$ with fun properties; for example
$$p\;\;\text{divides}\;\;\Phi_n(nx)\implies p\equiv1\pmod n,$$
where $\Phi_n(x)\in\mathbb Z[x]$ is the $n$th cyclotomic polynomial. One can even show, using this, that every nonconstant polynomial $f$ have infinitely many $1\pmod n$ prime divisors. (See discussion after Theorem 3 here.) Explicitly, we can use Dedekind-Kummer to take all but finitely many of the primes which split completely in the closure of $\mathbb Q(\zeta_n)$ and $\mathbb Q(\alpha)$ where $\alpha\in\mathbb C$ is a root of $f.$
Showing the general case, however, looks harder. The question is as follows.
For nonconstant polynomials $f(x)\in\mathbb Z[x],$ are there infinitely many $k\pmod n$ prime divisors, for any $n,k\in\mathbb N$ with $\gcd(k,n)=1$?
In particular, I suspect that purely "algebraic" techniques (even allowing, say, Dedekind-Kummer) are insufficient here, but I have no strong reason to believe this.
Actually, the question is false for somewhat easy reasons, as was pointed out to me: the polynomial $\Phi_n(nx)$ itself fails to hit every single$\pmod n$ class except for $1\pmod n$ and so provides a counterexample. The revised question, then, is for a classification of which modular classes of primes are hit infinitely often.
For nonconstant polynomials $f(x)\in\mathbb Z[x],$ when are there infinitely many $k\pmod n$ prime divisors, for given $n,k\in\mathbb N$ with $\gcd(k,n)=1$?
Best Answer
We assume that $f$ is monic and with discriminant $\Delta$.
Let $1 \leq k \leq n$ with $n \geq 3$ be coprime integers. Let $K=\mathbb{Q}(\zeta_n)$ and $L$ be the splitting field of $f$ over $K$, $L_1$ be the splitting field of $f$ over $\mathbb{Q}$, and $L_2$ be the subfield of $L_1$ generated by any root of $f$.
Let $p$ a prime number congruent to $k$ mod $n$ and $\mathfrak{p}$ be any ideal of $K$ above $p$. If $p$ is a prime divisor of $f$ unramified in $K$ and not dividing $\Delta$ (hence unramified in $L$), then this means that $f$ has a simple root mod $p$.
So, what is the class of the Frobenius at $p$ in $G=Gal(L/\mathbb{Q})$? We have an injective homomorphism $i:G \rightarrow Gal(L_1/\mathbb{Q}) \times Gal(K/\mathbb{Q})$ that clearly maps a Frobenius to a pair of Frobenius – thus, if $p$ is a prime divisor of $f$ congruent to $k$ mod $n$, then the image $i(Frob_p^L)$ must be $(g,k\,\mathrm{mod}\, n)$, where $g$ is conjugate to an element of $Gal(L_1/L_2)$.
Conversely, if a prime $p$ unramified in $K$ and not dividing $\Delta$ is such that $i(Frob_p^L)$ is $(g,k\,\mathrm{mod}\, n)$, with $g$ conjugate to an element of $Gal(L_1/L_2)$, then $p$ is congruent to $k$ mod $n$, and $g$ fixes a root $\alpha'$ of $f$, so that $\alpha'-\alpha'^p$ is in some prime ideal of $\mathbb{Q}(\alpha')$ above $p$, and thus $f$ has a root mod $p$.
Using Cebotarev, it follows that if $f$ has a prime divisor $p$ not dividing the discriminant of $f$ and congruent to $k$ mod $n$, then $f$ has infinitely many such primes $p$ (and the density of such primes is positive and can probably be computed in special cases).
In general (ie without using the existence of one prime divisor), to use Cebotarev, we need to ascertain the existence of some conjugacy class in $G$ of elements that are identity on $L_2$ and with a fixed action on $K$.
The appropriate $k$ will thus be (because $K/\mathbb{Q}$ is abelian) those such that $k \,\mathrm{mod}\,n$ is in the image of the projection $Gal(L/L_2) \rightarrow Gal(K/\mathbb{Q})=(\mathbb{Z}/n\mathbb{Z})^{\times}$, which, by elementary Galois theory, is the image of the restriction $Gal(L_2(\zeta_n)/L_2) \rightarrow Gal(K/\mathbb{Q})$ and thus the subgroup $Gal(K/K \cap L_2)$.
Our second characterization (still using Cebotarev) is thus $f$ has infinitely many prime divisors congruent to $k$ mod $n$ iff the automorphism of $K$ defined by $e^{2i\pi/n} \longmapsto e^{2ik\pi/n}$ is the identity on $K \cap L_2$.