An irreducible $f\in \mathbb{Z}[x]$, whose image in every $(\mathbb{Z}/p\mathbb{Z})[x]$ has a root?

Problem: Is there an irreducible $f\in \mathbb{Z}[x]$, whose image in every $(\mathbb{Z}/p\mathbb{Z})[x]$ has a root for $p$ prime? If there is, what is the minimal degree possible?

I can only prove that $x^2-c$ is impossible, by quadratic reciprocity and Chinese remainder theorem. Even the case of $a x^2 - c$ is unknown to me.

Meanwhile, if $f$ is not required to be irreducible, but only have no root in $\mathbb{Z}$, then $(x^2-a)(x^2-b)(x^2-ab)$ is a solution for non-sqaure $a,b,ab$, since if both $a,b$ are not squares in $\mathbb{Z}/p\mathbb{Z}$, then $ab$ is a square. Yet I still don't know if this is of minimal degree.

Also, it is natural to pose generalizations

1. When $p$ is not necessarily prime (equivalently for all prime powers).
2. When $p$ is odd prime.
3. When $p$ represents sufficiently large primes (equivalently all but a finite number left).

Solution 1:

No. In fact, if $f$ is an irreducible polynomial of degree at least $2$ then there are infinitely many primes $p$ such that $f$ does not have a root $\bmod p$.

The argument is standard and goes as follows. A theorem of Dedekind asserts that if $f$ factors as a product $\prod f_i(x) \bmod p$ of irreducible polynomials, and if $p$ does not divide the discriminant of $f$, then some element of the Galois group of $f$ has cycle type $(\deg f_1, \deg f_2, ...)$. The Frobenius density theorem (a weaker version of the Chebotarev density theorem) asserts that the converse holds in the following sense: if some element of the Galois group of $f$ has a given cycle type, then a positive proportion of primes has the property that the factorization of $f \bmod p$ has the same cycle type. In particular, if some element of the Galois group of $f$ has no fixed points, then a positive proportion of primes has the property that $f$ has no roots $\bmod p$.

But the Galois group of $f$ acts transitively on its roots, and we have the following general result.

Lemma: Let $G$ be a finite group acting transitively on a set $S$ of size greater than $1$. Then some $g \in G$ does not have a fixed point.

Proof. By Burnside's lemma,

$$1 = \frac{1}{|G|} \sum_{g \in G} |\text{Fix}(g)|$$

so the average number of fixed points of a random element of $G$ is $1$. On the other hand, $\text{id} \in G$ has $|S| > 1$ fixed points. Hence some element must have less than $1$ fixed point, which can only mean that it has no fixed points. $\Box$

The conclusion follows.

Solution 2:

Looking at the Galois group of the polynomial as a subgroup $G$ of $S_n$, we can translate your requirements as conditions on $G$ :

(i) $f$ has a root mod $p$ for every prime $p$ iff every element of $G$ has a fixpoint (by Cebotarev's theorem)
(ii) $f$ is irreducible in $\Bbb Q[x]$ iff $G$ is transitive.
(iii) $f$ has a rational root iff every element of $G$ has a common fixpoint.

I don't think satisfying (i) and (ii) is possible.

$(x^2-a)(x^2-b)(x^2-ab)$ gives the subgroup of $S_6$ generated by $(12)(34)$ and $(12)(56)$. It satisfies (i) and not (iii).

We can also achieve (i) and not (iii) with $n=5$ by using $G$ generated by $(123)$ and $(12)(45)$. For example, with something like $f(x) = (x^3-x+1)(x^2+23)$

Finally, we can enumerate the possible subgroups of $S_2,S_3,S_4$ to check that none of them satisfy (i) and not (iii), so $n=5$ is the minimal degree possible.