1.5 Factoring polynomials ‣ Chapter 1 Basic Definitions and Results

Proposition 1.11

Let $r\in\mathbb{Q}{}$ be a root of a polynomial

a_{m}X^{m}+a_{m-1}X^{m-1}+\cdots+a_{0},\quad a_{i}\in\mathbb{Z},

and write $r=c/d$ , $c,d\in\mathbb{Z}$ , $\gcd(c,d)=1$ . Then $c|a_{0}$ and $d|a_{m}.$

Proof.

It is clear from the equation

a_{m}c^{m}+a_{m-1}c^{m-1}d+\cdots+a_{0}d^{m}=0

that $d|a_{m}c^{m}$ , and therefore, $d|a_{m}.$ Similarly, $c|a_{0}$ . _□

Example 1.12

The polynomial $f(X)=X^{3}-3X-1$ is irreducible in $\mathbb{Q}[X]$ because its only possible roots are $\pm 1$ , and $f(1)\neq 0\neq f(-1)$ .

Proposition 1.13 (Gauss’s Lemma)

Let $f(X)\in\mathbb{Z}[X]$ . If $f(X)$ factors nontrivially in $\mathbb{Q}[X]$ , then it factors nontrivially in $\mathbb{Z}{}[X]$ .

Proof.

Let $f=gh$ in $\mathbb{Q}{}[X]$ with $g,h$ nonconstant. For suitable integers $m$ and $n$ , $g_{1}\overset{\smash{\lower 1.31395pt\hbox{{def}}}}{=}mg$ and $h_{1}\overset{\smash{\lower 1.31395pt\hbox{{def}}}}{=}nh$ have coefficients in $\mathbb{Z}{}$ , and so we have a factorization

mnf=g_{1}\cdot h_{1}\text{ in }\mathbb{Z}{}[X]\text{.}

If a prime $p$ divides $mn$ , then, looking modulo $p$ , we obtain an equation

0=\overline{g_{1}}\cdot\overline{h_{1}}\text{ in }\mathbb{F}{}_{p}[X]\text{.}

Since $\mathbb{F}_{p}[X]$ is an integral domain, this implies that $p$ divides all the coefficients of at least one of the polynomials $g_{1},h_{1}$ , say $g_{1}$ , so that $g_{1}=pg_{2}$ for some $g_{2}\in\mathbb{Z}[X]$ . Thus, we have a factorization

(mn/p)f=g_{2}\cdot h_{1}\text{ in }\mathbb{Z}{}[X]\text{.}

Continuing in this fashion, we eventually remove all the prime factors of $mn$ , and so obtain a nontrivial factorization of $f$ in $\mathbb{Z}{}[X]$ . _□

Proposition 1.14

If $f\in\mathbb{Z}[X]$ is monic, then every monic factor of $f$ in $\mathbb{Q}[X]$ lies in $\mathbb{Z}[X]$ .

Proof.

Let $g$ be a monic factor of $f$ in $\mathbb{Q}{}[X]$ , so that $f=gh$ with $h\in\mathbb{Q}{}[X]$ also monic. Let $m,n$ be the positive integers with the fewest prime factors such that $mg,nh\in\mathbb{Z}{}[X]$ . As in the proof of Gauss’s Lemma, if a prime $p$ divides $mn$ , then it divides all the coefficients of at least one of the polynomials $mg,nh$ , say $mg$ , in which case it divides $m$ because $g$ is monic. Now $\frac{m}{p}g\in\mathbb{Z}[X]$ , which contradicts the definition of $m$ . _□

Aside 1.15

We sketch an alternative proof of Proposition 1.14. A complex number $\alpha$ is said to be an algebraic integer if it is a root of a monic polynomial in $\mathbb{Z}{}[X]$ . Proposition 1.11 shows that every algebraic integer in $\mathbb{Q}{}$ lies in $\mathbb{Z}$ . The algebraic integers form a subring of $\mathbb{C}{}$ — see Theorem 6.5 of my notes on Commutative Algebra. Now let $\alpha_{1},\ldots,\alpha_{m}$ be the roots of $f$ in $\mathbb{C}{}$ . By definition, they are algebraic integers, and the coefficients of any monic factor of $f$ are polynomials in (certain of) the $\alpha_{i}$ , and therefore are algebraic integers. If they lie in $\mathbb{Q}{}$ , then they lie in $\mathbb{Z}{}$ .

Proposition 1.16 (Eisenstein’s criterion)

Let

f=a_{m}X^{m}+a_{m-1}X^{m-1}+\cdots+a_{0},\quad a_{i}\in\mathbb{Z};

suppose that there is a prime $p$ such that:

$\diamond$

$p$ does not divide $a_{m}$ ,
$\diamond$

$p$ divides $a_{m-1},...,a_{0}$ ,
$\diamond$

$p^{2}$ does not divide $a_{0}$ .

Then $f$ is irreducible in $\mathbb{Q}[X]$ .

Proof.

If $f(X)$ factors nontrivially in $\mathbb{Q}[X]$ , then it factors nontrivially in $\mathbb{Z}[X]$ , say,

a_{m}X^{m}+a_{m-1}X^{m-1}+\cdots+a_{0}=(b_{r}X^{r}+\cdots+b_{0})(c_{s}X^{s}+% \cdots+c_{0})

with $b_{i},c_{i}\in\mathbb{Z}$ and $r,s<m$ . Since $p$ , but not $p^{2}$ , divides $a_{0}=b_{0}c_{0}$ , $p$ must divide exactly one of $b_{0}$ , $c_{0}$ , say, $b_{0}$ . Now from the equation

