For small values of $n$ and $(a, n) = 1$ it is sometimes possible to give an elementary proof that there are infinitely many primes congruent to $a \bmod n$ along the lines of Euclid's classic proof of the infinitude of the primes.  The idea is to find a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $a \bmod n$ or $1 \bmod n$, and such that the first case occurs infinitely many times; then one proves, just as Euclid did, that the integer values of $p$ are divisible by infinitely many primes, and then one contrives to avoid the residue $1 \bmod n$ (if $a \neq 1$; if $a = 1$ then we take $p(t) = \Phi_n(t)$.)  Results of Schur and Murty (see <a href="http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/dirichleteuclid.pdf">this paper of Keith Conrad</a>) then imply that such a polynomial $p$ exists if and only if $a^2 \equiv 1 \bmod n$.  

Say that a subset $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ **has property E** if there exists a non-constant integer polynomial $p(t)$ such that the primes dividing an integer value of $p$ are, with finitely many exceptions, congruent to $s \bmod n$ or $1 \bmod n$ for some $s \in S$, and such that the first case occurs infinitely many times.  Then we know that any $S$ containing an element squaring to $1$ has property E.

However, there exist subsets $S \subset (\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing such an element with property E.  For example, let $G$ be a proper subgroup of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$, let $a \not \in G$, and consider

$$p(t) = nt + a.$$

Any prime divisor of $n + a$ is relatively prime to $a$, and at least one of these prime divisors must have residue $\bmod n$ not in $G$.  If $p_1, ... p_k$ are finitely many such primes, then $p(p_1 ... p_k) \equiv a \bmod n$ and hence must have a prime factor with the same property which moreover is relatively prime to each $p_i$.  It follows that $S = (\mathbb{Z}/n\mathbb{Z})^{\ast} - G$ has property E, and if $\phi(n)$ is not a power of $2$, then taking $G$ to be the subgroup generated by the square roots of $1$ gives the desired example.

**Question:**  What subsets $S$ of $(\mathbb{Z}/n\mathbb{Z})^{\ast}$ not containing square roots of $1$ have property E?

(If this question is somehow answered in Conrad's paper, my apologies; the material is somewhat beyond me.)