Many a times, to prove that a polynomial in one indeterminate with integer coefficients is irreducible, we prove that it is irreducible modulo some prime, $p$; i.e. irreducible in the ring $\mathbb{Z}_p[x]$. Unfortunately, the converse is not true, and this can be seen by a simple counterexample:
Claim: $f(x)=x^4+1$ is irreducible over $\mathbb Z[x]$ but has factors modulo every prime $p$.
Proof:
The symmetry in the coefficients of the polynomial suggests that whenever $r$ in $\mathbb Z$ is a root, then so is $s$ in $\mathbb Z$ where $rs \equiv 1(\mod p)$. (This small result is also interesting in its own right! ).
So it is enough to consider the factorization of $x^4+1$ into two quadratics.
Case i: $p\equiv 1(\mod 4)$
Here, there exists a solution, say a for the congruence $x^2 \equiv -1 (\mod p)$. (This is a standard result in number theory, first proved by Fermat.) Now, $(x^2+a)(x^2-a)=(x^4-a^2)(\mod p) \equiv (x^4+1)(\mod p)$ and so there are factors of $x^4+1 in \mathbb{Z}[x]$.
Case ii: $p\equiv 3(\mod 4)$
Then, the factorization is possible provided there exist integers $a, b, c, d$ satisfying $x^4 + 1 =( x^2 +a x+b)(x^2+c x +d)$ . This reduces to the four congruences-
(1) $a+c \equiv 0(\mod p)$
(2) $a c +b+d\equiv 0(\mod p)$
(3) $a d+b c\equiv 0(\mod p)$
(4) $b d\equiv 1(\mod p)$
(1) and (3) imply that $b\equiv d(\mod p)$ . Together with (4) gives $b^2\equiv d^2\equiv 1(mod\ p)$ so that $b\equiv d\equiv 1(\mod p)$ OR $b\equiv d\equiv -1(\mod p)$. Substituting in (2) gives $a^2\equiv 2(\mod p)$ or $a^2\equiv -2(\mod p)$
But one of the two equations must have a solution, because for a prime $p\equiv 3(\mod 4)$, if $r$ is not a quadratic residue, then $(-r)$ is. [Proof of this fact: If $(\frac{r}{p})=-1$ then $(\frac{-r}{p})=(\frac{-1}{p})(\frac{r}{p})=(-1)*(-1)=1$ where $(\frac{r}{p})$ is the Legendre symbol.]
Hence the congruences have at least one solution for $a, b, c, d$ for modulo every prime and thus$latex x^4+1$ is reducible modulo every prime. ∎