a_{1}=b_{0}c_{1}+b_{1}c_{0},

we see that $p|b_{1},$ and from the equation

a_{2}=b_{0}c_{2}+b_{1}c_{1}+b_{2}c_{0},

that $p|b_{2}$ . By continuing in this way, we find that $p$ divides $b_{0},b_{1},\ldots,b_{r}$ , which contradicts the condition that $p$ does not divide $a_{m}$ . _□

Remark 1.17

There is an algorithm for factoring a polynomial in $\mathbb{Q}[X]$ . To see this, consider $f\in\mathbb{Q}[X]$ . Multiply $f(X)$ by a rational number so that it is monic, and then replace it by $D^{\deg(f)}f(\frac{X}{D})$ , with $D$ equal to a common denominator for the coefficients of $f$ , to obtain a monic polynomial with integer coefficients. Thus we need consider only polynomials

f(X)=X^{m}+a_{1}X^{m-1}+\cdots+a_{m},\quad a_{i}\in\mathbb{Z}.

From the fundamental theorem of algebra (see LABEL:ag5 below), we know that $f$ splits completely in $\mathbb{C}[X]$ :

f(X)=\prod_{i=1}^{m}(X-\alpha_{i}),\quad\alpha_{i}\in\mathbb{C}.

From the equation

0=f(\alpha_{i})=\alpha_{i}^{m}+a_{1}\alpha_{i}^{m-1}+\cdots+a_{m}\text{,}

it follows that $|\alpha_{i}|$ is less than some bound depending only on the degree and coefficients of $f$ ; in fact,

|\alpha_{i}|\leq\max\{1,mB\}\text{, }B=\max|a_{i}|\text{.}

Now if $g(X)$ is a monic factor of $f(X)$ , then its roots in $\mathbb{C}$ are certain of the $\alpha_{i}$ , and its coefficients are symmetric polynomials in its roots (see p. LABEL:sympol). Therefore, the absolute values of the coefficients of $g(X)$ are bounded in terms of the degree and coefficients of $f$ . Since they are also integers (by 1.14), we see that there are only finitely many possibilities for $g(X)$ . Thus, to find the factors of $f(X)$ we (better PARI) have to do only a finite amount of checking.³³ 3 Of course, there are much faster methods than this. The Berlekamp–Zassenhaus algorithm factors the polynomial over certain suitable finite fields $\mathbb{F}{}_{p}$ , lifts the factorizations to rings $\mathbb{Z}{}/p^{m}\mathbb{Z}$ for some $m$ , and then searches for factorizations in $\mathbb{Z}{}[X]$ with the correct form modulo $p^{m}$ .

Therefore, we need not concern ourselves with the problem of factoring polynomials in the rings $\mathbb{Q}[X]$ or $\mathbb{F}_{p}[X]$ since PARI knows how to do it. For example, typing content(6*X^2+18*X-24) in PARI returns 6, and factor(6*X^2+18*X-24) returns $X-1$ and $X+4$ , showing that

6X^{2}+18X-24=6(X-1)(X+4)

in $\mathbb{Q}[X]$ . Typing factormod(X^2+3*X+3,7) returns $X+4$ and $X+6$ , showing that

X^{2}+3X+3=(X+4)(X+6)

in $\mathbb{F}_{7}[X]$ .

Remark 1.18

One other observation is useful. Let $f\in\mathbb{Z}[X]$ . If the leading coefficient of $f$ is not divisible by a prime $p$ , then a nontrivial factorization $f=gh$ in $\mathbb{Z}{}[X]$ will give a nontrivial factorization $\bar{f}=\bar{g}\bar{h}$ in $\mathbb{F}{}_{p}[X]$ . Thus, if $f(X)$ is irreducible in $\mathbb{F}_{p}[X]$ for some prime $p$ not dividing its leading coefficient, then it is irreducible in $\mathbb{Z}{}[X]$ . This test is very useful, but it is not always effective: for example, $X^{4}-10X^{2}+1$ is irreducible in $\mathbb{Z}{}[X]$ but it is reducible⁴⁴ 4 Here is a proof using only that the product of two nonsquares in $\mathbb{F}{}_{p}^{\times}$ is a square, which follows from the fact that $\mathbb{F}{}_{p}^{\times}$ is cyclic (see Exercise 1-3). If $2$ is a square in $\mathbb{F}{}_{p}$ , then $X^{4}-10X^{2}+1=(X^{2}-2\sqrt{2}X-1)(X^{2}+2\sqrt{2}X-1).$ If $3$ is a square in $\mathbb{F}{}_{p}$ , then $X^{4}-10X^{2}+1=(X^{2}-2\sqrt{3}X+1)(X^{2}+2\sqrt{3}X+1).$ If neither $2$ nor $3$ are squares, $6$ will be a square in $\mathbb{F}{}_{p}$ , and $X^{4}-10X^{2}+1=(X^{2}-(5+2\sqrt{6}))(X^{2}-(5-2\sqrt{6})).$ The general study of such polynomials requires nonelementary methods. See, for example, the paper Brandl, AMM, 93 (1986), pp. 286–288, which proves that for every composite integer $n\geq 1$ , there exists a polynomial in $\mathbb{Z}{}[X]$ of degree $n$ that is irreducible over $\mathbb{Z}$ but reducible modulo all primes. modulo every prime $p$ .