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. ∎
Advertisements