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}$?

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$.

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$.

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.