Families of Polynomials Irreducible in $\mathbb{Z}$ but reducible in $\mathbb{Z}/p\mathbb{Z}$ for all primes $p$.

I am wondering if there exist classification of polynomials that are irreducible in $ \mathbb{Z}$ but reducible $\pmod p$ for all primes $p$.

I am aware that $\Phi_n$ has this property if $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is not cyclic. Are there any other nice families?

In fact, even after researching a bit, I have not been able to find any other polynomials that don't fall into the family listed above. Any single example that is not of the above form is also welcomed.

Actually, I have found this paper which might be of interest: http://www.m-hikari.com/imf-password2008/33-36-2008/pearsonIMF33-36-2008.pdf


As explained in this math.SE answer and stated in the comments by mercio, for an irreducible polynomial of degree $n$ this condition is equivalent to the Galois group failing to contain an $n$-cycle. There are many transitive subgroups of $S_n$ failing to contain an $n$-cycle and hence (up to solving the inverse Galois problem, also as stated in the comments by mercio) many such polynomials, although no such subgroups exist when $n$ is prime (exercise) and "most" polynomials, as it turns out, have Galois group $S_n$.

In particular, in the linked math.SE answer I give a family of irreducible polynomials of degree $4$ with Galois group $V_4$, namely the polynomials

$$f_a(x) = x^2 - 2ax + 1$$

where $a$ is an integer not equal to $1$ or $\frac{b^2 \pm 2}{2}$ for any integer $b$. I think examples of this form were originally written down by Hilbert. The other four possible Galois groups, namely $S_4, A_4, D_4, C_4$, all contain a $4$-cycle, so $V_4$ is the only acceptable Galois group for a quartic.

A method for generating lots of examples, although it takes a bit of work to make it fully explicit, is the following. Let $G$ be non-cyclic. Construct a Galois extension $K/\mathbb{Q}$ with Galois group $G$, and then let $f$ be the minimal polynomial of a primitive element of $K$. The cyclotomic polynomials occur this way when $G = \mathbb{Z}_n^{\times}$ is not cyclic, but $G$ can be, say, any nonabelian group. This construction in particular shows that examples exist with arbitrarily large degrees other than the cyclotomic polynomials (up to solving the inverse Galois problem, any degree $n$ such that there exists a non-cyclic group of order $n$; it is known that these are precisely the numbers $n$ such that $\gcd(n, \varphi(n)) \neq 1$).

It shouldn't be hard to be explicit about this for for $G = S_3$ (as a transitive subgroup of $S_6$); you can take $K$ to be the splitting field of any monic irreducible cubic polynomial whose discriminant is not a square.

For the sake of having an explicit sequence of examples of arbitrarily large degrees other than the cyclotomic polynomials, take the minimal polynomials of the algebraic integers

$$\sqrt{2} + \sqrt{3} + \sqrt{5} + \dots + \sqrt{p_k}$$ where $p_k$ is the $k^{th}$ prime. These are primitive elements of $\mathbb{Q}(\sqrt{2}, \sqrt{3}, \dots \sqrt{p_k})$, which has Galois group $C_2^k$, which is non-cyclic as soon as $k \ge 2$.