Polynomials irreducible over $\mathbb{Q}$ but reducible over $\mathbb{F}_p$ for every prime $p$ Let $f(x) \in \mathbb{Z}[x]$. If we reduce the coefficents of $f(x)$ modulo $p$, where $p$ is prime, we get a polynomial $f^*(x) \in \mathbb{F}_p[x]$. Then if $f^*(x)$ is irreducible and has the same degree as $f(x)$, the polynomial $f(x)$ is irreducible. 
This is one way to show that a polynomial in $\mathbb{Z}[x]$ is irreducible, but it does not always work. There are polynomials which are irreducible in $\mathbb{Z}[x]$ yet factor in $\mathbb{F}_p[x]$ for every prime $p$. The only examples I know are $x^4 + 1$ and $x^4 - 10x^2 + 1$.
I'd like to see more examples, in particular an infinite family of polynomials like this would be interesting. How does one go about finding them? Has anyone ever attempted classifying all polynomials in $\mathbb{Z}[x]$ with this property?
 A: 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.) 
A: 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}$.
A: For any distinct primes $p_1,p_2$ the polynomial
$$x^4-2(p_1+p_2)x^2+(p_1-p_2)^2,(1)$$
is irreducible in $\Bbb Q$, but this polynomial is reducible modulo $p$ for any prime $p$. Let us see why:
It is a well-known fact that $[\Bbb Q(\sqrt{p_1},\sqrt{p_2}):\Bbb Q]=4$ and $\Bbb Q(\sqrt{p_1}+\sqrt{p_2})=\Bbb Q(\sqrt{p_1},\sqrt{p_2})$; see this, thus as $\sqrt{p_1}+\sqrt{p_2}$ is a root of $(1)$, this polynomial is irreducible over $\Bbb Q$.
As the Legendre symbol is multiplicative we get that $p_1$ or $p_2$ have a square root modulo $p$ or $p_1p_2$ does; notice this happens trivially if $p=p_1$ or $p=p_2$, hence as $\Bbb F_p(\sqrt{p_1},\sqrt{p_2})=\Bbb F_p(\sqrt{p_1},\sqrt{p_1p_2})=\Bbb F_p(\sqrt{p_2},\sqrt{p_1p_2})$, we obtain
$$[\Bbb F_p(\sqrt{p_1},\sqrt{p_2}):\Bbb F_p]\leq 2,$$
and this implies $(1)$ is not irreducible as $\sqrt{p_1}+\sqrt{p_2}$ is a root.
The polynomial $x^4-10x^2+1$ is a particular case with $p_1=2$ and $p_2=3$.
