FACTORING POLYNOMIALS - A Book of Abstract Algebra

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 image. To begin with, all the ideals of F[x] are principal ideals, which was also the case for the ideals of image.

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) = a0+…+anxn, then

image

hence ca(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) = a0 + ⋯ + anxn, the associates of a(x) are all its nonzero constant multiples. Among these multiples is the polynomial

image

which is equal to (1/an)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 + 4x + 2x3 is image.

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 alinear 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) = la(x) + 0b(x) and b(x) = 0a(x) + 1b(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

image

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) = x2 + 1 is irreducible over image; but over image it has factors (x + i)(xi).

We next state the analogs for polynomials of Euclid’s lemma and its corollaries. The proofs are almost identical to their counterparts in image; 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) ∣a1(x)a2(x) ⋯ an(x), then p(x) ∣ ai(x) for one of the factors ai(x) among a1(x),. . ., an(x).

Corollary 2 Let q1(x), …, qr(x) and p(x) be monic irreducible polynomials. If p(x) ∣ q1 (x) … qr(x), then p(x) is equal to one of the factors q1(x),...,qr(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) = kp1(x)p2(x) … pr(x)

where k is a constant in F and p1(x), …, pr(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) = kp1(x) ⋯ pr(x) = lq1(x) ⋯ qs(x)

then k = l, r = s, and each pi(x) is equal to a qJ(x).

The proof is the same, in all major respects, as the corresponding proof for image ; 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 image[x] and image[x]. Also, we will learn more about factoring polynomials into irreducibles.

EXERCISES

A. Examples of Factoring into Irreducible Factors

1 Factor x4 − 4 into irreducible factors over image, over image, and over image.

2 Factor x6 − 16 into irreducible factors over image, over image, and over image.

3 Find all the irreducible polynomials of degree ≤ 4 in image2[x].

# 4 Show that x2 + 2 is irreducible in image5[x]. Then factor x4 − 4 into irreducible factors in image5[x]. (By Theorem 3, it is sufficient to search for monic factors.)

5 Factor 2x3 + 4x + 1 in image5[x]. (Factor it as in Theorem 3.)

6 In image6[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 imagep[x], every nonzero polynomial has exactly p − 1 associates.

7 x2 + 1 is reducible in imagep[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 image5[x]. [HINT: Every reducible monic quadratic can be uniquely factored as (x + a)(x + b).]

2 How many reducible quadratics are there in image5[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 a0 + a1x + ⋯ + anxn in F[x] which satisfy a0 + a1 + ⋯ + an = 0. It has been shown (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 Σ aijxiyj in 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)ql(x) + r1,(x)

1 Prove that every common divisor of a(x) and b(x) is a common divisor of b(x) and r1(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 r1(x). This procedure can now be repeated on b(x) and r1(x); divide b(x) by r1(x):

b(x) = r1(x)q2(x)r2(x)

Next

r1(x) = r2(x)q3(x) + r3(x)

image

Finally,

rn1(x) = rn (x)qn+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), r1(x)] = ⋯ = gcd[rn1(x), rn(x)]

Since rn(x) is a divisor of rn1(x), it must be the gcd of rn(x) and rn.1. Thus,

rn(x) = gcd[a(x), b(x)]

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

# 2 Find the gcd of x3 + 1 and x4 + x3 + 2x2 + x − 1. Express this gcd as a linear combination of the two polynomials.

3 Do the same for x24 — 1 and x15 − 1.

4 Find the gcd of x3 + x2 + x + 1 and x4 + x3 + 2x2 + 2x in image3[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 : GG be defined by

h(a0 + a1x + ⋯ + anxn) = an + an1x + ⋯ + a0xn

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 hh = ε.

3 a0 + a1x + ⋯ + anxn is irreducible iff an + anlx + ⋯ + a0xn is irreducible.

4 Let a0 + a1x + ⋯ +anxn = (b0 + ⋯ +bmxm)(c0+ ⋯ +cqxq). Factor

an + an1x + ⋯ + a0xn

5 Let a(x) = a0 + a1x + ⋯ + anxn and â(x) = an + an 1x + ⋯ + a0xn. If cF, prove that a(c) = 0 iff â(1/c) = 0.