## A Book of Abstract Algebra, Second Edition (1982)

### Chapter 25. FACTORING POLYNOMIALS

Just as every integer can be factored into primes, so every polynomial can be factored into “irreducible” polynomials which cannot be factored further. As a matter of fact, polynomials behave very much like integers when it comes to factoring them. This is especially true when the polynomials have all their coefficients in a *field*.

Throughout this chapter, we let *F* represent some field and we consider polynomials over *F*. It will be found that *F*[*x*] has a considerable number of properties in common with . To begin with, all the ideals of *F*[*x*] are principal ideals, which was also the case for the ideals of .

Note carefully that in *F*[*x*], the principal ideal generated by a polynomial *a*(*x*) consists of all the products *a*(*x*)*s*(*x*) as *a*(*x*) remains fixed and *s*(*x*) ranges over all the members of *F*[*x*].

**Theorem 1** *Every ideal of F*[*x*] *is principal*.

PROOF: Let *J* be any ideal of *F*[*x*]. If *J* contains nothing but the zero polynomial, *J* is the principal ideal generated by 0. If there are nonzero polynomials in *J*, let *b*(*x*) be any polynomial of *lowest degree* in *J*. We will show that *J*=⟨(*b*(*x*)⟩, which is to say that every element of *J* is a polynomial multiple *b*(*x*)*q*(*x*) of *b*(*x*).

Indeed, if *a*(*x*) is any element of *J*, we may use the division algorithm to write *a*(*x*) = *b*(*x*)*q*(*x*) + *r*(*x*), where *r*(*x*) = 0 or deg *r*(*x*) < deg *b*(*x*). Now, *r*(*x*) = *a*{*x*) −*b*(*x*)*q*(*x*); but *a*(*x*) was chosen in *J*, and *b*(*x*) ∈ *J*; hence *b*(*x*)*q*(*x*) ∈ *J*. It follows that *r*(*x*) is in *J*.

If *r*(*x*) ≠ 0, its degree is less than the degree of *b*(*x*). But this is impossible because *b*(*x*) is a polynomial of lowest degree in *J*. Therefore, of necessity, *r*(*x*) = 0.

Thus, finally, *a*(*x*) = *b*(*x*)*q*(*x*); so every member of *J* is a multiple of *b*(*x*), as claimed. ■

It follows that every ideal *J* of *F*[*x*] is principal. In fact, as the proof above indicates, *J* is generated by any one of its members of lowest degree.

Throughout the discussion which follows, remember that we are considering polynomials in a fixed domain *F*[*x*] where *F* is a *field*.

Let *a*(*x*) and *b*(*x*) be in *F*[*x*]. We say that *b*(*x*) is a *multiple* of *a*(*x*) if

*b*(*x*) = *a*(*x*)*s*(*x*)

for some polynomial *s*(*x*) in *F*[*x*]. If *b*(*x*) is a multiple of *a*(*x*), we also say that *a*(*x*) is a *factor* of *b*(*x*), or that *a*(*x*) *divides* *b*(*x*). In symbols, we write

*a*(*x*)∣*b*(*x*)

Every nonzero constant polynomial divides every polynomial. For if *c* ≠ 0 is constant and *a*(*x*) = *a*_{0}+…+*a _{n}x^{n}*, then

hence *c* ∣ *a*(*x*). A polynomial *a*(*x*) is invertible iff it is a divisor of the unity polynomial 1. But if *a*(*x*)*b*(*x*) = 1, this means that *a*(*x*) and *b*(*x*) both have degree 0, that is, are constant polynomials: *a*(*x*) = *a*, *b*(*x*) = *b*, and *ab* = 1. Thus,

*the invertible elements of* *F*[*x*] *are all the nonzero constant polynomials*.

A pair of nonzero polynomials *a*(*x*) and *b*(*x*) are called *associates* if they divide one another: *a*(*x*)∣*b*(*x*) and *b*(*x*)∣*a*(*x*). That is to say,

*a*(*x*) = *b*(*x*)*c*(*x*) and *b*(*x*) = *a*(*x*)*d*(*x*)

for some *c*(*x*) and *d*(*x*). If this happens to be the case, then

*a*(*x*) = *b*(*x*)*c*(*x*) = *a*(*x*)*d*(*x*)*c*(*x*)

hence *d*(*x*)*c*(*x*) = 1 because *F*[*x*] is an integral domain. But then *c*(*x*) and *d*(*x*) are constant polynomials, and therefore *a*(*x*) and *b*(*x*) are constant multiples of each other. Thus, in *F*[*x*],

*a*(*x*) *and b*(*x*) *are associates iff they are constant multiples of each other*.

If *a*(*x*) = *a*_{0} + ⋯ + *a _{n}x^{n}*, the associates of

*a*(

*x*) are all its nonzero constant multiples. Among these multiples is the polynomial

which is equal to (1/*a _{n}*)

*a*(

*x*), and which has 1 as its leading coefficient. Any polynomial whose leading coefficient is equal to 1 is called

*monk*. Thus,

*every nonzero polynomial a*(

*x*)

*has a unique monic associate*. For example, the monic associate of 3 + 4

*x*+ 2

*x*

^{3}is .

A polynomial *d*(*x*) is called a *greatest common divisor* of *a*(*x*) and *b*(*x*) if *d*(*x*) divides *a*(*x*) and *b*(*x*), and is a multiple of any other common divisor of *a*(*x*) and *b*(*x*); in other words,

(i)*d*(*x*)∣*a*(*x*) and *d*(*x*)∣*b*(*x*), and

(ii)For any *u*(*x*) in *F*[*x*], if *u*(*x*)∣*a*(*x*) and *u*(*x*)∣*b*(*x*), then *u*(*x*)∣*d*(*x*). According to this definition, two different gcd’s of *a*(*x*) and *b*(*x*) divide each other, that is, are associates. Of all the possible gcd’s of *a*(*x*) and *b*(*x*), we select the monic one, call it *the* gcd of *a*(*x*) and *b*(*x*), and denote it by gcd[*a*(*x*), *b*(*x*)].

It is important to know that any pair of polynomials always *has* a greatest common divisor.

**Theorem 2** *Any two nonzero polynomials a*(*x*) *and b*(*x*) *in F*[*x*] *have a gcd d*(*x*).*Furthermore*, *d*(*x*) *can be expressed as a* “*linear combination*”

*d*(*x*) = *r*(*x*)*a*(*x*) + *s*(*x*)*b*(*x*)

*where r*(*x*) *and s*(*x*) *are in F*[*x*].

PROOF: The proof is analogous to the proof of the corresponding theorem for integers. If *J* is the set of all the linear combinations

*u*(*x*)*a*(*x*) + υ(*x*)*b*(*x*)

as *u*(*x*) and υ(*x*) range over *F*[*x*], then *J* is an ideal of *F*[*x*], say the ideal ⟨*d*(*x*)⟩ generated by *d*(*x*). Now *a*(*x*) = l*a*(*x*) + 0*b*(*x*) and *b*(*x*) = 0*a*(*x*) + 1*b*(*x*), so *a*(*x*) and *b*(*x*) are in *J*. But every element of 7 is a multiple of *d*(*x*), so

*d*(*x*)∣*a*(*x*) and *d*(*x*)∣*b*(*x*)

If *k*(*x*) is any common divisor of *a*(*x*) and *b*(*x*), this means there are polynomials *f*(*x*) and *g*(*x*) such that *a*(*x*) = *k*(*x*)*f*(*x*) and *b*(*x*) = *k*(*x*)*g*(*x*). Now, *d*(*x*) ∈ *J*, so *d*(*x*) can be written as a linear combination

hence *k*(*x*)∣*d*(*x*). This confirms that *d*(*x*) is the gcd of *a*(*x*) and *b*(*x*). ■

Polynomials *a*(*x*) and *b*(*x*) in *F*[*x*] are said to be *relatively prime* if their gcd is equal to 1. (This is equivalent to saying that their only common factors are constants in *F*.)

A polynomial *a*(*x*) of positive degree is said to be *reducible over F* if there are polynomials *b*(*x*) and *c*(*x*) in *F*[*x*], both of positive degree, such that

*a*(*x*) = *b*(*x*)*c*(*x*)

Because *b*(*x*) and *c*(*x*) both have positive degrees, and the sum of their degrees is deg *a*(*x*), *each has degree less than* deg *a*(*x*).

A polynomial *p*(*x*) of positive degree in *F*[*x*] is said to be *irreducible over F* if it cannot be expressed as the product of two polynomials of positive degree in *F*[*x*]. Thus, *p*(*x*) is irreducible iff it is not reducible.

When we say that a polynomial *p*(*x*) is irreducible, it is important that we specify *irreducible over the field F*. A polynomial may be irreducible over *F*, yet reducible over a larger field *E*. For example, *p*(*x*) = *x*^{2} + 1 is irreducible over ; but over it has factors (*x* + *i*)(*x* − *i*).

We next state the analogs for polynomials of Euclid’s lemma and its corollaries. The proofs are almost identical to their counterparts in ; therefore they are left as exercises.

**Euclid’s lemma for polynomials** *Let p*(*x*) *be irreducible. If p*(*x*)∣ *a*(*x*)*b*(*x*), *then p*(*x*)∣*a*(*x*) *or p*(*x*)∣*b*(*x*).

**Corollary 1** *Let p*(*x*) *be irreducible. If p*(*x*) ∣*a*_{1}(*x*)*a*_{2}(*x*) ⋯ *a _{n}*(

*x*),

*then p*(

*x*) ∣

*a*(

_{i}*x*)

*for one of the factors a*(

_{i}*x*)

*among a*

_{1}(

*x*),. . .,

*a*(

_{n}*x*).

**Corollary 2** *Let q*_{1}(*x*), …, *q _{r}*(

*x*)

*and p*(

*x*)

*be monic irreducible polynomials. If p*(

*x*) ∣

*q*

_{1}(

*x*) …

*q*(

_{r}*x*),

*then p*(

*x*)

*is equal to one of the factors*

*q*

_{1}(

*x*),...,

*q*(

_{r}*x*).

**Theorem 3: Factorization into irreducible polynomials** *Every polynomial a*(*x*) *of positive degree in F*[*x*] *can be written as a product*

*a*(*x*) = *kp*_{1}(*x*)*p*_{2}(*x*) … *p _{r}*(

*x*)

*where k is a constant in F and p*_{1}(*x*), …, *p _{r}*(

*x*)

*are monic irreducible polynomials of F*[

*x*].

If this were not true, we could choose a polynomial *a*(*x*) *of lowest degree* among those which cannot be factored into irreducibles. Then *a*(*x*) is reducible, so *a*(*x*) = *b*(*x*)*c*(*x*) where *b*(*x*) and *c*(*x*) have lower degree than *a*(*x*). But this means that *b*(*x*) and *c*(*x*) *can* be factored into irreducibles, and therefore *a*(*x*) can also.

**Theorem 4: Unique factorization** *If a*(*x*) *can be written in two ways as a product of monic irreducibles, say*

*a*(*x*) = *kp*_{1}(*x*) ⋯ *p _{r}*(

*x*) =

*lq*

_{1}(

*x*) ⋯

*q*(

_{s}*x*)

*then k* = *l*, *r* = *s*, *and each p _{i}*(

*x*)

*is equal to a q*(

_{J}*x*).

The proof is the same, in all major respects, as the corresponding proof for ; it is left as an exercise.

In the next chapter we will be able to improve somewhat on the last two results in the special cases of [*x*] and [*x*]. Also, we will learn more about factoring polynomials into irreducibles.

**EXERCISES**

**A. Examples of Factoring into Irreducible Factors**

**1** Factor *x*^{4} − 4 into irreducible factors over , over , and over .

**2** Factor *x*^{6} − 16 into irreducible factors over , over , and over .

**3** Find all the irreducible polynomials of degree ≤ 4 in _{2}[*x*].

**# 4** Show that

*x*

^{2}+ 2 is irreducible in

_{5}[

*x*]. Then factor

*x*

^{4}− 4 into irreducible factors in

_{5}[

*x*]. (By

__Theorem 3__, it is sufficient to search for monic factors.)

**5** Factor 2*x*^{3} + 4*x* + 1 in _{5}[*x*]. (Factor it as in __Theorem 3__.)

**6** In _{6}[*x*], factor each of the following into two polynomials of degree 1 : *x*, *x* + 2, *x* + 3. Why is this possible?

**B. Short Questions Relating to Irreducible Polynomials**

Let *F* be a field. Explain why each of the following is true in *F*[*x*]:

**1** Every polynomial of degree 1 is irreducible.

**2** If *a*(*x*) and *b*(*x*) are distinct monic polynomials, they cannot be associates.

**3** Any two distinct irreducible polynomials are relatively prime.

**4** If *a*(*x*) is irreducible, any associate of *a*(*x*) is irreducible.

**5** If *a*(*x*)≠, *a*(*x*) cannot be an associate of 0.

**6** In * _{p}*[

*x*], every nonzero polynomial has exactly

*p*− 1 associates.

**7** *x*^{2} + 1 is reducible in * _{p}*[

*x*] iff

*p*=

*a*+

*b*where

*ab*≡ 1 (mod

*p*).

**C. Number of Irreducible Quadratics over a Finite Field**

**1** Without finding them, determine *how many* reducible monic quadratics there are in _{5}[*x*]. [HINT: Every reducible monic quadratic can be uniquely factored as (*x* + *a*)(*x* + *b*).]

**2** How many reducible quadratics are there in _{5}[*x*]? How many irreducible quadratics?

**3** Generalize: How many irreducible quadratics are there over a finite field of *n* elements?

**4** How many irreducible cubics are there over a field of *n* elements?

**D. Ideals in Domains of Polynomials**

Let *F* be a field, and let *J* designate any ideal of *F*[*x*]. Prove parts 1−4.

**1** Any two generators of *J* are associates.

**2** *J* has a *unique* monic generator *m*(*x*). An arbitrary polynomial *a*(*x*) ∈ *F*[*x*] is in *J* iff *m*(*x*) ∣ *a*(*x*).

**3** *J* is a prime ideal iff it has an irreducible generator.

**# 4** If

*p*(

*x*) is irreducible, then ⟨

*p*(

*x*)⟩ is a

*maximal*ideal of

*F*[

*x*]. (See

__Chapter 18__,

__Exercise H5__.)

**5** Let *S* be the set of all polynomials *a*_{0} + *a*_{1}*x* + ⋯ + *a _{n}x^{n}* in

*F*[

*x*] which satisfy

*a*

_{0}+

*a*

_{1}+ ⋯ +

*a*= 0. It has been shown (

_{n}__Chapter 24__,

__Exercise E5__) that

*S*is an ideal of

*F*[

*x*]. Prove that

*x*− 1 ∈

*S*, and explain why it follows that

*S*=⟨− 1⟩.

**6** Conclude from part 5 that *F*[*x*]/⟨*x* − 1⟩ ≅ *F*. (See __Chapter 24__, __Exercise F4__.)

**7** Let *F*[*x*, *y*] denote the domain of all the polynomials Σ *a _{ij}x*

^{i}

*y*in

^{j}*two*letters

*x*and

*y*, with coefficients in

*F*. Let

*J*be the ideal of

*F*[

*x*,

*y*] which contains all the polynomials whose constant coefficient in zero. Prove that

*J*is not a principal ideal. Conclude that

__Theorem 1__is not true in

*F*[

*x*,

*y*].

**E. Proof of the Unique Factorization Theorem**

**1** Prove Euclid’s lemma for polynomials.

**2** Prove the two corollaries of Euclid’s lemma.

**3** Prove the unique factorization theorem for polynomials.

**F. A Method for Computing the gcd**

Let *a*(*x*) and *b*(*x*) be polynomials of positive degree. By the division algorithm, we may divide *a*(*x*) by *b*(*x*):

*a*(*x*) = *b*(*x*)*q*_{l}(*x*) + *r*_{1},(*x*)

**1** Prove that every common divisor of *a*(*x*) and *b*(*x*) is a common divisor of *b*(*x*) and *r*_{1}(*x*).

It follows from part 1 that the gcd of *a*(*x*) and *b*(*x*) is the same as the gcd of *b*(*x*) and *r*_{1}(*x*). This procedure can now be repeated on *b*(*x*) and *r*_{1}(*x*); divide *b*(*x*) by *r*_{1}(*x*):

*b*(*x*) = *r*_{1}(*x*)*q*_{2}(*x*)*r*_{2}(*x*)

Next

*r*_{1}(*x*) = *r*_{2}(*x*)*q*_{3}(*x*) + *r*_{3}(*x*)

Finally,

*r _{n}*

_{−}

_{1}(

*x*) =

*r*(

_{n}*x*)

*q*

_{n}_{+1}(

*x*) + 0

In other words, we continue to divide each remainder by the succeeding remainder. Since the remainders continually decrease in degree, there must ultimately be a zero remainder. But we have seen that

gcd[*a*(*x*),*b*(*x*)] = gcd[*b*(*x*), *r*_{1}(*x*)] = ⋯ = gcd[*r _{n}*

_{−}

_{1}(

*x*),

*r*(

_{n}*x*)]

Since *r _{n}*(

*x*) is a divisor of

*r*

_{n}_{−}

_{1}(

*x*), it must be the gcd of

*r*(

_{n}*x*) and

*r*

_{n}_{−}

_{.1}. Thus,

*r _{n}*(

*x*) = gcd[

*a*(

*x*),

*b*(

*x*)]

This method is called the *euclidean algorithm* for finding the gcd.

**# 2** Find the gcd of

*x*

^{3}+ 1 and

*x*

^{4}+

*x*

^{3}+ 2

*x*

^{2}+

*x*− 1. Express this gcd as a linear combination of the two polynomials.

**3** Do the same for *x*^{24} — 1 and *x*^{15} − 1.

**4** Find the gcd of *x*^{3} + *x*^{2} + *x* + 1 and *x*^{4} + *x*^{3} + 2*x*^{2} + 2*x* in _{3}[*x*].

**G. A Transformation of F[x]**

Let *G* be the subset of *F*[*x*] consisting of all polynomials whose constant term is nonzero. Let *h* : *G* → *G* be defined by

*h*(*a*_{0} + *a*_{1}*x* + ⋯ + *a _{n}x^{n}*) =

*a*+

_{n}*a*

_{n}_{−}

_{1}

*x*+ ⋯ +

*a*

_{0}

*x*

^{n}Prove parts 1−3:

**1** *h* preserves multiplication, that is, *h*[*a*(*x*)*b*(*x*)] = *h*[*a*(*x*)]*h*[*b*(*x*)].

**2** *h* is injective and surjective and *h* ∘ *h* = *ε*.

**3** *a*_{0} + *a*_{1}*x* + ⋯ + *a _{n}x^{n}* is irreducible iff

*a*+

_{n}*a*

_{n}_{−}

_{l}

*x*+ ⋯ +

*a*

_{0}

*x*

^{n}is irreducible.

**4** Let *a*_{0} + *a*_{1}*x* + ⋯ +*a _{n}x^{n}* = (

*b*

_{0}+ ⋯ +

*b*)(

_{m}x^{m}*c*

_{0}+ ⋯ +

*c*). Factor

_{q}x^{q}*a _{n}* +

*a*

_{n}_{−}

_{1}

*x*+ ⋯ +

*a*

_{0}

*x*

^{n}**5** Let *a*(*x*) = *a*_{0} + *a*_{1}*x* + ⋯ + *a _{n}x^{n}* and

*â*(

*x*) =

*a*+

_{n}*a*

_{n}_{ }

_{−}

_{ 1}

*x*+ ⋯ +

*a*

_{0}

*x*. If

^{n}*c*∈

*F*, prove that

*a*(

*c*) = 0 iff â(1/

*c*) = 0.