How is integer polynomial factorization reduced to factorization over a finite field?

Question

I've read on Wikipedia that the problem of factoring polynomials over $\mathbb Z$ can be reduced to factoring polynomials over some finite field, but I can't find any information on how this is done. Would it be possible to get a "big picture", simplified description of what makes this possible, as well as a reference to a more detailed description?

Answer 1

Partial information can be obtained. Most notably, if a given polynomial $q(x)$ factors over $\Bbb{Z}$ like $q(x)=f(x)g(x)$, then it will have factors of degrees equal to those of $f$ and $g$ modulo every prime as well. This allows us to deduce irreducibility in $\Bbb{Z}[x]$ in many cases:

• If $q(x)$ is irreducible modulo $p$ for some prime $p$, then it must be irreducible in $\Bbb{Z}[x]$ as well.
• If the degrees of factors modulo different primes are incompatible, then again we can conclude that the polynomial is irreducible in $\Bbb{Z}[x]$. For example a quartic that factors as a product of a linear and an irreducible cubic modulo prime $p_1$, and as a product of two quadratics modulo another prime $p_2$ cannot have any proper factors.

Search the site for examples!

On the other hand irreducibility over $\Bbb{Z}$ cannot be deduced from information about factorization over $\Bbb{Z}_p$. Not even if you include all the infinitely many primes. See this thread for examples of polynomials that factor modulo every prime, but yet are irreducible in $\Bbb{Z}[x]$. Qiaochu's answer in particular gives you bits and pieces about the related Galois theory.

---

[Edit:]

Another tool that occured to me is that of Chinese Remainder Theorem. The putative factors in $\Bbb{Z}[x]$ need to be congruent to the modulo $p$ factors. This may force too large coefficients that can be ruled out by other means. As an example consider the polynomial $$ q(x)=x^4-10x^2+1 $$ from the linked question. Modulo $7$ it factors as $$ q(x)=(x^2-x-1)(x^2+x-1) $$ and modulo $11$ it factors like $$ q(x)=(x^2+x+1)(x^2-x+1). $$ Could it have a quadratic factor $f(x)$ in $\Bbb{Z}[x]$? W.l.o.g. (Gauss' lemma) such a factor is monic, so $$ f(x)=x^2+a_1x+a_0. $$ The modulo $7$ factorization tells us that $a_0\equiv-1\pmod7$. But modulo $11$ information says that $a_0\equiv1\pmod{11}$. The Chinese Remainder Theorem then says that modulo $77$ we have $$a_0\equiv 34\pmod{77}.$$ Leaving it to you as an exercise to show that this forces $a_0$ to have too large an absolute value.

Unfortunately I do not know whether this kind of use of the CRT always gives something conclusive.