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

### Chapter 26. SUBSTITUTION IN POLYNOMIALS

Up to now we have treated polynomials as formal expressions. If *a*(*x*) is a polynomial over a field *F*, say

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

this means that the coefficients *a*_{0}, *a*_{1}, …,*a _{n}* are elements of the field

*F*, while the letter

*x*is a

*placeholder*which plays no other role than to occupy a given position.

When we dealt with polynomials in elementary algebra, it was quite different. The letter *x* was called an *unknown* and was allowed to assume numerical values. This made *a*(*x*) into a function having *x* as its independent variable. Such a function is called a *polynomial function*.

This chapter is devoted to the study of polynomial functions. We begin with a few careful definitions.

Let *a*(*x*) = *a*_{0} + *a*_{1}*x* + ⋯+ *a _{n}x^{n}* be a polynomial over

*F*. If

*c*is any element of

*F*, then

*a*_{0} + *a*_{1}*c* + ⋯+ *a _{n}c*

^{n}

is also an element of *F*, obtained by *substituting c* for *x* in the polynomial *a*(*x*). This element is denoted by *a*(*c*). Thus,

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

Since we may substitute any element of *F* for *x*, we may regard *a*(*x*) as a function from *F to F*. As such, it is called a *polynomial function on F*.

The difference between a polynomial and a polynomial function is mainly a difference of viewpoint. Given *a*(*x*) with coefficients in *F*: if *x* is regarded merely as a placeholder, then *a*(*x*) is a polynomial; if *x* is allowed to assume values in *F*, then *a*(*x*) is a polynomial function. The difference is a small one, and we will not make an issue of it.

If *a*(*x*) is a polynomial with coefficients in *F*, and *c* is an element of *F* such that

*a*(*c*) = 0

then we call *c* a *root* of *a*(*x*). For example, 2 is a root of the polynomial 3*x*^{2} + *x* − 14 ∈ [*x*], because 3 · 2^{2} + 2 − 14 = 0.

There is an absolutely fundamental connection between *roots* of a polynomial and *factors* of that polynomial. This connection is explored in the following pages, beginning with the next theorem:

Let *a*(*x*) be a polynomial over a field *F*.

**Theorem 1** *c is a root of a*(*x*) *iff x − c is a factor of a*(*x*).

PROOF: If *x* − *c* is a factor of *a*(*x*), this means that *a*(*x*) = (*x* − *c*)*q*(*x*) for some *q*(*x*). Thus, *a*(*c*) = (*c* − *c*)*q*(*c*) = 0, so *c* is a root of *a*(*x*). Conversely, if *c* is a root of *a*(*x*), we may use the division algorithm to divide *a*(*x*) by *x* − *c*: *a*(*x*) = (*x* − *c*)*q*(*x*) + *r*(*x*). The remainder r(*x*) is either 0 or a polynomial of lower degree than *x* − *c*; but *lower degree than* *x* — *c* means that *r*(*x*) is a constant polynomial: *r*(*x*) = *r* ≥ 0. Then

0 = *a*(*c*) = (*c* − *c*) *q*(*c*) + *r* = *0* + *r* = *r*

Thus, *r* = 0, and therefore *x* − *c* is a factor of *a*(*x*). *■*

__Theorem 1__ tells us that if *c* is a root of *a*(*x*), then *x* − *c* is a *factor* of *a*(*x*) (and vice versa). This is easily extended: if *c _{1}* and

*c*

_{2}are two roots of

*a*(

*x*), then

*x*−

*c*

_{1}and

*x*−

*c*

_{2}are two factors of

*a*(

*x*). Similarly, three roots give rise to three factors, four roots to four factors, and so on. This is stated concisely in the next theorem.

**Theorem 2** *If a*(*x*) *has distinct roots* *c*_{l}, …, *c _{m} in*

*F*,

*then*(

*x*−

*c*

_{1})(

*x*−

*c*

_{2}) ⋯ (

*x*−

*c*

_{m})

*is a factor of a*(

*x*).

