# always irreducible polynomial?

There exists irreducible polynomials in $\mathbb{Z}[x]$ (e.g. $x^4-10x^2+1$) which is reducible modulo every prime $p$.(A proof can be found in J.S. Milne's "Fields and Galois Theory", page13. Here is a quick link Notes of J.S. Milne ) This kind polynomial is so "bad". I want to know if there exists some non-trivial "good" polynomials.

State precisely:

Does there exist a polynomial $f(x)\in \mathbb{Z}[x]$ with degree>1 such that $f(x)$ is irreducible in $\mathbb{F}_p[x]$ for any prime number $p$?

-
@Chandru What about $p=2$? – Alex B. Jun 8 '11 at 7:50
@Chandru: In $\mathbb{F}_2[x]$, $x^2 + 1 = (x-1)(x+1)$. In $\mathbb{F}_5[x]$, $x^2 + 1 = (x-2)(x-3)$. Etc. In fact $x^2 + 1$ is reducible mod every $p$ that is $1 \mod 4$, by Fermat's sum of squares theorem (for instance). – ShreevatsaR Jun 8 '11 at 7:52
@shreevatsaR: Correct, now understood. I couldn't realize $-1$ and $1$ were same in $\mathbb{Z}_{2}$. – user9413 Jun 8 '11 at 7:53
@Chandru: this is not the first time I have needed to tell you this: stop posting unhelpful comments. If you think you have an answer, have the courage to post it as an answer, where it can be properly downvoted if it's wrong. – Qiaochu Yuan Jun 8 '11 at 11:50
@Qiaochu: Hi, I can't argue with you now. – user9413 Jun 8 '11 at 16:01

No, there is no such polynomial. Any polynomial $f(x) \in \mathbb{Z}[x]$ with degree greater than $1$ is reducible modulo every prime factor of every value it takes.

For, take any value of $n$ for which $f(n) \neq \pm 1$. (There must exist such $n$ because $f$ can take the values $1$ and $-1$ only finitely many times.) Consider any prime factor $p$ of $f(n)$. Then $f(n) \equiv 0 \mod p$, which means that $f$ is reducible in $\mathbb{F}_p[x]$: it is divisible by the polynomial $x-n$.

-
I think you should interpret why you are done? I mean why there exists such prime $p$ greater than the leading coefficient or ...., note that $f$ need not be monic ? – wxu Jun 8 '11 at 14:57
OK. It is easy to it cannot always happen that $f=x-n$ mod $p$ for every $p$ our choosed. – wxu Jun 8 '11 at 16:40
It can be showed that for every non-constant polynomial $f\in \mathbb{Z}[x]$ , the set consists of prime number $p$ for which $p$ is divisible by $f(n)$ for some $n$, is infinite. Maybe this fact $\cup_{i\in I}(a_i+(p_i))\neq\mathbb{Z}$, here $I$ is a finite set, will be helpful. – wxu Jun 13 '11 at 15:24
@wxu: To answer your first comment: if $p$ is less than the leading coefficient, that is also fine. And if it is exactly equal to the first coefficient so that the degree reduces, I would say that the polynomial has actually reduced. :-) – ShreevatsaR Jun 19 '11 at 21:28

The answer is 'no', except for linear polynomials. Indeed, if $f(x)\in\mathbb{Z}[x]$ is irreducible and of degree greater than 1, then its splitting field is a non-trivial extension of $\mathbb{Q}$, and in such an extension, infinitely many primes split, which means that $f$ splits modulo infinitely many primes. An even stronger statement is true: if $G$ is the Galois group of $f$, then the set of primes that split completely, i.e. primes (up to finitely many exceptions) modulo which $f$ splits into linear factors, has density $1/|G|$ by the Chebotarev density theorem.

-
This more than answers the question, but at the cost of introducing algebraic number theory and Galois theory where Shreevatsa's answer shows that more modest tools will do. It gives OP something to think about. – Gerry Myerson Jun 8 '11 at 13:22
Must $f$ be monic? – wxu Jun 8 '11 at 15:01