Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$

Solution 1:

There are two crucial results here.

Dedekind's theorem: Let $f$ be a monic irreducible polynomial over $\mathbb{Z}$ of degree $n$ and let $p$ be a prime such that $f$ has distinct roots $\bmod p$ (this is true for precisely the primes not dividing the discriminant). Suppose that the prime factorization of $f \bmod p$ is $$f \equiv \prod_{i=1}^k f_i \bmod p.$$

Then the Galois group $G$ of $f$ contains an element of cycle type $(\deg f_1, \deg f_2, ...)$. In particular, if $f$ is irreducible $\bmod p$, then $G$ contains an $n$-cycle.

Frobenius density theorem: The density of the primes with respect to which the factorization of $f \bmod p$ has the above form is equal to the density of elements of $G$ with the corresponding cycle type. In particular, for every cycle type there is at least one such prime $p$.

It follows that

$f$ is reducible $\bmod p$ for all $p$ if and only if $G$ does not contain an $n$-cycle.

The smallest value of $n$ for which this is possible is $n = 4$, where the Galois group $V_4 \cong C_2 \times C_2$ has no $4$-cycle. Thus to write down a family of examples it suffices to write down a family of irreducible quartics with Galois group $V_4$. As discussed for example in this math.SE question, if $$f(x) = (x^2 - a)^2 - b$$

is irreducible and $a^2 - b$ is a square, then $f$ has Galois group $V_4$. In particular, taking $b = a^2 - 1$ the problem reduces to finding infinitely many $a$ such that $$f(x) = x^4 - 2ax^2 + 1$$

is irreducible. We get your examples by setting $a = 0, 5$.

By the rational root theorem, the only possible rational roots of $f$ are $\pm 1$, so by taking $a \neq 1$ we already guarantee that $f$ has no rational roots. If $f$ splits into two quadratic factors, then they both have constant term $\pm 1$, so we can write $$x^4 - 2ax + 1 = (x^2 - bx \pm 1)(x^2 + bx \pm 1)$$

for some $b$. This gives $$2a = b^2 \mp 2.$$

Thus $f$ is irreducible if and only if $2a$ cannot be written in the above form (and also $a \neq 1$).

Classifying polynomials $f$ with this property seems quite difficult in general. When $n = 4$, it turns out that $V_4$ is in fact the only transitive subgroup of $S_4$ not containing a $4$-cycle, but for higher values of $n$ there should be lots more, and then one has to tell whether a polynomial has one of these as a Galois group...

(Except if $n = q$ is prime; in this case $q | |G|$ so it must have a $q$-cycle.)

Solution 2:

The polynomials $p_n(x)=x^{2^n}+1$ form an infinite family of examples of such polynomials. They are irreducible over the rationals, because $p_n(x)$ is also the cyclotomic polynomial of order $2^{n+1}$.

But the polynomial $p_n(x)$ factors in $\mathbb{F}_p[x]$ for any prime $p$. If $p=2$, this is obvious because $$ p_n(x)\equiv (x+1)^{2^n}\pmod2. $$ If $p$ is an odd prime, then the reasoning is a little bit more subtle. It follows from the fact that the order $d$ of $p$ in the group $G=\mathbb{Z}/2^{n+1}\mathbb{Z}^*$ is less than $2^n$ (by virtue of non-cyclicity of $G$), and the fact that the field $\mathbb{F}_{p^d}$ then contains a primitive root of unity of order $2^{n+1}$ as $2^{n+1}\mid (p^d-1)$. This implies that the primitive roots of unity of order $2^{n+1}$ have minimal polynomials of degree $d$, and these must be factors of $p_n(x)$ in $\Bbb{Z}_p[x]$.

It is worth observing that for the same reason ($G$ not cyclic) the polynomials $p_n(x)$ pass the test described in Qiaochu's answer. The elements of the Galois group all have orders that are powers of two $<2^n$, so the maximum length of a cycle is $2^{n-1}$.