PROOF: To prove this, let us first make a simple observation: *if a polynomial a*(*x*) *can be factored, any root of a*(*x*) *must be a root of one of its factors*. Indeed, if *a*(*x*) = *s*(*x*)*t*(*x*) and *a*(*c*) = 0, then *s*(*c*) *t*(*c*) = 0, and therefore either *s*(*c*) = 0 or *t*(*c*) − 0.

Let *c*_{l},…, *c*_{m} be distinct roots of *a*(*x*). By __Theorem 1__,

*a*(*x*) = (*x* − *c*_{1}) *q*_{1}(*x*)

By our observation in the preceding paragraph, *c*_{2} must be a root of *x* − *c*_{1} or of *q*_{1}(*x*). It cannot be a root of *x* − *c*_{1} because *c*_{2} − *c*_{1} ≠ 0; so *c*_{2} is a root of *q*_{1}(*x*). Thus, *q*_{1}(*x*) = (*x* − *c*_{2}) *q*_{2}(*x*), and therefore

*a*(*x*) = (*x* − *c*_{1})(*x* − *c*_{2}) *q*_{2}(*x*)

Repeating this argument for each of the remaining roots gives us our result. ■

An immediate consequence is the following important fact:

**Theorem 3** *If a*(*x*) *has degree n*, *it has at most n roots*.

PROOF: If *a*(*x*) had *n* + 1 roots *c*_{1},…, *c _{n}*

_{ + 1}, then by

__Theorem 2__, (

*x*−

*c*

_{1}) ⋯ (

*x*−

*c*

_{n}_{ + 1}) would be a factor of

*a*(

*x*), and the degree of

*a*(

*x*) would therefore be at least

*x*+ 1. ■

It was stated earlier in this chapter that the difference between polynomials and polynomial functions is mainly a difference of viewpoint. *Mainly*, but not entirely! Remember that two polynomials *a*(*x*) and *b*(*x*) are equal iff corresponding coefficients are equal, whereas two *functions a*(*x*) and *b*(*x*) are equal iff *a*(*x*) = *b*(*x*) for every *x* in their domain. These two notions of equality do not always coincide!

For example, consider the following two polynomials in _{5} [*x*]:

You may check that *a*(0) = *b*(0), *a*(1) = *b*(l),…, *a*(4) = *b*(4); hence *a*(*x*) and *b*(*x*) are equal functions from _{5} to _{5}. But as polynomials, *a*(*x*) and *b*(*x*) are quite distinct! (They do not even have the same degree.)

It is reassuring to know that this cannot happen when the field *F* is infinite. Suppose *a*(*x*) and *b*(*x*) are polynomials over a field *F* which has infinitely many elements. If *a*(*x*) and *b*(*x*) are equal as functions, this means that *a*(*c*) = *b*(*c*) for every *c* ∈ *F*. Define the polynomial *d*(*x*) to be the difference of *a*(*x*) and *b*(*x*): *d*(*x*) = *a*(*x*) − *b*(*x*). Then *d*(*c*) = *0* for every*c* ∈ *F*. Now, if *d*(*x*) were not the zero polynomial, it would be a polynomial (with some finite degree *n*) having *infinitely many roots*, and by __Theorem 3__ this is impossible! Thus, *d*(*x*) is the zero polynomial (all its coefficients are equal to zero), and therefore *a*(*x*) is the same polynomial as *b*(*x*). (They have the same coefficients.)

This tells us that if *F* is a field with infinitely many elements (such as , , or ), there is no need to distinguish between polynomials and polynomial functions. The difference is, indeed, just a difference of viewpoint.

**POLYNOMIALS OVER AND **

In scientific computation a great many functions can be approximated by polynomials, usually polynomials whose coefficients are integers or rational numbers. Such polynomials are therefore of great practical interest. It is easy to find the rational roots of such polynomials, and to determine if a polynomial over is irreducible over . We will do these things next.

First, let us make an important observation:

Let *a*(*x*) be a polynomial with rational coefficients, say

We may now factor out *s* from all but the first term to get

The polynomial *b*(*x*) has *integer coefficients;* and since it differs from *a*(*x*) only by a constant factor, it has the same roots as *a*(*x*). Thus, *for every polynomial with rational coefficients, there is a polynomial with integer coefficients having the same roots*. Therefore, for the present we will confine our attention to polynomials with integer coefficients. The next theorem makes it easy to find all the rational roots of such polynomials:

