Is it true that if $f(x)$ has a linear factor over $\mathbb{F}_p$ for every prime $p$, then $f(x)$ is reducible over $\mathbb{Q}$?

We know that $f(x)=x^4+1$ is a polynomial irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$.

My question is:

Is it true that if $f(x)$ has a linear factor over $\mathbb{F}_p$ for every prime $p$, then $f(x)$ has a linear factor over $\mathbb{Q}$?

Edit: Thanks for @Jyrki Lahtonen's answer, I want to do some modifications:

Is it true that if $f(x)$ has a linear factor over $\mathbb{F}_p$ for every prime $p$, then $f(x)$ is reducible over $\mathbb{Q}$?

Thanks in advance!

Solution 1:

For your follow-up question, only linear polynomials don't work :

Suppose $G$ is a subgroup of $S_n$ such that $G$ acts transitively on $\{1,\ldots, n\}$, and let $H_i^j = \{\sigma \in G \mid \sigma(i)=j \}$.

If $\tau(i)=j$ then $H_i^k = H_j^k \tau$, and $H_k^j = \tau H_k^i$. Since $G$ is transitive, every $H_i^j$ has the same cardinal. Since every element of $G$ is in $n$ such $H_i^j$, we have $|H_i^j| = |G|/n$, and in particular, elements in $G$ have on average $\sum |H_i^i|/|G| = 1$ fixed point. Since the identity element has $n$ fixed points, if $n>1$ there must be some elements in $G$ without fixed points.

So if you have an irreducible polynomial of degree $n$ over $\Bbb Q$ its Galois group is transitive on its $n$ roots, so if $n>1$, it has some elements without fixed points. Then Cebotarev's theorem says that there are infinitely many primes $p$ for which the polynomial doesn't have a linear factor over $\Bbb F_p$.

So if $P$ has linear factors for all primes, then it is reducible or of degree $1$.

Solution 2:

No. Consider $$ f(x)=(x^2+1)(x^2+2)(x^2-2). $$ Modulo any prime at least one of the numbers $-1$, $-2$, $2$ is a quadratic residue. Therefore $f(x)$ has a linear factor modulo $p$ for all primes $p$.

Solution 3:

A degree $5$ counterexample is cited in this question: $(x^2 + 31)(x^3 + x + 1)$.

The reason can be understood by studying the cubic. The splitting field of a cubic always contains $\sqrt{\Delta}$, where $\Delta$ is the discriminant of the polynomial. Consequently, there are three ways a cubic can split in a finite field:

• It has three roots
• It is irreducible (and $\Delta$ must be square, because the splitting field is the cubic extension)
• It has one root (and $\Delta$ is nonsquare)

For the given cubic, $\Delta = -31$; consequently if the cubic factor has no roots in the finite field, then the quadratic factor does.

Solution 4:

The idea used by user14972 in their answer can be used to find other examples:

$f(x)=(x^2+3)(x^3+2)$. How many zeroes the cubic factor has in $\Bbb F_p$ depends on which quadratic form of discriminant $D=-108=-3\cdot6^2$, if any, represents $p$; if 3 zeroes, $a^2+27b^2$; if no zeroes, $4a^2+2ab+7b^2$; if one zero, neither quadratic form. If that cubic factor has no zeroes, then $-108$ is a square $c^2$; $p>3$ so 6 has an inverse, and $(6^{-1}c)^2+3=0$.

Similarly, $f(x)=(x^2+3)(x^3+3)$, $D=-243=-3\cdot9^2$.

user14972's example, and the two above, use the characteristic cubic of quadratic forms whose discriminants have some value $D$ where $h(D)=3$, i.e. where quadratic forms of discriminant $D$ are in three classes. But it is not necessary to use such concepts of quadratic form theory.

If $p=3$ or $p=1\mod 6$, then $p$ has the form $a^2+3b^2$, so $0=(a^2+3b^2)b^{-2}=(ab^{-1})^2+3$. So, if $x^2+3$ has no zeroes in $\Bbb F_p$, then $p=2$ or $p=5\mod6$, so everything is a cube.[1] So we may take $f(x)=(x^2+3)(x^3+a)$ where $a$ is any integer except a cube (so that $f$ has no linear factor in $\Bbb Q$).

[Brandl][2] gives the example $f(x)=(x^2+x+1)(x^3-2)$. The following proof that $f$ has a zero in each $\Bbb F_p$ is adapted from [Brandl]. If $p\ne 1\mod 3$, then the order of the multiplicative group of $\Bbb F_p$ is not divisible by 3. Hence 2 is a cube modulo $p$.[1] If $p=1\mod 3$, then there exists a primitive cube root of unity $x$ modulo $p$. [This follows from Sylow's first theorem.] This is obviously a root of the polynomial $x^2+x+1$. [This is because $0=x^3-1=(x-1)(x^2+x+1)$ but $x\ne 1$.]

[1] Proof. If $p=2$ or 3, $a^3=a$. If $p=6k+5$, then, by Fermat's little theorem, $a=a^p=a^{6k+5}$, so $a=r^3$ where $r=a^{4k+3}$. Alternatively, if any element of $\Bbb F_p$ were not a cube, then, by the pigeonhole principle, at least two unequal elements $a, b$ must have equal cubes. Then $0=a^3-b^3=(a-b)(a^2+ab+b^2)$; $a-b\ne 0$ so $a^2+ab+b^2=0$. The only element whose cube is 0 is 0, so $b\ne 0$, so $b$ has an inverse. So $(a^2+ab+b^2)b^{-2}=0$ so $c^2+c+1=0$ where $c=ab^{-1}$. So $0=(c^2+c+1)(c-1)=c^3-1$ so $c^3=1$. $a\ne b$ so $c\ne 1$, so $c$'s order is 3, so $3\mid p-1$, contradiction.

[2] Rolf Brandl, Daniela Bubboloni and Ingrid Hupp. Polynomials with roots mod $p$ for all primes $p$. J. Group Theory 4 (2001), p.233--239.