Let *s/t* be a rational number in simplest form (that is, the integers *s* and *t* do not have a common factor greater than 1). Let *a*(*x*) = *a*_{0} + ⋯ + *a _{n}*

*x*be a polynomial with integer coefficients.

^{n}**Theorem 4** *If s/t is a root of a*(*x*), *then s|a*_{0} *and t|a _{n}*.

PROOF: If *s*/*t* is a root of *a*(*x*), this means that

*a*_{0} + *a*_{1}(*s/t*) + *⋯* + *a _{n}*(

*s*) = 0

^{n}/t^{n}Multiplying both sides of this equation by *t ^{n}* we get

*a*_{0} *t ^{n}* +

*a*

_{1}

*st*−

^{n}^{1}+ ⋯ +

*a*= 0 (1)

_{n}s^{n}We may now factor out *s* from all but the first term to get

− *a*_{0}*t ^{n}* =

*s*(

*a*

_{l}

*t*

^{n}^{ }

^{−}

^{ 1}+ ⋯ +

*a*

_{n}s^{n}^{ }

^{−}

^{ 1}

Thus, *s* /*a*_{0}*t ^{n}*; and since

*s*and

*t*have no common factors,

*s|a*

_{0}. Similarly, in

__Equation (1)__, we may factor out

*t*from all but the last term to get

*t*(*a*_{0}*t ^{n}*

^{ }

^{−}

^{ 1}+ ⋯ +

*a*

_{n}_{ }

_{−}

_{ 1}

*s*

^{n}^{ }

^{−}

^{ l})= −

*a*

_{n}s^{n}Thus, *t\a _{n}s^{n}*; and since

*s*and

*t*have no common factors,

*t\a*.

_{n}*■*

As an example of the way __Theorem 4__ may be used, let us find the rational roots of *a*(*x*) = 2*x*^{4} + 7*x*^{3} + 5*x*^{2} + 7*x* + 3. Any rational root must be a fraction *sit* where *s* is a factor of 3 and *t* is a factor of 2. The possible roots are therefore ±1, ±3, ± and ±. Testing each of these numbers by direct substitution into the equation *a*(*x*) = 0, we find that − and − 3 are roots.

Before going to the next step in our discussion we note a simple but fairly surprising fact.

**Lemma** *Let a*(*x*) = *b*(*x*)*c*(*x*), *where a*(*x*), *b*(*x*), *and c*(*x*) *have integer coefficients. If a prime number p divides every coefficient of a*(*x*), *it either divides every coefficient of b*(*x*) *or every coefficient of c*(*x*).

PROOF: If this is not the case, let *b _{r}* be the first coefficient of

*b*(

*x*) not divisible by

*p*, and let

*c*be the first coefficient of

_{t}*c*(

*x*) not divisible by

*p*. Now,

*a*(

*x*) =

*b*(

*x*)

*c*(

*x*), so

*a _{r}*

_{ + t}=

*b*

_{0}

*c*

_{r}_{ + t}+ ⋯ +

*b*+ ⋯ +

_{r}c_{t}*b*

_{r}_{ + t}

*c*

_{0}

Each term on the right, except *b _{r}c_{t}* is a product

*b*where either

_{i}C_{j}*i*>

*r*or

*j > t*. By our choice of

*b*and

_{r}*c*, if

_{t}*i*>

*r*then

*p*|

*b*, and

_{i}*j*>

*t*then

*p*|

*c*. Thus,

_{j}*p*is a factor of every term on the right with the possible exception of

*b*but

_{r}c_{n}*p*is also a factor of

*a*. Thus,

_{r + t}*p must*be a factor of

*b*hence of either

_{r}c_{n}*b*or

_{r}*c*and this is impossible. ■

_{n}We saw (in the discussion immediately preceding __Theorem 4__) that any polynomial *a*{*x*) with rational coefficients has a constant multiple *ka*(*x*)*, with integer coefficients*, which has the same roots as *a*(*x*). We can go one better; let *a*(*x*)*∈ *[*x*]:

**Theorem 5** *Suppose a*(*x*) *can be factored as a*(*x*) = *b*(*x*)*c*(*x*), *where b*(*x*) *and c*(*x*) *have rational coefficients. Then there are polynomials B*(*x*) *and C*(*x*) *with integer coefficients, which are constant multiples of b*(*x*) *and c*(*x*), *respectively, such that a*(*x*) = *B*(*x*)*C*(*x*).

PROOF. Let *k* and *l* be integers such that *kb*(*x*) and *lc*(*x*) have integer coefficients. Then *kla*(*x*) = [*kb*(*x*)][*lc*(*x*)]. By the lemma, each prime factor of *kl* may now be canceled with a factor of either *kb*(*x*) or *lc*(*x*). *■*

Remember that 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*). If there are *no* such polynomials, then *a*(*x*) is *irreducible over F*.

If we use this terminology, __Theorem 5__ states that *any polynomial with integer coefficients which is reducible over* *is reducible already over* .

In Chapter 25 we saw that every polynomial can be factored into irreducible polynomials. In order to factor a polynomial completely (that is, into irreducibles), we must be able to recognize an irreducible polynomial when we see one! This is not always an easy matter. But there is a method which works remarkably well for recognizing when a polynomial is irreducible over :

**Theorem 6: Eisenstein ’ s irreducibility criterion** *Let*

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

*be a polynomial with integer coefficients. Suppose there is a prime number p which divides every coefficient of a*(*x*) *except the leading cofficient a _{n} ; suppose p does not divide a_{n} and p*

^{2}

*does not divide a*

_{0}.

*Then a*(

*x*)

*is irreducible over*.

PROOF: If *a*(*x*) can be factored over as *a*(*x*) = *b*(*x*)*c*(*x*), then by __Theorem 5__ we may assume *b*(*x*) and *c*(*x*) have integer coefficients: say

*b*(*x*) = *b*_{0} + ⋯ + *b _{k}x^{k}* and

*c*(

*x*) =

*c*

_{0}+ ⋯ +

*c*

_{m}x^{m}Now, *a*_{0} = *b*_{0}*c*_{0};*p* divides *a*_{0} but *p*^{2} does not, so only *one* of *b*_{0}, *c*_{0} is divisible by *p*. Say *p*| *c*_{0} and *p* ∤ *b*_{0}. Next, *a _{n}* =

*b*and

_{k}c_{m}*p*∤

*a*, so

_{n}*p*∤

*c*.

_{m}Let *s* be the smallest integer such that *p* ∤ *c _{s}*. We have

* ^{a}s* =

*b*

_{0}

*c*+

_{s}*b*

_{1}

*c*

_{s}_{ }

_{−}

_{ 1}+ ⋯ +

*b*

_{s}c_{0}

and by our choice of *c _{s}*, every term on the right except

*b*

_{0}

*c*is divisible by

_{s}*p*. But

*a*is divisible by

_{s}also*p*, and therefore

*b*

_{0}

*c*must be divisible by

_{s}*p*. This is impossible because

*p*∤

*b*

_{0}and

*p*∤

*c*. Thus,

_{s}*a*(

*x*) cannot be factored. ■

For example, *x*^{3} + *2x*^{2} + *4x* + *2* is irreducible over because *p* = *2* satisfies the conditions of Eisenstein’s criterion.

**POLYNOMIALS OVER AND **

One of the most far-reaching theorems of classical mathematics concerns polynomials with complex coefficients. It is so important in the frame work of traditional algebra that it is called the *fundamental theorem of algebra*. It states the following:

*Every nonconstant polynomial with complex coefficients has a complex root*.

(The proof of this theorem is based upon techniques of calculus and can be found in most books on complex analysis. It is omitted here.)

It follows immediately that *the irreducible polynomials in* [*x*] *are exactly the polynomials of degree* 1. For if *a*(*x*) is a polynomial of degree greater than 1 in [*x*], then by the fundamental theorem of algebra it has a root *c* and therefore a factor *x* − *c*.

Now, every polynomial in [*x*] can be factored into irreducibles. Since the irreducible polynomials are all of degree 1, it follows that if *a*(*x*) is a polynomial of degree *n* over , it can be factored into

*a*(*x*) = *k*(*x − c _{1}*)(

*x − c*

_{2}) ⋯ (

*x − c*)

_{n}In particular, *if a*(*x*) *has degree n it has n* (*not necessarily distinct*) *complex roots* *c*_{1} … *c _{n}*.

Since every real number a is a complex number (*a* = *a* + 0*i*), what has just been stated applies equally to polynomials with real coefficients. Specifically, if *a*(*x*) is a polynomial of degree *n* with real coefficients, it can be factored into *a*(*x*) = *k*(*x − c _{1}*) ⋯ (

*x*−

*c*), where

_{n}*c*

_{l}, …,

*c*are complex numbers (some of which may be real).

_{n}For our closing comments, we need the following lemma:

**Lemma** *Suppose a*(*x*) ∈ [*x*]. *If a* + *bi is a root of a*(*x*)*, so is a − bi*.

PROOF: Remember that *a − bi* is called the conjugate of *a* + *bi*. If *r* is any complex number, we write *r* for its conjugate. It is easy to see that the function *f*(*r*) = is a homomorphism from to (in fact, it is an isomorphism). For every *real* number *a*, *f*(*a*) = *a*. Thus, if *a*(*x*) has real coefficients, then *f*(*a*_{0} + *a _{1}r* + ⋯ +

*a*) =

_{n}r^{n}*a*

_{0}+

*a*+ ⋯ +

_{1}*a*. Since

_{n}^{n}*f*(0) = 0, it follows that if

*r*is a root of

*a*(

*x*), so is . ■

Now let *a*(*x*) be any polynomial with real coefficients, and let *r* = *a* + *bi* be a complex root of *a*(*x*). Then is also a root of *a*(*x*), so

(*x − r*)(*x* − ) = *x*^{2} − 2*ax* + (*a*^{2} + *b*^{2})

and this is a quadratic polynomial *with real coefficients!* We have thus shown that *any polynomial with real coefficients can be factored into polynomials of degree 1 or 1 in *[*x*]. In particular, the irreducible polynomials of the linear polynomials and [*x*] are the linear polynomials and the irreducible quadratics (that is, the *ax*^{2} + *bx* + *c* where *b*^{2} *− 4ac <* 0).

**EXERCISES**

**A. Finding Roots of Polynomials over Finite Fields**

In order to find a root of *a*(*x*) in a finite field *F*, the simplest method (if *F* is small) is to test every element of *F* by substitution into the equation *a*(*x*) = 0.

**1** Find all the roots of the following polynomials in _{5}[*x*], and factor the polynomials:

*x*^{3} + *x*^{2} + *x* + 1; 3*x*^{4} + *x*^{2} + 1; *x*^{5} + 1; *x*^{4} + 1; *x*^{4} + 4

**# 2** Use Fermat’s theorem to find all the roots of the following polynomials in

_{7}[

*x*]:

*x*^{100} − 1; 3*x*^{98} + *x*^{19} + 3; 2*x*^{74} − *x*^{55} + 2*x* + 6

**3** Using Fermat ’s theorem, find polynomials of degree *≤*6 which determine the same functions as the following polynomials in _{7}[*x*]:

3*x*^{75} − 5*x*^{54} + 2*x*^{13} − *x*^{2}; 4*x*^{108} + 6*x*^{101} − 2*x*^{81}; 3*x*^{103} − *x*^{73} + 3*x*^{55} − *x*^{25}

**4** Explain why every polynomial in * _{p}*[

*x*] has the same roots as a polynomial of degree

*< p*.

**B. Finding Roots of Polynomials over **

**# 1** Find all the rational roots of the following polynomials, and factor them into irreducible polynomials in [

*x*]:

**2** Factor each of the preceding polynomials in [*x*] and in [*x*].

**3** Find associates with integer coefficients for each of the following polynomials:

**4** Find all the rational roots of the polynomials in part 3 and factor them over .

**5** Does 2*x*^{4} + 3*x*^{2} − 2 have any rational roots? Can it be factored into two polynomials of lower degree in [*x*]? Explain.

**C. Short Questions Relating to Roots**

Let *F* be a field.

Prove that parts 1−3 are true in *F*[*x*].

**1** The remainder of *p*(*x*), when divided by *x* − *c*, is *p*(*c*).

**2** (*x* − *c*)|(*p*(*x*) − *p*(*c*)).

**3** Every polynomial has the same roots as any of its associates.

**4** If *a*(*x*) and *b*(*x*) have the same roots in *F*, are they necessarily associates? Explain.

** 5** Prove: If

*a*(

*x*) is a monic polynomial of degree

*n*, and

*a*(

*x*) has

*n*roots

*c*

_{1}, …,

*c*∈

_{n}*F*, then

*a*(

*x*) = (

*x*−

*c*

_{1}) ⋯ (

*x*−

*c*).

_{n}**6** Suppose *a*(*x*) and *b*(*x*) have degree <*n*. If *a*(*c*) = *b*(*c*) for *n* values of *c*, prove that *a*(*x*) = *b*(*x*).

**7** There are infinitely many irreducible polynomials in _{5}[*x*].

**# 8** How many roots does

*x*

^{2}−

*x*have in

_{10}? In

_{11}? Explain the difference.

**D. Irreducible Polynomials in [ x] by Eisenstein’s Criterion (and Variations on the Theme)**

**1** Show that each of the following polynomials is irreducible over :

**2** It often happens that a polynomial *a*(*y*), as it stands, does not satisfy the conditions of Eisenstein’s criterion, but with a simple change of variable y = *x* + *c*, it does. It is important to note that if *a*(*x*) can be factored into *p*(*x*)*q*(*x*), then certainly *a*(*x* + *c*) can be factored into *p*(*x* + *c*)*q*(*x* + *c*). Thus, the irreducibility of *a*(*x* + *c*) implies the irreducibility of *a*(*x*).

(*a*) Use the change of variable *y* = *x* + l to show that *x*^{4} + 4*x* + l is irreducible in [*x*]. [In other words, test (*x* + l)^{4} + 4(*x* + 1) + 1 by Eisenstein’s criterion.]

(*b*) Find an appropriate change of variable to prove that the following are irreducible in [*x*]:

*x*^{4} + 2*x*^{2} − l; *x*^{3} −3*x* + 1; *x*^{4} + 1; *x*^{4} − 10*x*^{2} + 1

**# 3** Prove that for any prime

*p*,

*x*

^{p}^{ }

^{−}

^{ l}+

*x*

^{p}^{ }

^{−}

^{ 2}+ ⋯ +

*x*+ 1 is irreducible in [

*x*].[HINT: By elementary algebra,

(*x* − 1)(*x ^{p}*

^{ }

^{−}

^{1}+

*x*

^{p}^{ }

^{−}

^{ 2}+ ⋯ +

*x*+ 1) =

*x*

^{p}^{ }

^{−}

^{ 1}

hence

Use the change of variable *y* = *x* + 1, and expand by the binomial theorem.

**4** By __Exercise G3__ of __Chapter 25__, the function

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

*a*+

_{n}*a*

_{n}_{ }

_{−}

_{ 1}

*x*+ ⋯ +

*a*

_{0}

*x*

^{n}restricted to polynomials with nonzero constant term matches irreducible polynomials with irreducible polynomials. Use this fact to state a dual version of Eisenstein’s irreducibility criterion.

**5** Use part 4 to show that each of the following polynomials is irreducible in [*x*]:

**E. Irreducibility of Polynomials of Degree ≤4**

**1** Let *F* be any field. Explain why, if *a*(*x*) is a quadratic or cubic polynomial in *F*[*x*], *a*(*x*) is irreducible in *F*[*x*] iff *a*(*x*) has no roots in *F*.

**2** Prove that the following polynomials are irreducible in [*x*]:

**3** Suppose a monic polynomial *a*(*x*) of degree 4 in *F*[*x*] has no roots in *F*. Then *a*(*x*)is reducible iff it is a product of two quadratics *x*^{2} + *ax* + *b* and *x*^{2} + *cx* + *d*, that is, iff

*a*(*x*) = *x*^{4} + (*a* + *c*)*x*^{3} + (*ac* + *b* + *d*)*x*^{2} + (*bc* + *ad*)*x* +*bd*

If the coefficients of *a*(*x*) cannot be so expressed (in terms of *any a*, *b*,*c*, *d* ∈ *F*) then *a*(*x*) must be irreducible.

**Example** *a*(*x*) = *x*^{4} + 2*x*^{3} + *x* + 1; *then bd* = 1, *so b* = d = ±1; *thus*, *bc* + *ad* = ±(*a* + *c*), but *a* + *c* = 2 *and* *bc* + *ad* = 1; *which is impossible*.

Prove that the following polynomials are irreducible in [*x*] (use __Theorem 5__, searching only for integer values of *a*, *b*, *c*, *d*):

*x*^{4} − 5*x*^{2} + 1; 3*x*^{4} − *x*^{2} − 2; *x*^{4} + *x*^{3} + 3*x* + 1

**4** Prove that the following polynomials are irreducible in _{5}[*x*]:

2*x*^{3} + *x*^{2} + 4*x* + l; *x*^{4} + 2; *x*^{4} + 4*x*^{2} + 2; *x*^{4} +1

**F. Mapping onto _{n} to Determine Irreducibility over **

If *h* : → * _{n}* is the natural homomorphism, let : [

*x*] →

*[*

_{n}*x*] be defined by

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

*h*(

*a*

_{0}) +

*h*(

*a*

_{l})

*x*+ ⋯ +

*h*(

*a*)

_{n}*x*

^{n}In __Chapter 24__, __Exercise G__, it is proved that is a homomorphism. Assume this fact and prove:

**# 1** If (

*a*(

*x*)) is irreducible in

*[*

_{n}*x*] and

*a*(

*x*) is monic, then

*a*(

*x*) is irreducible in [

*x*].

**2** *x*^{4} + 10*x*^{3} + 7 is irreducible in [*x*] by using the natural homomorphism from to _{5}.

**3** The following are irreducible in [*x*] (find the right value of *n* and use the natural homomorphism from to * _{n}*):

*x*^{4} − 10 *x*^{2} + 1; *x*^{4} +7 *x*^{3} + 14*x*^{2} + 3; *x*^{5} +1

**G. Roots and Factors in A[x] When A Is an Integral Domain**

It is a useful fact that __Theorems 1__, __2__, and __3__ are still true in *A*[*x*] when *A* is not a field, but merely an integral domain. The proof of __Theorem 1__ must be altered a bit to avoid using the division algorithm. We proceed as follows:

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

*c*is a root of

*a*(

*x*), consider

*a*(*x*) − *a*(*c*) = *a*_{1}(*x* − *c*) + *a*_{2}(*x*^{2} − *c*^{2}) + ⋯ + *a _{n}*(

*x*−

^{n}*c*)

^{n}**1** Prove that for *k* = 1, …, *n*:

*a _{k}*(

*x*) =

^{k}− c^{k}*a*(

_{k}*x − c*)(

*x*

^{k}^{ }

^{−}

^{ l}+

*x*

^{k}^{ }

^{−}

^{ 2}

*c*+

*⋯*+

*c*

^{k}^{ }

^{−}

^{ l})

**2** Conclude from part 1 that *a*(*x*) − *a*(*c*) = (*x − c*)*q*(*x*) for some *q*(*x*).

**3** Complete the proof of __Theorem 1__, explaining why this particular proof is valid when *A* is an integral domain, not necessarily a field.

**4** Check that __Theorems 2__ and __3__ are true in *A*[*x*] when *A* is an integral domain.

**H. Polynomial Interpolation**

One of the most important applications of polynomials is to problems where we are given several values of *x* (say, *x* = *a*_{0},*a*_{1}, …, *a _{n}*) and corresponding values of

*y*(say,

*y*=

*b*

_{0},

*b*,…,

*b*), and we need to find a function

_{n}*y*=

*f*(

*x*) such that

*f*(

*a*

_{0}) =

*b*

_{0},

*f*(

*a*

_{1}) =

*b*

_{1},…,

*f*(

*a*) =

_{n}*b*. The simplest and most useful kind of function for this purpose is a polynomial function of the lowest possible degree.

_{n}We now consider a commonly used technique for constructing a polynomial *p*(*x*) of degree *n* which assumes given values *b*_{0}, *b*_{1},…, *b _{n}* are given points

*a*

_{0},

*a*

_{1},…,

*a*,. That is,

_{n}*p*(*a*_{0})= *b*_{0},*p*(*a*_{1})=*b*, …,*p*(*a _{n}*) =

*b*

_{n}First, for each *i* = 0,1, …, *n*, let

*q _{i}*(

*x*)= (

*x*−

*a*

_{0}) ⋯(

*x*−

*a*

_{i}_{ }

_{−}

_{ 1})(

*x*−

*a*

_{i}_{ +1}) ⋯ (

*x*−

*a*)

_{n}**1** Show that *q _{i}*(

*a*) = 0 for

_{j}*j ≠ i*, and

*q*(

_{i}*a*) ≠ 0.

_{i}Let *q _{i}*(

*a*) =

_{i}*c*, and define

_{i}*p*(

*x*) as follows:

(This is called the *Lagrange interpolation formula*.)

**2** Explain why *p*(*a*_{0}) = *b*_{0}, *p*(*a _{x}*) =,…,

*p*(

*a*)=

_{n}*b*.

_{n}**# 3** Prove that there is one and

*only*one polynomial

*p*(

*x*) of degree

*≤ n*such that

*p*(

*a*

_{0}) =

*b*

_{0}

*, …, p*(

*a*) =

_{n}*b*.

_{n}**4** Use the Lagrange interpolation formula to prove that if *F* is a finite field, every function from *F* to *F* is equal to a polynomial function. (In fact, the degree of this polynomial is less than the number of elements in *F*.)

**5** If *t*(*x*) is any polynomial in *F*[*x*], and *a*_{0}, …, *a _{n}* ∈

*F*, the unique polynomial

*p*(

*x*) of degree

*≤ n*such that

*p*(

*a*

_{0}) =

*t*(

*a*

_{0}), …,

*p*(

*a*) =

_{n}*t*(

*a*) is called the

_{n}*Lagrange interpolator*for

*t*(

*x*) and

*a*

_{0}, …,

*a*. Prove that the remainder, when

_{n}*t*(

*x*) is divided by (

*x*−

*a*)(

_{0}*x*−

*a*

_{1}) ⋯ (

*x*−

*a*), is the Lagrange interpolator.

_{n}**I. Polynomial Functions over a Finite Field**

**1** Find three polynomials in _{5}[*x*] which determine the same function as

*x*^{2} − *x* + 1

**2** Prove that *x ^{p}* −

*x*has

*p*roots in

*[*

_{p}*x*], for any prime

*p*. Draw the conclusion that in

*[*

_{p}*x*],

*x*−

^{p}*x*can be factored as

*x ^{p}* −

*x*=

*x*(

*x*− 1)(

*x*− 2) ⋯ [

*x*− (

*p*− 1)]

**3** Prove that if *a*(*x*) and *b*(*x*) determine the same function in * _{p}*[

*x*], then

(*x ^{p}* −

*x*)|(

*a*(

*x*)−

*b*(

*x*))

In the next four parts, let *F* be any finite field.

**# 4** Let

*a*(

*x*) and

*b*(

*x*) be in

*F*[

*x*]. Prove that if

*a*(

*x*) and

*b*(

*x*) determine the same function, and if the number of elements in

*F*exceeds the degree of

*a*(

*x*) as well as the degree of

*b*(

*x*), then

*a*(

*x*) =

*b*(

*x*).

**5** Prove: The set of all *a*(*x*) which determine the zero function is an ideal of *F*[*x*]. What its generator?

**6** Let (*F*) be the ring of all functions from *F* to *F*, defined in the same way as (). Let *h*: *F*[*x*]→ (*F*) send every polynomial *a*(*x*) to the polynomial function which it determines. Show that *h* is a homomorphism from *F*[*x*] *onto *(*F*). (NOTE: To show that *h* is *onto*, use __Exercise H4__.)

**7** Let *F* = {*C* _{1}, …, *c _{n}*} and

*p*(

*x*) = (

*x*−

*c*

_{1}) ⋯ (

*x*−

*c*). Prove that

_{n}*F*[*x*]/⟨*p*(*x*)⟩ ≅ (*F*)