7.1 Polynomials · Matrix Theory

The eigenvalues of a square matrix will turn out to be the roots of a polynomial attached to it, its characteristic polynomial (Section 7.3). So we need to know how many roots a polynomial can have, when it has any at all, and how its roots show up in its factors. All of this rests on multiplying and dividing polynomials. So far (Definition 1.2.13), $𝐹 [𝑥]$ has only been a vector space. This section gives it a multiplication and develops the algebra of $𝐹 [𝑥]$ that the rest of the book uses. Throughout, $𝐹$ is a field.

7.1.1Multiplying polynomials

To multiply $𝑎_{0} + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2}$ by $𝑏_{0} + 𝑏_{1} 𝑥$ , we expand with the distributive law, use $𝑥^{𝑖} 𝑥^{𝑗} = 𝑥^{𝑖 + 𝑗}$ , and collect equal powers of $𝑥$ :

\begin{aligned} (𝑎_{0} + 𝑎_{1} 𝑥 + 𝑎_{2} 𝑥^{2}) (𝑏_{0} + 𝑏_{1} 𝑥) & = 𝑎_{0} 𝑏_{0} + (𝑎_{0} 𝑏_{1} + 𝑎_{1} 𝑏_{0}) 𝑥 \\ + (𝑎_{1} 𝑏_{1} + 𝑎_{2} 𝑏_{0}) 𝑥^{2} + 𝑎_{2} 𝑏_{1} 𝑥^{3} . \end{aligned}

The coefficient of $𝑥^{𝑘}$ collects the products $𝑎_{𝑖} 𝑏_{𝑗}$ with $𝑖 + 𝑗 = 𝑘$ . A polynomial is its sequence of coefficients (Definition 1.2.13), so we take this rule as the definition.

Definition 7.1.1 (Product of polynomials). Let $𝑝 =$ $(𝑎_{0}, 𝑎_{1}, 𝑎_{2}, \dots)$ and $𝑞 =$ $(𝑏_{0}, 𝑏_{1}, 𝑏_{2}, \dots)$ be polynomials in $𝐹 [𝑥]$ . Their product is $𝑝 𝑞 =$ $(𝑐_{0}, 𝑐_{1}, 𝑐_{2}, \dots)$ , where

𝑐_{𝑘} = \sum_{𝑖 = 0}^{𝑘} 𝑎_{𝑖} 𝑏_{𝑘 - 𝑖} = 𝑎_{0} 𝑏_{𝑘} + 𝑎_{1} 𝑏_{𝑘 - 1} + \dots + 𝑎_{𝑘} 𝑏_{0} .

We also write $𝑐_{𝑘} =$ $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}$ , a sum over the pairs $(𝑖, 𝑗)$ of nonnegative integers with $𝑖 + 𝑗 = 𝑘$ .

The product is again a polynomial. If $𝑎_{𝑖} = 0$ for $𝑖 > 𝑚$ and $𝑏_{𝑗} = 0$ for $𝑗 > 𝑛$ , then for $𝑘 > 𝑚 + 𝑛$ every pair with $𝑖 + 𝑗 = 𝑘$ has $𝑖 > 𝑚$ or $𝑗 > 𝑛$ , so every term of $𝑐_{𝑘}$ is $0$ (Proposition 1.1.15).

Two special cases connect the definition with the notation of Notation 1.2.15. First, $𝑥^{𝑗} 𝑥^{𝑘} = 𝑥^{𝑗 + 𝑘}$ , because the only nonzero term of the product is $1 \cdot 1$ , in position $𝑗 + 𝑘$ . In particular $𝑥^{𝑘}$ is the product of $𝑘$ copies of $𝑥$ , so the notation $𝑥^{𝑘}$ means what it says. Second, a constant $𝑐 = (𝑐, 0, 0, \dots)$ times $𝑞$ is $(𝑐 𝑏_{0}, 𝑐 𝑏_{1}, \dots)$ , which is the scalar multiple $𝑐 𝑞$ of Definition 1.2.13. So writing $𝑐 𝑞$ is unambiguous.

Example 7.1.2 (Products over three fields).

(a)Over $ℚ$ , the product $(1 + 𝑥) (1 - 𝑥 + 𝑥^{2})$ has coefficients $𝑐_{0} = 1$ , $𝑐_{1} = 1 \cdot (- 1) + 1 \cdot 1 = 0$ , $𝑐_{2} = 1 \cdot 1 + 1 \cdot (- 1) = 0$ , and $𝑐_{3} = 1 \cdot 1 = 1$ . So $(1 + 𝑥) (1 - 𝑥 + 𝑥^{2}) =$ $1 +$ $𝑥^{3}$ .
(b)Over $ℂ$ , $(𝑥 - 𝑖) (𝑥 + 𝑖) =$ $𝑥^{2} +$ $(𝑖 - 𝑖) 𝑥 -$ $𝑖^{2} =$ $𝑥^{2} +$ $1$ .
(c)Over $𝔽_{2}$ , ${(1 + 𝑥)}^{2} =$ $1 +$ $(1 + 1) 𝑥 +$ $𝑥^{2} =$ $1 +$ $𝑥^{2}$ . So $𝑥^{2} + 1$ is a square in $𝔽_{2} [𝑥]$ , while in $ℝ [𝑥]$ it is not even a product of two polynomials of degree $1$ (Corollary 7.1.42).

Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring). For all $𝑝, 𝑞, 𝑟 \in 𝐹 [𝑥]$ and $𝑐 \in 𝐹$ :

(a) $𝑝 𝑞 = 𝑞 𝑝$ ;
(b) $(𝑝 𝑞) 𝑟 = 𝑝 (𝑞 𝑟)$ ;
(c) $𝑝 (𝑞 + 𝑟) =$ $𝑝 𝑞 +$ $𝑝 𝑟$ ;
(d) $1 𝑝 = 𝑝$ ;
(e) $𝑐 (𝑝 𝑞) =$ $(𝑐 𝑝) 𝑞 =$ $𝑝 (𝑐 𝑞)$ .

In particular, $𝐹 [𝑥]$ with its addition and this multiplication is a commutative ring (Definition 1.1.20).

Proof.routine

Uses. Definition 7.1.1 (Product of polynomials), Proposition 1.2.14 ( $𝐹 [𝑥]$ is a vector space), Definition 1.1.20 (Commutative ring), Definition 1.1.1 (Field)

Techniques. Compute entry by entry (Technique 2.4.15)

Hint 1. Compare the

𝑘

-th coefficients of the two sides of each identity, the way one compares entries of matrices.

Hint 2. For (b), write the

𝑘

-th coefficient of each side as a single sum over the triples

(𝑖, 𝑗, 𝑙)

of nonnegative integers with

𝑖 + 𝑗 + 𝑙 = 𝑘

Sketch. Each identity holds coefficient by coefficient. The

𝑘

-th coefficient of

𝑝 𝑞

\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}

, which is symmetric in

𝑝

and

𝑞

. Both sides of (b) have

𝑘

-th coefficient

\sum_{𝑖 + 𝑗 + 𝑙 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} 𝑑_{𝑙}

. Parts (c), (d), and (e) follow from distributivity in

𝐹

, and the additive ring axioms are those of the vector space

𝐹 [𝑥]

Write $𝑝 = (𝑎_{𝑖})$ , $𝑞 = (𝑏_{𝑗})$ , and $𝑟 = (𝑑_{𝑙})$ . All sums below are finite, so they can be reordered and regrouped freely.

(a) The $𝑘$ -th coefficient of $𝑝 𝑞$ is $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}$ , and that of $𝑞 𝑝$ is $\sum_{𝑗 + 𝑖 = 𝑘} 𝑏_{𝑗} 𝑎_{𝑖}$ . These are sums over the same pairs, and $𝑎_{𝑖} 𝑏_{𝑗} = 𝑏_{𝑗} 𝑎_{𝑖}$ .

(b) By distributivity, the $𝑘$ -th coefficient of $(𝑝 𝑞) 𝑟$ is

\sum_{𝑚 + 𝑙 = 𝑘} (\sum_{𝑖 + 𝑗 = 𝑚} 𝑎_{𝑖} 𝑏_{𝑗}) 𝑑_{𝑙} = \sum_{𝑖 + 𝑗 + 𝑙 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} 𝑑_{𝑙},

since each triple $(𝑖, 𝑗, 𝑙)$ with $𝑖 + 𝑗 + 𝑙 = 𝑘$ occurs exactly once on the left, with $𝑚 = 𝑖 + 𝑗$ . In the same way, the $𝑘$ -th coefficient of $𝑝 (𝑞 𝑟)$ is $\sum_{𝑖 + 𝑚 = 𝑘} 𝑎_{𝑖} (\sum_{𝑗 + 𝑙 = 𝑚} 𝑏_{𝑗} 𝑑_{𝑙}) =$ $\sum_{𝑖 + 𝑗 + 𝑙 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} 𝑑_{𝑙}$ . By associativity in $𝐹$ , the two agree.

(c) The $𝑘$ -th coefficient of $𝑝 (𝑞 + 𝑟)$ is $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} (𝑏_{𝑗} + 𝑑_{𝑗}) =$ $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} +$ $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑑_{𝑗}$ , which is the $𝑘$ -th coefficient of $𝑝 𝑞 + 𝑝 𝑟$ .

(d) Since $1 = (1, 0, 0, \dots)$ , the only possibly nonzero term in the $𝑘$ -th coefficient of $1 𝑝$ is $1 \cdot 𝑎_{𝑘} = 𝑎_{𝑘}$ .

(e) $\sum_{𝑖 + 𝑗 = 𝑘} (𝑐 𝑎_{𝑖}) 𝑏_{𝑗} =$ $𝑐 \sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} =$ $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} (𝑐 𝑏_{𝑗})$ .

Finally, the axioms of a commutative ring that involve only addition (commutativity, associativity, a zero element, and negatives) hold because $𝐹 [𝑥]$ is a vector space (Proposition 1.2.14). Together with (a)–(d), this makes $𝐹 [𝑥]$ a commutative ring. □

By (c), (e), and $𝑥^{𝑖} 𝑥^{𝑗} = 𝑥^{𝑖 + 𝑗}$ , polynomials are multiplied by expanding and collecting terms:

(\sum_{𝑖} 𝑎_{𝑖} 𝑥^{𝑖}) (\sum_{𝑗} 𝑏_{𝑗} 𝑥^{𝑗}) = \sum_{𝑖, 𝑗} 𝑎_{𝑖} 𝑏_{𝑗} 𝑥^{𝑖 + 𝑗} .

From now on we compute with polynomials as in school. The identities of Section 1.1.2 that do not use multiplicative inverses, such as $𝟎 𝑝 = 𝟎$ , $(- 1) 𝑝 = - 𝑝$ , and the sign rules, have the same proofs in every commutative ring, so they hold in $𝐹 [𝑥]$ .

Intuition. In a product of two polynomials, the highest power of

𝑥

comes only from the two leading terms,

(𝑎 𝑥^{𝑚}) (𝑏 𝑥^{𝑛}) =

𝑎 𝑏 𝑥^{𝑚 + 𝑛}

. Every other pair of terms lands lower. Over a field

𝑎 𝑏 \neq 0

when

𝑎, 𝑏 \neq 0

, so nothing can cancel the top term. Over

ℤ / 4 ℤ

, where

2 \cdot 2 = 0

, the same definition would give

{(2 𝑥 + 1)}^{2} =

4 𝑥^{2} +

4 𝑥 +

1 =

1

, and the degree would drop.

Proposition 7.1.4 (Degree of a product). Let

𝑝, 𝑞 \in 𝐹 [𝑥]

be nonzero, with leading coefficients

𝑎

and

𝑏

. Then

𝑝 𝑞 \neq 𝟎

deg (𝑝 𝑞) =

deg 𝑝 +

deg 𝑞

, and the leading coefficient of

𝑝 𝑞

𝑎 𝑏

. With the conventions

- \infty +

𝑛 =

𝑛 +

(- \infty) =

- \infty +

(- \infty) =

- \infty

, the formula

deg (𝑝 𝑞) =

deg 𝑝 +

deg 𝑞

holds for all

𝑝, 𝑞 \in 𝐹 [𝑥]

Proof.routine

Uses. Definition 7.1.1 (Product of polynomials), Definition 1.2.16 (Degree), Proposition 1.1.17 (No zero divisors), Proposition 1.1.15 (Multiplying by zero)

Hint 1. Let

𝑚 = deg 𝑝

and

𝑛 = deg 𝑞

. Which pairs

(𝑖, 𝑗)

can give a nonzero term

𝑎_{𝑖} 𝑏_{𝑗}

Hint 2. Only pairs with

𝑖 \leq 𝑚

and

𝑗 \leq 𝑛

, so

𝑖 + 𝑗 \leq 𝑚 + 𝑛

. For

𝑘 = 𝑚 + 𝑛

only the pair

(𝑚, 𝑛)

survives.

Sketch. A term

𝑎_{𝑖} 𝑏_{𝑗}

is nonzero only if

𝑖 \leq 𝑚

and

𝑗 \leq 𝑛

. So the coefficients of

𝑝 𝑞

vanish beyond position

𝑚 + 𝑛

, and the coefficient of

𝑥^{𝑚 + 𝑛}

𝑎_{𝑚} 𝑏_{𝑛} = 𝑎 𝑏

, which is nonzero because

𝐹

has no zero divisors. If

𝑝

𝑞

𝟎

, every coefficient of

𝑝 𝑞

0

Write $𝑝 = (𝑎_{𝑖})$ and $𝑞 = (𝑏_{𝑗})$ , and let $𝑚 = deg 𝑝$ and $𝑛 = deg 𝑞$ , so that $𝑎 = 𝑎_{𝑚}$ and $𝑏 = 𝑏_{𝑛}$ . A term $𝑎_{𝑖} 𝑏_{𝑗}$ can be nonzero only if $𝑎_{𝑖} \neq 0$ and $𝑏_{𝑗} \neq 0$ , that is, only if $𝑖 \leq 𝑚$ and $𝑗 \leq 𝑛$ , and then $𝑖 + 𝑗 \leq 𝑚 + 𝑛$ . Hence the $𝑘$ -th coefficient of $𝑝 𝑞$ is $0$ for $𝑘 > 𝑚 + 𝑛$ , and for $𝑘 = 𝑚 + 𝑛$ the only pair that can contribute is $(𝑚, 𝑛)$ . So the coefficient of $𝑥^{𝑚 + 𝑛}$ in $𝑝 𝑞$ is $𝑎 𝑏$ , which is nonzero by Proposition 1.1.17. Therefore $𝑝 𝑞 \neq 𝟎$ , $deg (𝑝 𝑞) = 𝑚 + 𝑛$ , and $𝑎 𝑏$ is the leading coefficient of $𝑝 𝑞$ .

If $𝑝 = 𝟎$ or $𝑞 = 𝟎$ , every term $𝑎_{𝑖} 𝑏_{𝑗}$ has a factor $0$ , so $𝑝 𝑞 = 𝟎$ (Proposition 1.1.15), and both sides of the formula are $- \infty$ . □

Definition 7.1.5 (Monic polynomial). A nonzero polynomial is monic if its leading coefficient is

1

For example, $𝑥^{2} - 3 𝑥 + 2$ and every product $(𝑥 - 𝑐_{1}) (𝑥 - 𝑐_{2}) \dots (𝑥 - 𝑐_{𝑛})$ are monic, by Proposition 7.1.4, while $2 𝑥 + 1$ is not. Every nonzero $𝑝$ is $𝑎$ times a monic polynomial for exactly one $𝑎 \in 𝐹$ , namely its leading coefficient $𝑎$ : indeed $𝑝 = 𝑎 (𝑎^{- 1} 𝑝)$ , and $𝑐 𝑢$ has leading coefficient $𝑐$ when $𝑢$ is monic.

The proposition gives an argument that recurs throughout the book.

Technique 7.1.6 (Compare degrees and leading coefficients). To show that a polynomial is zero, or that an identity between polynomials cannot hold, compare the degrees of the two sides, and when the degrees agree, their leading coefficients. Over a field the degree of a product is the sum of the degrees (Proposition 7.1.4), and a sum has degree at most the larger of the two degrees, with equality when they differ (Proposition 1.2.18). The typical use: if $𝑠 𝑔 = ℎ$ with $𝑠 \neq 𝟎$ and $deg ℎ < deg 𝑠$ , then $𝑔 = 𝟎$ , because a nonzero multiple of $𝑠$ has degree at least $deg 𝑠$ .

Reach for it in uniqueness statements about polynomials (quotients and remainders, greatest common divisors, and later minimal polynomials), and to show that a polynomial is constant or zero. Leading coefficients settle what degrees alone cannot, for instance that two monic polynomials that divide each other are equal. The canonical example is the uniqueness half of Theorem 7.1.14. Proposition 1.5.24 was an earlier instance.

Used in 8 places

Corollary 7.1.7, Theorem 7.1.14, Theorem 7.1.45, Exercise 7.1.55, Exercise 7.1.65, Exercise 7.1.69, Theorem 7.6.2, Problem 7.12.

Corollary 7.1.7 (No zero divisors, cancellation, and units). Let $𝑝, 𝑞, 𝑟 \in 𝐹 [𝑥]$ .

(a)If $𝑝 𝑞 = 𝟎$ , then $𝑝 = 𝟎$ or $𝑞 = 𝟎$ .
(b)If $𝑝 \neq 𝟎$ and $𝑝 𝑞 = 𝑝 𝑟$ , then $𝑞 = 𝑟$ .
(c) $𝑝$ has a multiplicative inverse in $𝐹 [𝑥]$ if and only if $𝑝$ is a nonzero constant.

Proof.routine

Uses. Proposition 7.1.4 (Degree of a product), Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring)

Techniques. Compare degrees and leading coefficients (Technique 7.1.6)

Hint 1. (a) is a restatement of part of Proposition 7.1.4. For (b), move everything to one side.

Hint 2. For (c), if

𝑝 𝑞 = 1

, take degrees of both sides.

Sketch. (a) A product of nonzero polynomials is nonzero. (b)

𝑝 (𝑞 - 𝑟) = 𝟎

with

𝑝 \neq 𝟎

forces

𝑞 - 𝑟 = 𝟎

. (c) If

𝑝 𝑞 = 1

, then

deg 𝑝 + deg 𝑞 = 0

with both degrees nonnegative, so

deg 𝑝 = 0

; nonzero constants

𝑐

have the inverse

𝑐^{- 1}

(a) If $𝑝$ and $𝑞$ are both nonzero, then $𝑝 𝑞 \neq 𝟎$ by Proposition 7.1.4.

(b) By Proposition 7.1.3, $𝑝 (𝑞 - 𝑟) =$ $𝑝 𝑞 -$ $𝑝 𝑟 =$ $𝟎$ . Since $𝑝 \neq 𝟎$ , (a) gives $𝑞 - 𝑟 = 𝟎$ , that is, $𝑞 = 𝑟$ .

(c) A nonzero constant $𝑐$ has the inverse $𝑐^{- 1}$ , since $𝑐 \cdot 𝑐^{- 1} = 1$ . Conversely, suppose $𝑝 𝑞 = 1$ . Then $𝑝$ and $𝑞$ are nonzero, and $deg 𝑝 +$ $deg 𝑞 =$ $deg 1 =$ $0$ by Proposition 7.1.4. Both degrees are nonnegative integers, so $deg 𝑝 = 0$ , and $𝑝$ is a nonzero constant. □

So $𝐹 [𝑥]$ shares two features with the integers: a product of nonzero elements is nonzero, and few elements are invertible (in $ℤ$ , only $\pm 1$ ). In particular $𝑥$ has no inverse, and $𝐹 [𝑥]$ is not a field. The analogy with $ℤ$ continues in Section 7.1.2 with division with remainder.

Exercise 7.1.8.routine

(a)Over $ℚ$ , compute $(𝑥^{2} - 𝑥 + 1) (𝑥^{2} + 𝑥 + 1)$ and, for $𝑛 \geq 1$ , $(1 - 𝑥) (1 + 𝑥 + 𝑥^{2} + \dots + 𝑥^{𝑛 - 1})$ .
(b)Over $𝔽_{2}$ , compute ${(1 + 𝑥 + 𝑥^{2})}^{2}$ . Over $𝔽_{3}$ , compute ${(1 + 𝑥)}^{3}$ .

Solution.

Uses. Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring), Definition 7.1.1 (Product of polynomials)

Hint 1. For the first product in (a), write the factors as

(𝑥^{2} + 1) - 𝑥

and

(𝑥^{2} + 1) + 𝑥

. In the second, most terms cancel in pairs.

Hint 2. For (b), expand as over

ℤ

, then reduce the coefficients modulo

2

3

Sketch. (a)

{(𝑥^{2} + 1)}^{2} -

𝑥^{2} =

𝑥^{4} +

𝑥^{2} +

1

, and the second product telescopes to

1 - 𝑥^{𝑛}

. (b)

{(1 + 𝑥 + 𝑥^{2})}^{2} =

1 +

2 𝑥 +

3 𝑥^{2} +

2 𝑥^{3} +

𝑥^{4}

, which is

1 + 𝑥^{2} + 𝑥^{4}

over

𝔽_{2}

;

{(1 + 𝑥)}^{3} =

1 +

3 𝑥 +

3 𝑥^{2} +

𝑥^{3}

, which is

1 + 𝑥^{3}

over

𝔽_{3}

(a) Since $𝐹 [𝑥]$ is a commutative ring, $(𝑢 - 𝑣) (𝑢 + 𝑣) =$ $𝑢^{2} -$ $𝑣^{2}$ . With $𝑢 = 𝑥^{2} + 1$ and $𝑣 = 𝑥$ ,

\begin{aligned} (𝑥^{2} - 𝑥 + 1) (𝑥^{2} + 𝑥 + 1) & = {(𝑥^{2} + 1)}^{2} - 𝑥^{2} \\ = 𝑥^{4} + 𝑥^{2} + 1 . \end{aligned}

For the second product,

(1 - 𝑥) \sum_{𝑘 = 0}^{𝑛 - 1} 𝑥^{𝑘} = \sum_{𝑘 = 0}^{𝑛 - 1} 𝑥^{𝑘} - \sum_{𝑘 = 0}^{𝑛 - 1} 𝑥^{𝑘 + 1} = 1 - 𝑥^{𝑛},

since every $𝑥^{𝑘}$ with $1 \leq 𝑘 \leq 𝑛 - 1$ occurs once in each sum and cancels.

(b) Expanding, ${(1 + 𝑥 + 𝑥^{2})}^{2} =$ $1 +$ $2 𝑥 +$ $3 𝑥^{2} +$ $2 𝑥^{3} +$ $𝑥^{4}$ . In $𝔽_{2}$ , $2 = 0$ and $3 = 1$ , so the square is $1 + 𝑥^{2} + 𝑥^{4}$ . Similarly ${(1 + 𝑥)}^{3} =$ $1 +$ $3 𝑥 +$ $3 𝑥^{2} +$ $𝑥^{3}$ , and in $𝔽_{3}$ this is $1 + 𝑥^{3}$ .

Evaluation and substitution

Evaluating a polynomial at a scalar (Definition 1.2.17) uses only that scalars can be added, multiplied, and raised to powers. The same formula makes sense with a polynomial in place of the scalar.

Definition 7.1.9 (Substitution). Let $𝑝 =$ $\sum_{𝑘 = 0}^{𝑑} 𝑎_{𝑘} 𝑥^{𝑘} \in$ $𝐹 [𝑥]$ and $𝑟 \in 𝐹 [𝑥]$ . The polynomial obtained by substituting $𝑟$ into $𝑝$ is

𝑝 (𝑟) = \sum_{𝑘 = 0}^{𝑑} 𝑎_{𝑘} 𝑟^{𝑘} \in 𝐹 [𝑥],

where $𝑟^{0} = 1$ and $𝑟^{𝑘}$ is the product of $𝑘$ copies of $𝑟$ .

For instance $𝑝 (𝑥) = 𝑝$ , since $𝑥^{𝑘}$ is the $𝑘$ -th power of $𝑥$ , and if $𝑝 = 𝑥^{2} - 3$ , then $𝑝 (𝑥 + 1) =$ ${(𝑥 + 1)}^{2} -$ $3 =$ $𝑥^{2} +$ $2 𝑥 -$ $2$ . If $𝑟 = 𝑐$ is a constant, then $𝑝 (𝑐)$ is the constant polynomial whose value is the scalar $𝑝 (𝑐)$ of Definition 1.2.17, so the two notations agree.

Proposition 7.1.10 (Evaluation respects sums and products). Let $𝑝, 𝑞 \in 𝐹 [𝑥]$ and $𝑐 \in 𝐹$ , and let $𝑡$ be either a scalar in $𝐹$ or a polynomial in $𝐹 [𝑥]$ . Then

\begin{matrix} (𝑝 + 𝑞) (𝑡) = 𝑝 (𝑡) + 𝑞 (𝑡), (𝑐 𝑝) (𝑡) = 𝑐 𝑝 (𝑡), \\ (𝑝 𝑞) (𝑡) = 𝑝 (𝑡) 𝑞 (𝑡) . \end{matrix}

Proof.routine

Uses. Definition 1.2.17 (Evaluation), Definition 7.1.9 (Substitution), Definition 7.1.1 (Product of polynomials), Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring), Proposition 1.2.18 (Degree and evaluation versus the operations)

Hint 1. Write

𝑝 = \sum_{𝑖} 𝑎_{𝑖} 𝑥^{𝑖}

and

𝑞 = \sum_{𝑗} 𝑏_{𝑗} 𝑥^{𝑗}

, and substitute

𝑡

into the formula for the coefficients of

𝑝 𝑞

Hint 2. Regroup the double sum

\sum_{𝑘} \sum_{𝑖 + 𝑗 = 𝑘}

as a sum over all pairs

(𝑖, 𝑗)

, and use

𝑡^{𝑖 + 𝑗} = 𝑡^{𝑖} 𝑡^{𝑗}

Sketch. The first two identities are the computation of Proposition 1.2.18(c). For the product,

(𝑝 𝑞) (𝑡) =

\sum_{𝑘} (\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}) 𝑡^{𝑘} =

\sum_{𝑖, 𝑗} (𝑎_{𝑖} 𝑡^{𝑖}) (𝑏_{𝑗} 𝑡^{𝑗}) =

𝑝 (𝑡) 𝑞 (𝑡)

, by distributivity,

𝑡^{𝑖 + 𝑗} = 𝑡^{𝑖} 𝑡^{𝑗}

, and commutativity, all of which hold in

𝐹

and in the commutative ring

𝐹 [𝑥]

In both cases $𝑡$ lies in a commutative ring, $𝐹$ or $𝐹 [𝑥]$ (Proposition 7.1.3), in which scalars multiply as in $𝐹$ (for $𝐹 [𝑥]$ this is Proposition 7.1.3(e)) and $𝑡^{𝑖} 𝑡^{𝑗} = 𝑡^{𝑖 + 𝑗}$ . These are the only facts we use.

Choose $𝑑$ with $𝑝 =$ $\sum_{𝑖 = 0}^{𝑑} 𝑎_{𝑖} 𝑥^{𝑖}$ and $𝑞 =$ $\sum_{𝑗 = 0}^{𝑑} 𝑏_{𝑗} 𝑥^{𝑗}$ , and put $𝑎_{𝑖} = 𝑏_{𝑖} = 0$ for $𝑖 > 𝑑$ . Then $𝑝 +$ $𝑞 =$ $\sum_{𝑖} (𝑎_{𝑖} + 𝑏_{𝑖}) 𝑥^{𝑖}$ and $𝑐 𝑝 =$ $\sum_{𝑖} (𝑐 𝑎_{𝑖}) 𝑥^{𝑖}$ , and distributivity gives $(𝑝 + 𝑞) (𝑡) =$ $𝑝 (𝑡) +$ $𝑞 (𝑡)$ and $(𝑐 𝑝) (𝑡) =$ $𝑐 𝑝 (𝑡)$ , as in Proposition 1.2.18(c). For the product, $𝑝 𝑞 =$ $\sum_{𝑘 = 0}^{2 𝑑} (\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}) 𝑥^{𝑘}$ , so

\begin{aligned} (𝑝 𝑞) (𝑡) & = \sum_{𝑘 = 0}^{2 𝑑} \sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} 𝑡^{𝑘} = \sum_{𝑖 = 0}^{𝑑} \sum_{𝑗 = 0}^{𝑑} (𝑎_{𝑖} 𝑡^{𝑖}) (𝑏_{𝑗} 𝑡^{𝑗}) \\ = (\sum_{𝑖 = 0}^{𝑑} 𝑎_{𝑖} 𝑡^{𝑖}) (\sum_{𝑗 = 0}^{𝑑} 𝑏_{𝑗} 𝑡^{𝑗}) = 𝑝 (𝑡) 𝑞 (𝑡) . \end{aligned}

The second equality regroups the terms by pairs $(𝑖, 𝑗)$ instead of by $𝑘 = 𝑖 + 𝑗$ (the pairs with $𝑖 > 𝑑$ or $𝑗 > 𝑑$ contribute $0$ ) and uses $𝑡^{𝑖 + 𝑗} = 𝑡^{𝑖} 𝑡^{𝑗}$ and commutativity. The third is distributivity. □

Remark 7.1.11 (Polynomials in a matrix). For $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ and $𝑝 =$ $\sum_{𝑘 = 0}^{𝑑} 𝑎_{𝑘} 𝑥^{𝑘}$ , write $𝑝 (𝐴) =$ $𝑎_{0} 𝐼_{𝑛} +$ $𝑎_{1} 𝐴 +$ $\dots +$ $𝑎_{𝑑} 𝐴^{𝑑}$ , as in Proposition 4.1.31. The proof above used only that powers of $𝑡$ satisfy $𝑡^{𝑖} 𝑡^{𝑗} = 𝑡^{𝑖 + 𝑗}$ , that products distribute over sums, and that scalars commute with powers of $𝑡$ . It never multiplied $𝑡$ by anything except its own powers and scalars. All of this holds for $𝐴$ (Notation 2.4.16, Proposition 2.4.14), so

\begin{matrix} (𝑝 + 𝑞) (𝐴) = 𝑝 (𝐴) + 𝑞 (𝐴), (𝑐 𝑝) (𝐴) = 𝑐 𝑝 (𝐴), \\ (𝑝 𝑞) (𝐴) = 𝑝 (𝐴) 𝑞 (𝐴), \end{matrix}

even though matrix multiplication is not commutative. In particular $𝑝 (𝐴) 𝑞 (𝐴) =$ $(𝑝 𝑞) (𝐴) =$ $(𝑞 𝑝) (𝐴) =$ $𝑞 (𝐴) 𝑝 (𝐴)$ : any two polynomials in the same matrix commute. Section 7.2 evaluates polynomials at operators in the same way.

Corollary 7.1.12 (Substituting twice). Let

𝑝, 𝑟 \in 𝐹 [𝑥]

, and let

𝑡

be a scalar in

𝐹

or a polynomial in

𝐹 [𝑥]

. Then

(𝑝 (𝑟)) (𝑡) =

𝑝 (𝑟 (𝑡))

Proof.routine

Uses. Proposition 7.1.10 (Evaluation respects sums and products), Definition 7.1.9 (Substitution), induction on $𝑘$

Techniques. Check it on a basis (Technique 2.2.7)

Hint 1. Both sides respect sums and scalar multiples in

𝑝

. So it is enough to check the identity for

𝑝 = 𝑥^{𝑘}

Hint 2. For

𝑝 = 𝑥^{𝑘}

the left side is

(𝑟^{𝑘}) (𝑡)

. Apply the product rule of Proposition 7.1.10

𝑘

times.

Sketch. By Proposition 7.1.10,

𝑝 \mapsto (𝑝 (𝑟)) (𝑡)

and

𝑝 \mapsto 𝑝 (𝑟 (𝑡))

both respect sums and scalar multiples, and every polynomial is a finite combination of the

𝑥^{𝑘}

. For

𝑝 = 𝑥^{𝑘}

(𝑟^{𝑘}) (𝑡) =

{𝑟 (𝑡)}^{𝑘}

by Proposition 7.1.10 and induction on

𝑘

, and this is

𝑥^{𝑘} (𝑟 (𝑡))

Let $𝑠 = 𝑟 (𝑡)$ . By Proposition 7.1.10, applied first with $𝑟$ and then with $𝑡$ , the map $𝑝 \mapsto (𝑝 (𝑟)) (𝑡)$ respects sums and scalar multiples, and so does $𝑝 \mapsto 𝑝 (𝑠)$ . Every polynomial is a finite linear combination of $1, 𝑥, 𝑥^{2}, \dots$ , so it suffices to prove the identity for $𝑝 = 𝑥^{𝑘}$ , $𝑘 \geq 0$ .

For $𝑝 = 𝑥^{𝑘}$ we have $𝑥^{𝑘} (𝑟) = 𝑟^{𝑘}$ and $𝑥^{𝑘} (𝑠) = 𝑠^{𝑘}$ , so we must show $(𝑟^{𝑘}) (𝑡) = 𝑠^{𝑘}$ . For $𝑘 = 0$ both sides are $1$ . If $(𝑟^{𝑘}) (𝑡) = 𝑠^{𝑘}$ , then by Proposition 7.1.10, $(𝑟^{𝑘 + 1}) (𝑡) =$ $(𝑟^{𝑘} 𝑟) (𝑡) =$ $(𝑟^{𝑘}) (𝑡) 𝑟 (𝑡) =$ $𝑠^{𝑘} 𝑠 =$ $𝑠^{𝑘 + 1}$ . □

For example, substituting $𝑥 + 1$ into $𝑝 (𝑥 + 1)$ gives $𝑝 ((𝑥 + 1) + 1) =$ $𝑝 (𝑥 + 2)$ : take $𝑟 = 𝑡 = 𝑥 + 1$ . This is the fact used in Exercise 2.3.48.

7.1.2Division with remainder

For integers $𝑎$ and $𝑏 > 0$ there are integers $𝑞$ and $𝑟$ with $𝑎 = 𝑏 𝑞 + 𝑟$ and $0 \leq 𝑟 < 𝑏$ . Polynomials can be divided the same way, with the degree in place of size. Long division, familiar from school, computes the quotient: at each step, subtract a multiple of the divisor that cancels the leading term of what is left.

Example 7.1.13 (Long division). Over $ℚ$ , divide $𝑝 =$ $2 𝑥^{4} -$ $𝑥^{3} +$ $3 𝑥^{2} +$ $𝑥 -$ $1$ by $𝑠 = 2 𝑥^{2} + 1$ . The leading term $2 𝑥^{4}$ of $𝑝$ is $𝑥^{2}$ times the leading term $2 𝑥^{2}$ of $𝑠$ , so we subtract $𝑥^{2} 𝑠$ . The leading term of what is left is $- 𝑥^{3} = (- \frac{1}{2} 𝑥) \cdot 2 𝑥^{2}$ , so we subtract $- \frac{1}{2} 𝑥 𝑠$ , and so on:

\begin{aligned} 𝑝 - 𝑥^{2} 𝑠 & = - 𝑥^{3} + 2 𝑥^{2} + 𝑥 - 1, \\ 𝑝 - (𝑥^{2} - \frac{1}{2} 𝑥) 𝑠 & = 2 𝑥^{2} + \frac{3}{2} 𝑥 - 1, \\ 𝑝 - (𝑥^{2} - \frac{1}{2} 𝑥 + 1) 𝑠 & = \frac{3}{2} 𝑥 - 2 . \end{aligned}

The last line has degree $1 < 2 = deg 𝑠$ , so we stop. With $𝑞 = 𝑥^{2} - \frac{1}{2} 𝑥 + 1$ and $𝑟 = \frac{3}{2} 𝑥 - 2$ ,

𝑝 = (2 𝑥^{2} + 1) (𝑥^{2} - \frac{1}{2} 𝑥 + 1) + (\frac{3}{2} 𝑥 - 2) .

The coefficient $- \frac{1}{2}$ appeared because we divided by the leading coefficient $2$ of $𝑠$ . Over $ℤ$ this step would be impossible: dividing by the leading coefficient of the divisor is the one place where long division needs a field. Over $𝔽_{3}$ , where $2^{- 1} = 2$ , the same steps give $𝑞 = 𝑥^{2} + 𝑥 + 1$ and $𝑟 = 1$ .

Theorem 7.1.14 (Division with remainder). Let $𝑝, 𝑠 \in 𝐹 [𝑥]$ with $𝑠 \neq 𝟎$ . There are unique polynomials $𝑞, 𝑟 \in 𝐹 [𝑥]$ such that

𝑝 = 𝑠 𝑞 + 𝑟 and deg 𝑟 < deg 𝑠 .

We call $𝑞$ the quotient and $𝑟$ the remainder of $𝑝$ on division by $𝑠$ .

The theorem is often called the division algorithm, after the procedure that proves it. If $deg 𝑠 = 0$ , the condition $deg 𝑟 < 0$ means $𝑟 = 𝟎$ : division by a nonzero constant $𝑏$ is exact, with $𝑞 = 𝑏^{- 1} 𝑝$ .

Intuition. Uniqueness is a degree count. Two divisions

𝑝 =

𝑠 𝑞 +

𝑟 =

𝑠 𝑞^{'} +

𝑟^{'}

give

𝑠 (𝑞 - 𝑞^{'}) = 𝑟^{'} - 𝑟

. The right side has degree less than

deg 𝑠

, and a nonzero multiple of

𝑠

cannot, so

𝑞 = 𝑞^{'}

. For existence, one step of long division replaces

𝑝

by a polynomial of smaller degree, which suggests strong induction on

deg 𝑝

. A second proof avoids division altogether and counts dimensions instead.

Proof (by induction on the degree).standard

Uses. Proposition 7.1.4 (Degree of a product), Proposition 1.2.18 (Degree and evaluation versus the operations), Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring), Definition 1.2.16 (Degree)

Techniques. Compare degrees and leading coefficients (Technique 7.1.6), Uniqueness via two candidates (Technique 1.1.8), Strong induction and well-ordering (Technique 5.2.12)

Hint 1. Prove uniqueness and existence separately. For uniqueness, subtract two divisions

𝑝 =

𝑠 𝑞 +

𝑟 =

𝑠 𝑞^{'} +

𝑟^{'}

and compare degrees.

Hint 2. For existence, use strong induction on

deg 𝑝

. If

deg 𝑝 < deg 𝑠

there is nothing to do. Otherwise subtract from

𝑝

a multiple of

𝑠

that cancels its leading term.

Hint 3. With

𝑎

and

𝑏

the leading coefficients of

𝑝

and

𝑠

, the polynomial

𝑝 -

(𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚} 𝑠

has degree less than

𝑛 = deg 𝑝

. Divide it by the induction hypothesis, and add

(𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚}

to the quotient.

Sketch. If

𝑠 𝑞 + 𝑟 = 𝑠 𝑞^{'} + 𝑟^{'}

, then

𝑠 (𝑞 - 𝑞^{'}) = 𝑟^{'} - 𝑟

has degree less than

deg 𝑠

, which forces

𝑞 = 𝑞^{'}

, and then

𝑟 = 𝑟^{'}

. For existence, induct on

𝑛 = deg 𝑝

. If

𝑛 < 𝑚 = deg 𝑠

, take

𝑞 = 𝟎

and

𝑟 = 𝑝

. Otherwise the leading terms of

𝑝

and

(𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚} 𝑠

agree, so

𝑝_{1} =

𝑝 -

(𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚} 𝑠

has degree less than

𝑛

. If

𝑝_{1} = 𝑠 𝑞_{1} + 𝑟_{1}

, then

𝑝 =

𝑠 (𝑞_{1} + (𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚}) +

𝑟_{1}

Let $𝑚 = deg 𝑠$ , which is a nonnegative integer, and let $𝑏 \neq 0$ be the leading coefficient of $𝑠$ .

Uniqueness. Suppose $𝑝 =$ $𝑠 𝑞 +$ $𝑟 =$ $𝑠 𝑞^{'} +$ $𝑟^{'}$ with $deg 𝑟 < 𝑚$ and $deg 𝑟^{'} < 𝑚$ . By Proposition 7.1.3, $𝑠 (𝑞 - 𝑞^{'}) = 𝑟^{'} - 𝑟$ , and $deg (𝑟^{'} - 𝑟) < 𝑚$ by Proposition 1.2.18(a) and (b). If $𝑞 \neq 𝑞^{'}$ , then by Proposition 7.1.4

deg (𝑠 (𝑞 - 𝑞^{'})) = 𝑚 + deg (𝑞 - 𝑞^{'}) \geq 𝑚,

which is impossible. So $𝑞 = 𝑞^{'}$ , and then $𝑟^{'} - 𝑟 = 𝑠 \cdot 𝟎 = 𝟎$ , so $𝑟 = 𝑟^{'}$ .

Existence. If $𝑝 = 𝟎$ , take $𝑞 = 𝑟 = 𝟎$ . For nonzero $𝑝$ we use strong induction on $𝑛 = deg 𝑝$ : let $𝑛 \geq 0$ , and assume that every polynomial of degree less than $𝑛$ (including $𝟎$ ) has a quotient and remainder on division by $𝑠$ . Let $deg 𝑝 = 𝑛$ , with leading coefficient $𝑎$ .

If $𝑛 < 𝑚$ , take $𝑞 = 𝟎$ and $𝑟 = 𝑝$ . Suppose $𝑛 \geq 𝑚$ . By Proposition 7.1.4, the polynomial $(𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚} 𝑠$ has degree $(𝑛 - 𝑚) + 𝑚 = 𝑛$ and leading coefficient $(𝑎 / 𝑏) 𝑏 = 𝑎$ . So in

𝑝_{1} = 𝑝 - (𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚} 𝑠,

the coefficient of $𝑥^{𝑛}$ is $𝑎 - 𝑎 = 0$ , and all coefficients beyond $𝑥^{𝑛}$ are $0$ . Hence $deg 𝑝_{1} < 𝑛$ , and by the induction hypothesis $𝑝_{1} = 𝑠 𝑞_{1} + 𝑟_{1}$ for some $𝑞_{1}, 𝑟_{1}$ with $deg 𝑟_{1} < 𝑚$ . Then

𝑝 = 𝑝_{1} + (𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚} 𝑠 = 𝑠 (𝑞_{1} + (𝑎 / 𝑏) 𝑥^{𝑛 - 𝑚}) + 𝑟_{1},

as desired. □

Unwound, the induction is long division. The equation $𝑝 = 𝑠 𝑞 + 𝑟$ is an invariant, and $deg 𝑟$ is a quantity that drops at every step, so this is an instance of Technique 3.3.5.

Algorithm 7.1.15 (Long division)

Input: Polynomials $𝑝, 𝑠 \in 𝐹 [𝑥]$ with $𝑠 \neq 𝟎$ . Let $𝑚 = deg 𝑠$ and let $𝑏$ be the leading coefficient of $𝑠$ .
Output: The quotient $𝑞$ and the remainder $𝑟$ of $𝑝$ on division by $𝑠$ .

Set

𝑞 = 𝟎

and

𝑟 = 𝑝

deg 𝑟 < 𝑚

, output

𝑞

and

𝑟

and stop.

Otherwise, let

𝑑 = deg 𝑟

and let

𝑐

be the leading coefficient of

𝑟

. Replace

𝑞

𝑞 + (𝑐 / 𝑏) 𝑥^{𝑑 - 𝑚}

and

𝑟

𝑟 -

(𝑐 / 𝑏) 𝑥^{𝑑 - 𝑚} 𝑠

, and return to step 2.

At the start $𝑝 = 𝑠 𝑞 + 𝑟$ , and step 3 adds $(𝑐 / 𝑏) 𝑥^{𝑑 - 𝑚} 𝑠$ to $𝑠 𝑞$ and subtracts it from $𝑟$ , so $𝑝 = 𝑠 𝑞 + 𝑟$ remains true. The same step lowers $deg 𝑟$ , as in the proof. So the algorithm stops after at most $deg 𝑝 - 𝑚 + 1$ steps, and then $deg 𝑟 < 𝑚$ .

The second proof is the one in LADR. It proves existence without constructing anything.

Proof of Theorem 7.1.14 (by linear algebra).standard

Uses. Proposition 1.5.24 (Distinct degrees), Example 4.1.7 (Dimensions of the standard spaces), Theorem 4.1.10 (Independent lists are short), Proposition 7.1.4 (Degree of a product), Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring)

Techniques. Uniqueness gives existence (Technique 3.4.21), Dimension counting (Technique 4.2.24)

Hint 1. Uniqueness is the degree count from the first proof. For existence, let

𝑛 = deg 𝑝 \geq 𝑚 = deg 𝑠

and work in

{𝐹 [𝑥]}_{\leq 𝑛}

. Which polynomials have the form

𝑠 𝑞 + 𝑟

with

deg 𝑞 \leq 𝑛 - 𝑚

and

deg 𝑟 < 𝑚

Hint 2. They are the linear combinations of

1,

𝑥,

\dots,

𝑥^{𝑚 - 1},

𝑠,

𝑥 𝑠,

\dots,

𝑥^{𝑛 - 𝑚} 𝑠

. Show that this list is a basis of

{𝐹 [𝑥]}_{\leq 𝑛}

Hint 3. The list consists of

𝑛 + 1

nonzero polynomials with the distinct degrees

0, 1, \dots, 𝑛

Sketch. Let

𝑛 = deg 𝑝 \geq 𝑚

(otherwise take

𝑞 = 𝟎

𝑟 = 𝑝

). The

𝑛 + 1

polynomials

1,

𝑥,

\dots,

𝑥^{𝑚 - 1},

𝑠,

𝑥 𝑠,

\dots,

𝑥^{𝑛 - 𝑚} 𝑠

have the distinct degrees

0, \dots, 𝑛

, so they are independent, and since

dim {𝐹 [𝑥]}_{\leq 𝑛} = 𝑛 + 1

, they form a basis. Expanding

𝑝

in this basis writes it as

𝑟 + 𝑠 𝑞

, with

𝑟

a combination of

1, \dots, 𝑥^{𝑚 - 1}

and

𝑞

a combination of

1, \dots, 𝑥^{𝑛 - 𝑚}

. Uniqueness is as in the first proof.

Uniqueness was proved in the first proof without induction, so we prove existence. Let $𝑚 = deg 𝑠$ . If $𝑝 = 𝟎$ or $deg 𝑝 < 𝑚$ , take $𝑞 = 𝟎$ and $𝑟 = 𝑝$ . So let $𝑛 = deg 𝑝 \geq 𝑚$ , and consider the list

ℬ︀ = 1, 𝑥, \dots, 𝑥^{𝑚 - 1}, 𝑠, 𝑥 𝑠, \dots, 𝑥^{𝑛 - 𝑚} 𝑠

in ${𝐹 [𝑥]}_{\leq 𝑛}$ . By Proposition 7.1.4, $deg (𝑥^{𝑗} 𝑠) = 𝑗 + 𝑚$ , so the $𝑛 + 1$ polynomials in $ℬ︀$ are nonzero with degrees $0,$ $1,$ $\dots,$ $𝑚 -$ $1,$ $𝑚,$ $𝑚 +$ $1,$ $\dots,$ $𝑛$ , which are distinct. By Proposition 1.5.24, $ℬ︀$ is linearly independent. Its length $𝑛 + 1$ equals $dim {𝐹 [𝑥]}_{\leq 𝑛}$ (Example 4.1.7), so $ℬ︀$ is a basis of ${𝐹 [𝑥]}_{\leq 𝑛}$ by Theorem 4.1.10(b). Hence there are scalars with

\begin{matrix} 𝑝 = 𝑎_{0} + 𝑎_{1} 𝑥 + \dots + 𝑎_{𝑚 - 1} 𝑥^{𝑚 - 1} \\ + 𝑏_{0} 𝑠 + 𝑏_{1} 𝑥 𝑠 + \dots + 𝑏_{𝑛 - 𝑚} 𝑥^{𝑛 - 𝑚} 𝑠 . \end{matrix}

Let $𝑟 =$ $\sum_{𝑖 = 0}^{𝑚 - 1} 𝑎_{𝑖} 𝑥^{𝑖}$ and $𝑞 =$ $\sum_{𝑗 = 0}^{𝑛 - 𝑚} 𝑏_{𝑗} 𝑥^{𝑗}$ . By Proposition 7.1.3, $𝑝 = 𝑠 𝑞 + 𝑟$ , and $deg 𝑟 \leq 𝑚 - 1 < 𝑚$ . □

Intuition (Two proofs compared). The first proof constructs

𝑞

and

𝑟

and unwinds into long division, so it is the one to use for computing. The second never divides. Independence of the list

ℬ︀

is the uniqueness statement for

𝑝 = 𝟎

, and a dimension count upgrades it to spanning, which is existence. This is Technique 3.4.21, which proved polynomial interpolation in Section 3.4.5. In the language of Section 4.2, the map

𝐹^{𝑛 + 1} \to {𝐹 [𝑥]}_{\leq 𝑛}

sending a list of coefficients to the corresponding combination of

ℬ︀

is an injective linear map between spaces of the same dimension, hence bijective (Corollary 4.2.18). The count works because the conditions

deg 𝑞 \leq 𝑛 - 𝑚

and

deg 𝑟 \leq 𝑚 - 1

leave exactly

(𝑛 - 𝑚 + 1) + 𝑚 = 𝑛 + 1

unknown coefficients, one for each coefficient of

𝑝

Definition 7.1.16 (Divisibility). Let

𝑝, 𝑠 \in 𝐹 [𝑥]

. We say that

𝑠

divides

𝑝

, and write

𝑠 ∣ 𝑝

, if

𝑝 = 𝑠 𝑞

for some

𝑞 \in 𝐹 [𝑥]

. Then

𝑠

is a factor (or divisor) of

𝑝

, and

𝑝

is a multiple of

𝑠

If $𝑠 \neq 𝟎$ , then $𝑠 ∣ 𝑝$ exactly when the remainder of $𝑝$ on division by $𝑠$ is $𝟎$ , by the uniqueness in Theorem 7.1.14. Some consequences of the definition and of Proposition 7.1.4:

every $𝑠$ divides $𝟎$ , and $𝟎$ divides only $𝟎$ ;
a nonzero constant $𝑐$ divides every $𝑝$ , since $𝑝 = 𝑐 (𝑐^{- 1} 𝑝)$ ;
if $𝑠 ∣ 𝑝$ and $𝑝 \neq 𝟎$ , then $deg 𝑠 \leq deg 𝑝$ ;
if $𝑠 ∣ 𝑝$ and $𝑝 ∣ 𝑠$ with $𝑝, 𝑠 \neq 𝟎$ , then $𝑝 = 𝑐 𝑠$ for a nonzero constant $𝑐$ . (If $𝑝 = 𝑠 𝑔$ and $𝑠 = 𝑝 ℎ$ , then $𝑠 = 𝑠 𝑔 ℎ$ , so $𝑔 ℎ = 1$ by Corollary 7.1.7(b), and $𝑔$ is a nonzero constant by Corollary 7.1.7(c).) In particular, two monic polynomials that divide each other are equal.

For example, $𝑥 + 1 ∣ 𝑥^{3} + 1$ over every field, since $𝑥^{3} +$ $1 =$ $(𝑥 + 1) (𝑥^{2} - 𝑥 + 1)$ .

The quotient and remainder do not depend on the field in which we compute them. This is useful when a polynomial with real coefficients is factored over $ℂ$ .

Corollary 7.1.17 (Division does not depend on the field). Let

𝐹

be a subfield of a field

𝐾

(Definition 1.1.32), and let

𝑝, 𝑠 \in 𝐹 [𝑥]

with

𝑠 \neq 𝟎

. The quotient and remainder of

𝑝

on division by

𝑠

𝐾 [𝑥]

are the quotient and remainder in

𝐹 [𝑥]

. In particular,

𝑠

divides

𝑝

𝐾 [𝑥]

if and only if

𝑠

divides

𝑝

𝐹 [𝑥]

Proof.routine

Uses. Definition 1.1.32 (Subfield), Theorem 7.1.14 (Division with remainder), Definition 7.1.1 (Product of polynomials)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Divide in

𝐹 [𝑥]

first. Does the result still satisfy the conditions of Theorem 7.1.14 when it is read in

𝐾 [𝑥]

Hint 2. Use the uniqueness half of Theorem 7.1.14 over

𝐾

Sketch.

𝐹 [𝑥] \subseteq 𝐾 [𝑥]

, and sums, products, and degrees of polynomials with coefficients in

𝐹

are the same whether computed in

𝐹

or in

𝐾

. So the quotient and remainder over

𝐹

also satisfy

𝑝 = 𝑠 𝑞 + 𝑟

and

deg 𝑟 < deg 𝑠

𝐾 [𝑥]

, and by uniqueness over

𝐾

they are the quotient and remainder there.

A polynomial with coefficients in $𝐹$ is also one with coefficients in $𝐾$ , so $𝐹 [𝑥] \subseteq 𝐾 [𝑥]$ . The operations of $𝐹$ are those of $𝐾$ restricted to $𝐹$ (Definition 1.1.32), and sums and products of polynomials are computed from their coefficients by the formulas of Definition 1.2.13 and Definition 7.1.1. So for $𝑝, 𝑠 \in 𝐹 [𝑥]$ , the sum and product are the same whether computed in $𝐹 [𝑥]$ or in $𝐾 [𝑥]$ , and so is the degree.

Let $𝑞, 𝑟 \in 𝐹 [𝑥]$ be the quotient and remainder of $𝑝$ on division by $𝑠$ in $𝐹 [𝑥]$ . Then $𝑝 = 𝑠 𝑞 + 𝑟$ and $deg 𝑟 < deg 𝑠$ also hold in $𝐾 [𝑥]$ . By the uniqueness in Theorem 7.1.14 over $𝐾$ , $𝑞$ and $𝑟$ are the quotient and remainder in $𝐾 [𝑥]$ . In particular the remainder in $𝐾 [𝑥]$ is $𝟎$ if and only if the remainder in $𝐹 [𝑥]$ is $𝟎$ . □

Exercise 7.1.18.routine Let

𝑝 = 𝑥^{4} + 𝑥^{3} + 𝑥 + 2

and

𝑠 = 𝑥^{2} + 1

. Find the quotient and remainder of

𝑝

on division by

𝑠

over

ℚ

, over

𝔽_{2}

, and over

𝔽_{3}

. Over which of these fields does

𝑠

divide

𝑝

Solution.

Uses. Theorem 7.1.14 (Division with remainder), Algorithm 7.1.15 (Long division), Definition 7.1.16 (Divisibility)

Hint 1. Run Algorithm 7.1.15 over

ℚ

. Since

𝑠

is monic, no division by a leading coefficient is needed.

Hint 2. The computation over

ℚ

uses only integer arithmetic, so it can be reduced modulo

2

and modulo

3

. Why does reducing give the right answer?

Sketch. Over

ℚ

𝑝 -

𝑥^{2} 𝑠 =

𝑥^{3} -

𝑥^{2} +

𝑥 +

2

, minus

𝑥 𝑠

gives

- 𝑥^{2} + 2

, plus

𝑠

gives

3

. So

𝑞 = 𝑥^{2} + 𝑥 - 1

and

𝑟 = 3

. Reducing

𝑝 = 𝑠 𝑞 + 3

modulo

2

and

3

gives a valid division there, so by uniqueness

𝑟 = 1

over

𝔽_{2}

and

𝑟 = 𝟎

over

𝔽_{3}

. Only over

𝔽_{3}

does

𝑠

divide

𝑝

Over $ℚ$ , long division gives

\begin{aligned} 𝑝 - 𝑥^{2} 𝑠 & = 𝑥^{3} - 𝑥^{2} + 𝑥 + 2, \\ 𝑝 - (𝑥^{2} + 𝑥) 𝑠 & = - 𝑥^{2} + 2, \\ 𝑝 - (𝑥^{2} + 𝑥 - 1) 𝑠 & = 3 . \end{aligned}

So $𝑝 =$ $(𝑥^{2} + 1) (𝑥^{2} + 𝑥 - 1) +$ $3$ , with quotient $𝑥^{2} + 𝑥 - 1$ and remainder $3$ . Since $3 \neq 0$ , $𝑠$ does not divide $𝑝$ in $ℚ [𝑥]$ .

Every coefficient in this identity is an integer, and the identity was obtained by adding and multiplying integers, so it remains true when every coefficient is read in $𝔽_{2}$ or $𝔽_{3}$ . Over $𝔽_{2}$ , it reads $𝑝 =$ $(𝑥^{2} + 1) (𝑥^{2} + 𝑥 + 1) +$ $1$ , and $deg 1 = 0 < 2$ , so by the uniqueness in Theorem 7.1.14 the quotient is $𝑥^{2} + 𝑥 + 1$ and the remainder is $1$ . Over $𝔽_{3}$ , $3 = 0$ , so $𝑝 =$ $(𝑥^{2} + 1) (𝑥^{2} + 𝑥 + 2)$ (as $- 1 = 2$ ), the remainder is $𝟎$ , and $𝑠 ∣ 𝑝$ . So $𝑠$ divides $𝑝$ only over $𝔽_{3}$ .

7.1.3Roots and linear factors

Definition 7.1.19 (Root). Let

𝑝 \in 𝐹 [𝑥]

. A scalar

𝑐 \in 𝐹

is a root (or zero) of

𝑝

𝑝 (𝑐) = 0

Which roots exist depends on the field. The polynomial $𝑥^{2} + 1$ has no root in $ℝ$ , since $𝑡^{2} + 1 \geq 1$ for real $𝑡$ ; in $ℂ$ it has the roots $𝑖$ and $- 𝑖$ ; in $𝔽_{2}$ it has the root $1$ ; and in $𝔽_{5}$ it has the roots $2$ and $3$ , as $2^{2} + 1 = 5$ and $3^{2} + 1 = 10$ . The polynomial $𝑥^{2} - 2$ has no root in $ℚ$ , because $\sqrt{2}$ is irrational, and two roots in $ℝ$ .

The theorem below is the link between roots and factors. It is the case $𝑠 = 𝑥 - 𝑐$ of division with remainder.

Theorem 7.1.20 (Factor theorem). Let $𝑝 \in 𝐹 [𝑥]$ and $𝑐 \in 𝐹$ . There is a unique $𝑞 \in 𝐹 [𝑥]$ with

𝑝 = (𝑥 - 𝑐) 𝑞 + 𝑝 (𝑐),

and if $deg 𝑝 \geq 1$ , then $deg 𝑞 = deg 𝑝 - 1$ . In particular, $𝑐$ is a root of $𝑝$ if and only if $𝑥 - 𝑐$ divides $𝑝$ .

Proof (by division with remainder).routine

Uses. Theorem 7.1.14 (Division with remainder), Proposition 7.1.10 (Evaluation respects sums and products), Proposition 7.1.4 (Degree of a product), Definition 7.1.16 (Divisibility)

Hint 1. Divide

𝑝

𝑥 - 𝑐

. What can the remainder be?

Hint 2. The remainder is a constant. Evaluate both sides of

𝑝 = (𝑥 - 𝑐) 𝑞 + 𝑟

𝑐

Sketch. Division by

𝑥 - 𝑐

, which has degree

1

, leaves a constant remainder

𝑟

. Evaluating

𝑝 = (𝑥 - 𝑐) 𝑞 + 𝑟

𝑐

with Proposition 7.1.10 gives

𝑝 (𝑐) =

0 \cdot

𝑞 (𝑐) +

𝑟 =

𝑟

. The quotient is unique by Theorem 7.1.14, and degrees give

deg 𝑞 = deg 𝑝 - 1

. If

𝑝 (𝑐) = 0

, then

𝑝 = (𝑥 - 𝑐) 𝑞

; conversely,

𝑝 = (𝑥 - 𝑐) 𝑞^{'}

gives

𝑝 (𝑐) = 0

By Theorem 7.1.14 with $𝑠 = 𝑥 - 𝑐$ , which has degree $1$ , there are unique $𝑞, 𝑟$ with $𝑝 = (𝑥 - 𝑐) 𝑞 + 𝑟$ and $deg 𝑟 < 1$ , so $𝑟$ is a constant. By Proposition 7.1.10, $𝑝 (𝑐) =$ $(𝑐 - 𝑐) 𝑞 (𝑐) +$ $𝑟 =$ $𝑟$ . So $𝑝 =$ $(𝑥 - 𝑐) 𝑞 +$ $𝑝 (𝑐)$ . If also $𝑝 =$ $(𝑥 - 𝑐) 𝑞^{'} +$ $𝑝 (𝑐)$ , this is a division with remainder $𝑝 (𝑐)$ , of degree less than $1$ , so $𝑞^{'} = 𝑞$ by uniqueness.

If $deg 𝑝 \geq 1$ , then $(𝑥 - 𝑐) 𝑞 =$ $𝑝 -$ $𝑝 (𝑐)$ has the same degree as $𝑝$ , because subtracting a constant does not change any coefficient beyond the constant term. So $𝑞 \neq 𝟎$ and $1 + deg 𝑞 = deg 𝑝$ (Proposition 7.1.4).

Finally, if $𝑝 (𝑐) = 0$ , then $𝑝 = (𝑥 - 𝑐) 𝑞$ , so $𝑥 - 𝑐 ∣ 𝑝$ . Conversely, if $𝑝 = (𝑥 - 𝑐) 𝑞^{'}$ for some $𝑞^{'}$ , then $𝑝 (𝑐) =$ $(𝑐 - 𝑐) 𝑞^{'} (𝑐) =$ $0$ by Proposition 7.1.10. □

The quotient can also be written down directly. This is how Section 3.4.5 split off a root before products were available, and it gives a fast way to compute $𝑞$ by hand.

Proof (explicitly, by Horner’s scheme).standard

Uses. Lemma 3.4.23 (Too many roots), Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring), Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 7.1.10 (Evaluation respects sums and products)

Hint 1. The identity

𝑥^{𝑗} -

𝑐^{𝑗} =

(𝑥 - 𝑐) (𝑥^{𝑗 - 1} + 𝑐 𝑥^{𝑗 - 2} + \dots + 𝑐^{𝑗 - 1})

holds in

𝐹 [𝑥]

. Prove it by expanding the right side.

Hint 2. Multiply it by

𝑎_{𝑗}

, sum over

𝑗

, and collect powers of

𝑥

. The coefficients of

𝑞

are the numbers

𝑏_{𝑖}

from the proof of Lemma 3.4.23.

Sketch. The right side of

𝑥^{𝑗} -

𝑐^{𝑗} =

(𝑥 - 𝑐) \sum_{𝑖 < 𝑗} 𝑥^{𝑖} 𝑐^{𝑗 - 1 - 𝑖}

telescopes. Multiplying by

𝑎_{𝑗}

and summing gives

𝑝 -

𝑝 (𝑐) =

(𝑥 - 𝑐) 𝑞

with

𝑞 =

\sum_{𝑖 < 𝑛} 𝑏_{𝑖} 𝑥^{𝑖}

and

𝑏_{𝑖} =

\sum_{𝑗 > 𝑖} 𝑎_{𝑗} 𝑐^{𝑗 - 1 - 𝑖}

, computed from the top by

𝑏_{𝑛 - 1} = 𝑎_{𝑛}

and

𝑏_{𝑖} =

𝑎_{𝑖 + 1} +

𝑐 𝑏_{𝑖 + 1}

. Uniqueness of

𝑞

is cancellation of

𝑥 - 𝑐

, and

𝑏_{𝑛 - 1} = 𝑎_{𝑛} \neq 0

gives the degree.

If $𝑝$ is constant, then $𝑝 -$ $𝑝 (𝑐) =$ $𝟎 =$ $(𝑥 - 𝑐) 𝟎$ . Otherwise write $𝑝 =$ $\sum_{𝑗 = 0}^{𝑛} 𝑎_{𝑗} 𝑥^{𝑗}$ with $𝑛 \geq 1$ and $𝑎_{𝑛} \neq 0$ . For $𝑗 \geq 1$ , the following sum telescopes in $𝐹 [𝑥]$ :

(𝑥 - 𝑐) \sum_{𝑖 = 0}^{𝑗 - 1} 𝑥^{𝑖} 𝑐^{𝑗 - 1 - 𝑖} = \sum_{𝑖 = 0}^{𝑗 - 1} 𝑥^{𝑖 + 1} 𝑐^{𝑗 - 1 - 𝑖} - \sum_{𝑖 = 0}^{𝑗 - 1} 𝑥^{𝑖} 𝑐^{𝑗 - 𝑖} = 𝑥^{𝑗} - 𝑐^{𝑗} .

This is the computation in the proof of Lemma 3.4.23, with the indeterminate $𝑥$ in place of the scalar $𝑡$ . Multiplying by $𝑎_{𝑗}$ , summing over $𝑗 = 1, \dots, 𝑛$ , and collecting the terms with the same power of $𝑥$ ,

𝑝 - 𝑝 (𝑐) = \sum_{𝑗 = 1}^{𝑛} 𝑎_{𝑗} (𝑥^{𝑗} - 𝑐^{𝑗}) = (𝑥 - 𝑐) 𝑞,

where

𝑞 = \sum_{𝑖 = 0}^{𝑛 - 1} 𝑏_{𝑖} 𝑥^{𝑖}, 𝑏_{𝑖} = \sum_{𝑗 = 𝑖 + 1}^{𝑛} 𝑎_{𝑗} 𝑐^{𝑗 - 1 - 𝑖} .

The leading coefficient of $𝑞$ is $𝑏_{𝑛 - 1} = 𝑎_{𝑛} \neq 0$ , so $deg 𝑞 = 𝑛 - 1$ . In both cases, if also $𝑝 -$ $𝑝 (𝑐) =$ $(𝑥 - 𝑐) 𝑞^{'}$ , then $𝑞^{'} = 𝑞$ by Corollary 7.1.7(b). The last sentence of the theorem follows as in the first proof. □

As computed in the proof of Lemma 3.4.23, $𝑏_{𝑛 - 1} = 𝑎_{𝑛}$ and $𝑏_{𝑖} =$ $𝑎_{𝑖 + 1} +$ $𝑐 𝑏_{𝑖 + 1}$ . Continuing one more step, $𝑎_{0} + 𝑐 𝑏_{0} = 𝑝 (𝑐)$ , by expanding the nested form $𝑝 (𝑐) =$ $𝑎_{0} +$ $𝑐 (𝑎_{1} + 𝑐 (𝑎_{2} + \dots + 𝑐 𝑎_{𝑛}))$ . This recursion is Horner’s scheme, or synthetic division. It computes the quotient by $𝑥 - 𝑐$ and the value $𝑝 (𝑐)$ at once, with $𝑛$ multiplications.

Example 7.1.21 (Synthetic division). Let $𝑝 =$ $𝑥^{3} -$ $6 𝑥^{2} +$ $11 𝑥 -$ $6$ and $𝑐 = 1$ . Horner’s scheme runs through the coefficients $1, - 6, 11, - 6$ from the top:

\begin{matrix} 𝑏_{2} = 1, 𝑏_{1} = - 6 + 1 \cdot 1 = - 5, \\ 𝑏_{0} = 11 + 1 \cdot (- 5) = 6, 𝑝 (1) = - 6 + 1 \cdot 6 = 0 . \end{matrix}

So $1$ is a root and $𝑝 =$ $(𝑥 - 1) (𝑥^{2} - 5 𝑥 + 6)$ . Running the scheme again on $𝑥^{2} - 5 𝑥 + 6$ with $𝑐 = 2$ gives $1$ , $- 5 + 2 = - 3$ , and remainder $6 + 2 \cdot (- 3) = 0$ , so $𝑥^{2} -$ $5 𝑥 +$ $6 =$ $(𝑥 - 2) (𝑥 - 3)$ , and

𝑝 = (𝑥 - 1) (𝑥 - 2) (𝑥 - 3) .

In the language of Example 2.6.29, the factor theorem says $ker {ev}_{𝑐} =$ $im (𝑀 - 𝑐 id)$ : the polynomials with root $𝑐$ are exactly the multiples $(𝑥 - 𝑐) 𝑞 =$ $(𝑀 - 𝑐 id) (𝑞)$ .

Intuition. Each root splits off a linear factor. Distinct roots split off distinct factors: after

𝑝 = (𝑥 - 𝑐_{1}) 𝑞

, a second root

𝑐_{2} \neq 𝑐_{1}

𝑝

satisfies

0 =

(𝑐_{2} - 𝑐_{1}) 𝑞 (𝑐_{2})

, and since

𝑐_{2} - 𝑐_{1} \neq 0

and

𝐹

has no zero divisors,

𝑐_{2}

is a root of

𝑞

. Each factor costs one degree, so there is room for at most

deg 𝑝

of them.

Proposition 7.1.22 (Counting roots). Let $𝑝 \in 𝐹 [𝑥]$ be nonzero, and let $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝐹$ be distinct roots of $𝑝$ . Then

(𝑥 - 𝑐_{1}) (𝑥 - 𝑐_{2}) \dots (𝑥 - 𝑐_{𝑘}) ∣ 𝑝,

and $𝑘 \leq deg 𝑝$ . In particular, a nonzero polynomial $𝑝$ has at most $deg 𝑝$ roots in $𝐹$ .

Proof.standard

Uses. Theorem 7.1.20 (Factor theorem), Proposition 7.1.10 (Evaluation respects sums and products), Proposition 1.1.17 (No zero divisors), Proposition 7.1.4 (Degree of a product)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. Induct on

𝑘

, the length of the list of roots. For the inductive step, assume

𝑝 =

(𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑘 - 1}) 𝑞

Hint 2. Evaluate this factorization at

𝑐_{𝑘}

. Why must

𝑞 (𝑐_{𝑘}) = 0

Hint 3. For the bound, compare degrees in

𝑝 =

(𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑘}) 𝑞^{'}

, noting that

𝑞^{'} \neq 𝟎

Sketch. By induction on

𝑘

𝑝 =

(𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑘 - 1}) 𝑞

. Evaluating at

𝑐_{𝑘}

gives

0 =

(𝑐_{𝑘} - 𝑐_{1}) \dots (𝑐_{𝑘} - 𝑐_{𝑘 - 1}) 𝑞 (𝑐_{𝑘})

, and the differences are nonzero, so

𝑞 (𝑐_{𝑘}) = 0

and

𝑥 - 𝑐_{𝑘}

divides

𝑞

by the factor theorem. Then

𝑝 =

(𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑘}) 𝑞^{'}

with

𝑞^{'} \neq 𝟎

, and

deg 𝑝 =

𝑘 +

deg 𝑞^{'} \geq

𝑘

We prove the divisibility by induction on $𝑘$ . For $𝑘 = 0$ the product is empty, that is, equal to $1$ , which divides $𝑝$ . Let $𝑘 \geq 1$ , and suppose $𝑝 =$ $(𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑘 - 1}) 𝑞$ for some $𝑞 \in 𝐹 [𝑥]$ . By Proposition 7.1.10,

0 = 𝑝 (𝑐_{𝑘}) = (𝑐_{𝑘} - 𝑐_{1}) \dots (𝑐_{𝑘} - 𝑐_{𝑘 - 1}) 𝑞 (𝑐_{𝑘}) .

The roots are distinct, so $𝑐_{𝑘} - 𝑐_{𝑖} \neq 0$ for each $𝑖 < 𝑘$ , and the product of these differences is nonzero by Proposition 1.1.17. Hence $𝑞 (𝑐_{𝑘}) = 0$ , and $𝑞 = (𝑥 - 𝑐_{𝑘}) 𝑞^{'}$ for some $𝑞^{'}$ by Theorem 7.1.20. So $𝑝 =$ $(𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑘}) 𝑞^{'}$ , which proves the divisibility.

Since $𝑝 \neq 𝟎$ , also $𝑞^{'} \neq 𝟎$ . Each $𝑥 - 𝑐_{𝑖}$ has degree $1$ , so Proposition 7.1.4 gives $deg 𝑝 =$ $𝑘 +$ $deg 𝑞^{'} \geq$ $𝑘$ . □

The bound $𝑘 \leq deg 𝑝$ is Lemma 3.4.23 in another form: a polynomial in ${𝐹 [𝑥]}_{\leq 𝑛}$ with $𝑛 + 1$ distinct roots is zero. What is new is the divisibility, which says where the roots sit in $𝑝$ . The proof used that $𝐹$ has no zero divisors, to conclude $𝑞 (𝑐_{𝑘}) = 0$ . With coefficients in $ℤ / 8 ℤ$ , which has zero divisors, $𝑥^{2} - 1$ has four roots (Exercise 7.1.52).

Corollary 7.1.23 (Polynomials and their values).

(a)Let $𝑝, 𝑞 \in {𝐹 [𝑥]}_{\leq 𝑛}$ . If $𝑝 (𝑐) = 𝑞 (𝑐)$ for $𝑛 + 1$ distinct $𝑐 \in 𝐹$ , then $𝑝 = 𝑞$ .
(b)A nonzero polynomial has only finitely many roots. If $𝐹$ is infinite, two polynomials with the same polynomial function $𝐹 \to 𝐹$ are equal.

Proof.routine

Uses. Proposition 7.1.22 (Counting roots), Proposition 1.2.18 (Degree and evaluation versus the operations)

Techniques. Contrapositive (Technique 1.5.4)

Hint. Apply Proposition 7.1.22 to

𝑝 - 𝑞

Sketch. In (a),

𝑝 - 𝑞 \in {𝐹 [𝑥]}_{\leq 𝑛}

has

𝑛 + 1

roots, more than its degree if it were nonzero. In (b), if

𝑝

and

𝑞

have the same function,

𝑝 - 𝑞

has every element of

𝐹

as a root, infinitely many.

(a) By Proposition 1.2.18, $𝑝 - 𝑞 \in {𝐹 [𝑥]}_{\leq 𝑛}$ and $(𝑝 - 𝑞) (𝑐) =$ $𝑝 (𝑐) -$ $𝑞 (𝑐) =$ $0$ for the $𝑛 + 1$ given points. If $𝑝 - 𝑞$ were nonzero, it would have at least $𝑛 + 1 > deg (𝑝 - 𝑞)$ roots, contradicting Proposition 7.1.22. So $𝑝 = 𝑞$ .

(b) The first claim is Proposition 7.1.22. If $𝑝 (𝑐) = 𝑞 (𝑐)$ for every $𝑐 \in 𝐹$ and $𝐹$ is infinite, then $𝑝 - 𝑞$ has infinitely many roots, so $𝑝 - 𝑞 = 𝟎$ . □

Part (b) is the fact promised in Aside (Polynomials versus polynomial functions): over $ℚ$ , $ℝ$ , and $ℂ$ , a polynomial is determined by its polynomial function. Over a finite field it is not. Section 7.1.4 finds all polynomials with a given function.

Multiplicity

A root can split off more than one linear factor, as in $𝑥^{2} - 2 𝑥 + 1 = {(𝑥 - 1)}^{2}$ . Counting roots with these repetitions gives a sharper version of Proposition 7.1.22, and over $ℂ$ an exact count.

Definition 7.1.24 (Multiplicity of a root). Let

𝑝 \in 𝐹 [𝑥]

be nonzero and

𝑐 \in 𝐹

. The multiplicity of

𝑐

as a root of

𝑝

is the largest integer

𝑚 \geq 0

such that

{(𝑥 - 𝑐)}^{𝑚} ∣ 𝑝

. A root of multiplicity

1

is simple, and a root of multiplicity at least

2

is repeated (or multiple).

The largest such $𝑚$ exists, because ${(𝑥 - 𝑐)}^{0} = 1$ divides $𝑝$ , and ${(𝑥 - 𝑐)}^{𝑚} ∣ 𝑝$ forces $𝑚 \leq deg 𝑝$ (degrees, as $𝑝 \neq 𝟎$ ). By the factor theorem, $𝑐$ is a root of $𝑝$ exactly when its multiplicity is at least $1$ . We do not define multiplicities for the zero polynomial, which every power of $𝑥 - 𝑐$ divides.

Lemma 7.1.25 (Reading off a multiplicity). Let

𝑝 \in 𝐹 [𝑥]

be nonzero,

𝑐 \in 𝐹

, and

𝑚 \geq 0

. Then

𝑐

has multiplicity exactly

𝑚

as a root of

𝑝

if and only if

𝑝 = {(𝑥 - 𝑐)}^{𝑚} 𝑞

for some

𝑞 \in 𝐹 [𝑥]

with

𝑞 (𝑐) \neq 0

Proof.routine

Uses. Definition 7.1.24 (Multiplicity of a root), Corollary 7.1.7 (No zero divisors, cancellation, and units), Theorem 7.1.20 (Factor theorem)

Hint 1. For “if”, suppose also

{(𝑥 - 𝑐)}^{𝑚 + 1} ∣ 𝑝

, and cancel

{(𝑥 - 𝑐)}^{𝑚}

Hint 2. For “only if”, if

𝑞 (𝑐) = 0

, the factor theorem splits one more factor

𝑥 - 𝑐

off

𝑞

Sketch. If

𝑝 = {(𝑥 - 𝑐)}^{𝑚} 𝑞

with

𝑞 (𝑐) \neq 0

and also

𝑝 = {(𝑥 - 𝑐)}^{𝑚 + 1} 𝑞^{'}

, cancelling

{(𝑥 - 𝑐)}^{𝑚}

gives

𝑞 = (𝑥 - 𝑐) 𝑞^{'}

, so

𝑞 (𝑐) = 0

, a contradiction; so

𝑚

is the largest exponent. Conversely, if

𝑚

is the multiplicity and

𝑝 = {(𝑥 - 𝑐)}^{𝑚} 𝑞

with

𝑞 (𝑐) = 0

, then

𝑞 = (𝑥 - 𝑐) 𝑞^{″}

and

{(𝑥 - 𝑐)}^{𝑚 + 1}

divides

𝑝

Suppose $𝑝 = {(𝑥 - 𝑐)}^{𝑚} 𝑞$ with $𝑞 (𝑐) \neq 0$ . Then ${(𝑥 - 𝑐)}^{𝑚} ∣ 𝑝$ . If ${(𝑥 - 𝑐)}^{𝑚^{'}} ∣ 𝑝$ for some $𝑚^{'} > 𝑚$ , then so does ${(𝑥 - 𝑐)}^{𝑚 + 1}$ , say $𝑝 = {(𝑥 - 𝑐)}^{𝑚 + 1} 𝑞^{'}$ . Then ${(𝑥 - 𝑐)}^{𝑚} 𝑞 =$ ${(𝑥 - 𝑐)}^{𝑚} (𝑥 - 𝑐) 𝑞^{'}$ , and cancelling the nonzero factor ${(𝑥 - 𝑐)}^{𝑚}$ (Corollary 7.1.7(b)) gives $𝑞 = (𝑥 - 𝑐) 𝑞^{'}$ , so $𝑞 (𝑐) = 0$ , a contradiction. Hence $𝑚$ is the multiplicity.

Conversely, let $𝑚$ be the multiplicity, and write $𝑝 = {(𝑥 - 𝑐)}^{𝑚} 𝑞$ . If $𝑞 (𝑐) = 0$ , then $𝑞 = (𝑥 - 𝑐) 𝑞^{″}$ by Theorem 7.1.20, and ${(𝑥 - 𝑐)}^{𝑚 + 1} ∣ 𝑝$ , contradicting the maximality of $𝑚$ . So $𝑞 (𝑐) \neq 0$ . □

Example 7.1.26 (Multiplicity depends on the field). Let

𝑝 = 𝑥^{3} - 𝑥^{2} - 𝑥 + 1

. Over

ℚ

𝑝 = {(𝑥 - 1)}^{2} (𝑥 + 1)

, and

𝑞 = 𝑥 + 1

has

𝑞 (1) = 2 \neq 0

. So

1

is a root of multiplicity

2

, and

- 1

is a simple root. Over

𝔽_{2}

the same polynomial is

𝑥^{3} + 𝑥^{2} + 𝑥 + 1

, and since

𝑥 + 1 = 𝑥 - 1

there,

𝑝 = {(𝑥 - 1)}^{3}

: the root

1

has multiplicity

3

. In the factorization

{(𝑥 - 1)}^{2} (𝑥 + 1)

, the cofactor now has

𝑞 (1) = 1 + 1 = 0

, so Lemma 7.1.25 does not stop at

𝑚 = 2

Proposition 7.1.27 (Multiplicities add up to at most the degree). Let $𝑝 \in 𝐹 [𝑥]$ be nonzero, and let $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝐹$ be distinct, with multiplicities $𝑚_{1}, \dots, 𝑚_{𝑘}$ as roots of $𝑝$ . Then

{(𝑥 - 𝑐_{1})}^{𝑚_{1}} {(𝑥 - 𝑐_{2})}^{𝑚_{2}} \dots {(𝑥 - 𝑐_{𝑘})}^{𝑚_{𝑘}} ∣ 𝑝,

and in particular $𝑚_{1} +$ $𝑚_{2} +$ $\dots +$ $𝑚_{𝑘} \leq$ $deg 𝑝$ .

Proof.standard

Uses. Lemma 7.1.25 (Reading off a multiplicity), Proposition 7.1.10 (Evaluation respects sums and products), Proposition 1.1.17 (No zero divisors), Proposition 7.1.4 (Degree of a product)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. Induct on

𝑘

, as in the proof of Proposition 7.1.22, now splitting off

{(𝑥 - 𝑐_{𝑘})}^{𝑚_{𝑘}}

at once.

Hint 2. Suppose

𝑝 =

{(𝑥 - 𝑐_{1})}^{𝑚_{1}} \dots {(𝑥 - 𝑐_{𝑘 - 1})}^{𝑚_{𝑘 - 1}} 𝑞

. Let

𝜇

be the multiplicity of

𝑐_{𝑘}

as a root of

𝑞

, and write

𝑞 = {(𝑥 - 𝑐_{𝑘})}^{𝜇} ℎ

with

ℎ (𝑐_{𝑘}) \neq 0

Hint 3. Then

𝑝 = {(𝑥 - 𝑐_{𝑘})}^{𝜇} 𝑔

for a

𝑔

with

𝑔 (𝑐_{𝑘}) \neq 0

. Apply Lemma 7.1.25 to

𝑝

Sketch. Induct on

𝑘

. If

𝑝 =

\prod_{𝑖 < 𝑘} {(𝑥 - 𝑐_{𝑖})}^{𝑚_{𝑖}} 𝑞

and

𝑞 = {(𝑥 - 𝑐_{𝑘})}^{𝜇} ℎ

with

ℎ (𝑐_{𝑘}) \neq 0

, then

𝑝 = {(𝑥 - 𝑐_{𝑘})}^{𝜇} 𝑔

with

𝑔 =

\prod_{𝑖 < 𝑘} {(𝑥 - 𝑐_{𝑖})}^{𝑚_{𝑖}} ℎ

and

𝑔 (𝑐_{𝑘}) =

\prod_{𝑖 < 𝑘} {(𝑐_{𝑘} - 𝑐_{𝑖})}^{𝑚_{𝑖}} ℎ (𝑐_{𝑘}) \neq

0

. By Lemma 7.1.25

𝜇 = 𝑚_{𝑘}

, so

{(𝑥 - 𝑐_{𝑘})}^{𝑚_{𝑘}}

divides

𝑞

. Degrees give

\sum 𝑚_{𝑖} \leq deg 𝑝

We induct on $𝑘$ ; for $𝑘 = 0$ there is nothing to prove. Let $𝑘 \geq 1$ and suppose $𝑝 =$ ${(𝑥 - 𝑐_{1})}^{𝑚_{1}} \dots {(𝑥 - 𝑐_{𝑘 - 1})}^{𝑚_{𝑘 - 1}} 𝑞$ . Since $𝑝 \neq 𝟎$ , $𝑞 \neq 𝟎$ . Let $𝜇$ be the multiplicity of $𝑐_{𝑘}$ as a root of $𝑞$ . By Lemma 7.1.25, $𝑞 = {(𝑥 - 𝑐_{𝑘})}^{𝜇} ℎ$ with $ℎ (𝑐_{𝑘}) \neq 0$ . Reordering the factors,

𝑝 = {(𝑥 - 𝑐_{𝑘})}^{𝜇} 𝑔, where 𝑔 = {(𝑥 - 𝑐_{1})}^{𝑚_{1}} \dots {(𝑥 - 𝑐_{𝑘 - 1})}^{𝑚_{𝑘 - 1}} ℎ .

By Proposition 7.1.10, $𝑔 (𝑐_{𝑘}) =$ ${(𝑐_{𝑘} - 𝑐_{1})}^{𝑚_{1}} \dots {(𝑐_{𝑘} - 𝑐_{𝑘 - 1})}^{𝑚_{𝑘 - 1}} ℎ (𝑐_{𝑘})$ , which is nonzero by Proposition 1.1.17, as every factor is nonzero. By Lemma 7.1.25 applied to $𝑝$ , the multiplicity of $𝑐_{𝑘}$ as a root of $𝑝$ is $𝜇$ , so $𝜇 = 𝑚_{𝑘}$ . Hence $𝑝 =$ ${(𝑥 - 𝑐_{1})}^{𝑚_{1}} \dots {(𝑥 - 𝑐_{𝑘})}^{𝑚_{𝑘}} ℎ$ , which proves the divisibility. Comparing degrees with Proposition 7.1.4, $deg 𝑝 =$ $𝑚_{1} +$ $\dots +$ $𝑚_{𝑘} +$ $deg ℎ \geq$ $𝑚_{1} +$ $\dots +$ $𝑚_{𝑘}$ . □

With all $𝑚_{𝑖} \geq 1$ , this sharpens Proposition 7.1.22: counted with multiplicity, a nonzero polynomial has at most $deg 𝑝$ roots. Over $ℂ$ the count is exactly $deg 𝑝$ (Corollary 7.1.35).

Repeated roots can be detected without factoring, with the formal derivative $𝑝^{'}$ of Example 2.1.9.

Exercise 7.1.28.standard Let

𝑝 \in 𝐹 [𝑥]

be nonzero and

𝑐 \in 𝐹

. Show that

𝑐

is a repeated root of

𝑝

if and only if

𝑝 (𝑐) = 0

and

𝑝^{'} (𝑐) = 0

Solution.

Uses. Theorem 7.1.20 (Factor theorem), Lemma 7.1.25 (Reading off a multiplicity), Exercise 2.1.49, Proposition 7.1.10 (Evaluation respects sums and products)

Hint 1. Both conditions include that

𝑐

is a root. So write

𝑝 = (𝑥 - 𝑐) 𝑞

and compute

𝑝^{'}

with the product rule (Exercise 2.1.49).

Hint 2. You should find

𝑝^{'} (𝑐) = 𝑞 (𝑐)

. Compare with Lemma 7.1.25 for

𝑚 = 1

Sketch. If

𝑐

is not a root, both sides are false. If it is,

𝑝 = (𝑥 - 𝑐) 𝑞

, and the product rule gives

𝑝^{'} = 𝑞 + (𝑥 - 𝑐) 𝑞^{'}

, so

𝑝^{'} (𝑐) = 𝑞 (𝑐)

. By Lemma 7.1.25,

𝑐

is simple exactly when

𝑞 (𝑐) \neq 0

, that is, when

𝑝^{'} (𝑐) \neq 0

If $𝑝 (𝑐) \neq 0$ , then $𝑐$ is not a root, so it is not a repeated root, and both sides of the equivalence are false. So suppose $𝑝 (𝑐) = 0$ , and write $𝑝 = (𝑥 - 𝑐) 𝑞$ (Theorem 7.1.20). The formal derivative satisfies the product rule (Exercise 2.1.49(a)), and ${(𝑥 - 𝑐)}^{'} = 1$ , so

𝑝^{'} = 𝑞 + (𝑥 - 𝑐) 𝑞^{'}, hence 𝑝^{'} (𝑐) = 𝑞 (𝑐) + 0 \cdot 𝑞^{'} (𝑐) = 𝑞 (𝑐)

by Proposition 7.1.10. By Lemma 7.1.25 with $𝑚 = 1$ , the root $𝑐$ is simple if and only if $𝑞 (𝑐) \neq 0$ . So $𝑐$ is repeated if and only if $𝑞 (𝑐) = 0$ , that is, if and only if $𝑝^{'} (𝑐) = 0$ .

7.1.4Interpolation, revisited

In Section 3.4.5, the existence of interpolating polynomials came from their uniqueness, through a square linear system, and the Lagrange polynomials $𝐿_{𝑖}$ were defined as solutions of that system. Example 3.4.28 previewed a closed form that needed products. We can now prove it.

Proposition 7.1.29 (Lagrange polynomials in closed form). Let $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ be distinct. For $𝑖 = 0, \dots, 𝑛$ ,

𝐿_{𝑖} = \prod_{𝑗 \neq 𝑖} \frac{𝑥 - 𝑐_{𝑗}}{𝑐_{𝑖} - 𝑐_{𝑗}} .

Consequently, for $𝑑_{0}, \dots, 𝑑_{𝑛} \in 𝐹$ , the unique $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ with $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ is

𝑝 = \sum_{𝑖 = 0}^{𝑛} 𝑑_{𝑖} \prod_{𝑗 \neq 𝑖} \frac{𝑥 - 𝑐_{𝑗}}{𝑐_{𝑖} - 𝑐_{𝑗}} .

Proof.routine

Uses. Definition 3.4.26 (Lagrange polynomials), Theorem 3.4.24 (Polynomial interpolation), Proposition 3.4.27 (Lagrange’s formula), Proposition 7.1.10 (Evaluation respects sums and products), Proposition 7.1.4 (Degree of a product)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Check that the product has degree at most

𝑛

and takes the values that define

𝐿_{𝑖}

Hint 2. Evaluate the product at

𝑐_{𝑘}

with Proposition 7.1.10. Which factor vanishes when

𝑘 \neq 𝑖

Sketch. The product

𝑃_{𝑖}

is a nonzero scalar times a product of

𝑛

linear factors, so it has degree

𝑛

. At

𝑐_{𝑖}

every factor is

1

; at

𝑐_{𝑘}

with

𝑘 \neq 𝑖

, the factor with

𝑗 = 𝑘

0

. So

𝑃_{𝑖}

has the defining values of

𝐿_{𝑖}

, and

𝑃_{𝑖} = 𝐿_{𝑖}

by uniqueness in Theorem 3.4.24. The formula for

𝑝

is then Proposition 3.4.27.

Let $𝑃_{𝑖}$ be the product on the right. The scalar $\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})$ is nonzero, since the nodes are distinct and $𝐹$ has no zero divisors, so

𝑃_{𝑖} = {(\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗}))}^{- 1} \prod_{𝑗 \neq 𝑖} (𝑥 - 𝑐_{𝑗})

is a nonzero scalar times a product of $𝑛$ polynomials of degree $1$ , and $deg 𝑃_{𝑖} = 𝑛$ by Proposition 7.1.4. By Proposition 7.1.10,

𝑃_{𝑖} (𝑐_{𝑘}) = \prod_{𝑗 \neq 𝑖} \frac{𝑐_{𝑘} - 𝑐_{𝑗}}{𝑐_{𝑖} - 𝑐_{𝑗}} .

For $𝑘 = 𝑖$ every factor is $1$ , so $𝑃_{𝑖} (𝑐_{𝑖}) = 1$ . For $𝑘 \neq 𝑖$ , the factor with $𝑗 = 𝑘$ is $0$ , so $𝑃_{𝑖} (𝑐_{𝑘}) = 0$ . Thus $𝑃_{𝑖} \in {𝐹 [𝑥]}_{\leq 𝑛}$ has the values that define $𝐿_{𝑖}$ (Definition 3.4.26), and $𝑃_{𝑖} = 𝐿_{𝑖}$ by the uniqueness in Theorem 3.4.24. The formula for $𝑝$ follows from Proposition 3.4.27. □

Intuition (Two routes to interpolation). With the closed form in hand, Theorem 3.4.24 has a second proof that reverses the roles of existence and uniqueness. Existence is now a construction: the polynomial

\sum_{𝑖} 𝑑_{𝑖} 𝑃_{𝑖}

has degree at most

𝑛

, and the computation above shows that it takes the value

𝑑_{𝑘}

𝑐_{𝑘}

. Uniqueness is Corollary 7.1.23(a), a count of roots. In Section 3.4.5, by contrast, uniqueness was the root count and existence came for free from the square system. The first route needs no formula, which helps when one is hard to guess, as in Exercise 7.1.57. The second gives the answer explicitly and explains the shape of

𝐿_{𝑖}

: it is the simplest polynomial vanishing at the other nodes, rescaled to be

1

𝑐_{𝑖}

The node polynomial $𝜔 =$ $(𝑥 - 𝑐_{0}) (𝑥 - 𝑐_{1}) \dots (𝑥 - 𝑐_{𝑛})$ , of degree $𝑛 + 1$ , describes what happens without the degree bound.

Corollary 7.1.30 (All interpolating polynomials). Let $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ be distinct, let $𝑑_{0}, \dots, 𝑑_{𝑛} \in 𝐹$ , let $𝑝_{0} \in {𝐹 [𝑥]}_{\leq 𝑛}$ be the polynomial with $𝑝_{0} (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ , and let $𝜔 =$ $(𝑥 - 𝑐_{0}) \dots (𝑥 - 𝑐_{𝑛})$ . A polynomial $𝑝 \in 𝐹 [𝑥]$ satisfies $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ if and only if

𝑝 = 𝑝_{0} + 𝜔 ℎ for some ℎ \in 𝐹 [𝑥] .

In particular, $𝑝_{0}$ is the remainder of every such $𝑝$ on division by $𝜔$ .

Proof.routine

Uses. Proposition 7.1.22 (Counting roots), Proposition 7.1.10 (Evaluation respects sums and products), Theorem 7.1.14 (Division with remainder), Theorem 3.4.24 (Polynomial interpolation)

Techniques. Particular plus homogeneous (Technique 3.1.18)

Hint 1. The conditions are linear in

𝑝

, and

𝑝_{0}

is one solution. Which

𝑝

satisfy the homogeneous conditions

𝑝 (𝑐_{𝑖}) = 0

Hint 2. Use the divisibility in Proposition 7.1.22.

Sketch. If

𝑝 = 𝑝_{0} + 𝜔 ℎ

, then

𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖} + 0

. Conversely,

𝑝 - 𝑝_{0}

has the

𝑛 + 1

distinct roots

𝑐_{𝑖}

, so

𝜔

divides it by Proposition 7.1.22 (or

𝑝 - 𝑝_{0} = 𝟎

). Since

deg 𝑝_{0} < deg 𝜔

, the equation

𝑝 = 𝜔 ℎ + 𝑝_{0}

is a division with remainder.

If $𝑝 = 𝑝_{0} + 𝜔 ℎ$ , then $𝑝 (𝑐_{𝑖}) =$ $𝑝_{0} (𝑐_{𝑖}) +$ $𝜔 (𝑐_{𝑖}) ℎ (𝑐_{𝑖}) =$ $𝑑_{𝑖} +$ $0 =$ $𝑑_{𝑖}$ by Proposition 7.1.10, since $𝑐_{𝑖}$ is a root of $𝜔$ . Conversely, suppose $𝑝 (𝑐_{𝑖}) = 𝑑_{𝑖}$ for all $𝑖$ . Then $𝑝 - 𝑝_{0}$ has the $𝑛 + 1$ distinct roots $𝑐_{0}, \dots, 𝑐_{𝑛}$ . If $𝑝 - 𝑝_{0} = 𝟎$ , take $ℎ = 𝟎$ . Otherwise $𝜔 ∣ 𝑝 - 𝑝_{0}$ by Proposition 7.1.22, so $𝑝 - 𝑝_{0} = 𝜔 ℎ$ for some $ℎ$ .

Finally, $𝑝 = 𝜔 ℎ + 𝑝_{0}$ with $deg 𝑝_{0} \leq$ $𝑛 <$ $𝑛 +$ $1 =$ $deg 𝜔$ , so by the uniqueness in Theorem 7.1.14, $𝑝_{0}$ is the remainder of $𝑝$ on division by $𝜔$ . □

This is Technique 3.1.18 once more: $𝑝_{0}$ is a particular solution, and the polynomials vanishing at all nodes are the multiples of $𝜔$ . The quartic $𝑞$ of Figure 3.4.1 is an example. It passes through the same four points as the cubic $𝑝$ , and indeed $𝑞 -$ $𝑝 =$ $\frac{1}{2} (𝑥^{4} - 2 𝑥^{3} - 𝑥^{2} + 2 𝑥) =$ $\frac{1}{2} (𝑥 + 1) 𝑥 (𝑥 - 1) (𝑥 - 2)$ is a multiple of $𝜔$ .

The figure can be explored with the least-squares component of Section 6.5. With four points and degree $3$ , the least-squares cubic passes through all four points, so it is the interpolating polynomial.

\begin{matrix} 𝑝 = 2 𝐿_{0} + 𝐿_{1} + 0 𝐿_{2} + 5 𝐿_{3} = 1 - 2 𝑥 + 𝑥^{3}, \\ 𝐿_{3} = \frac{(𝑥 + 1) 𝑥 (𝑥 - 1)}{6} \end{matrix}

With four points at distinct

𝑥

-values and degree

3

, the residuals are

0

and the curve is the interpolating cubic

1 - 2 𝑥 + 𝑥^{3}

of Example 3.4.25. Drag one point up or down while the others stay fixed: the cubic changes by a multiple of the Lagrange polynomial of that node, which vanishes at the other three nodes. Add a fifth point and the cubic no longer passes through all of them, unless the new point happens to lie on it.

Remark 7.1.31 (Finite fields). Let $𝐹$ be a finite field with $𝑞$ elements, and take all $𝑞$ elements of $𝐹$ as the nodes. Corollary 7.1.30 with all values $𝑑_{𝑖} = 0$ shows that the polynomials whose polynomial function is zero are exactly the multiples of

𝜔_{𝐹} = \prod_{𝑐 \in 𝐹} (𝑥 - 𝑐),

a monic polynomial of degree $𝑞$ . Two polynomials have the same polynomial function if and only if their difference is a multiple of $𝜔_{𝐹}$ , and each function $𝐹 \to 𝐹$ is the polynomial function of exactly one polynomial of degree less than $𝑞$ (Theorem 3.4.24 with all $𝑞$ elements as nodes; compare Problem 1.18). For $𝐹 = 𝔽_{𝑝}$ , $𝜔_{𝐹} = 𝑥^{𝑝} - 𝑥$ (Exercise 7.1.55), which explains the example $𝑥^{𝑝} - 𝑥$ of Aside (Polynomials versus polynomial functions).

7.1.5The Fundamental Theorem of Algebra

Over $ℝ$ , the polynomial $𝑥^{2} + 1$ has no root. Correspondingly, the rotation of the plane by a right angle has no eigenvalue (Section 7.2): no line through $𝟎$ is mapped to itself. The complex numbers were built to give $𝑥^{2} + 1$ a root (Section 1.1.4). The surprise is that nothing more needs to be added: every nonconstant polynomial with complex coefficients, even one with nonreal coefficients such as $𝑥^{2} - 𝑖$ or $𝑥^{5} + 𝑖 𝑥 + 1$ , already has a root in $ℂ$ .

Theorem 7.1.32 (Fundamental Theorem of Algebra). Every nonconstant polynomial

𝑝 \in ℂ [𝑥]

has a root in

ℂ

Intuition (Why there must be a root). Let $𝑝$ have degree $𝑛 \geq 1$ , and watch the values $𝑝 (𝑧)$ as $𝑧$ goes once around the circle $| 𝑧 | = 𝑅$ . For large $𝑅$ , the leading term dominates, $𝑝 (𝑧) \approx 𝑎_{𝑛} 𝑧^{𝑛}$ , and since $𝑧^{𝑛}$ goes around $0$ exactly $𝑛$ times when $𝑧$ goes around once, so does the curve traced by $𝑝 (𝑧)$ . For tiny $𝑅$ , $𝑝 (𝑧) \approx 𝑝 (0)$ , and if $𝑝 (0) \neq 0$ (otherwise $0$ is a root), the curve is a small loop near $𝑝 (0)$ that does not go around $0$ at all. As $𝑅$ grows from small to large, the curve moves continuously, and the number of times it winds around $0$ changes from $0$ to $𝑛$ . It can only change when the curve passes through $0$ , and a point $𝑧$ with $𝑝 (𝑧) = 0$ is a root. Figure 7.1.1 shows this for $𝑝 = 𝑧^{3} + 𝑧 + 1$ .

Making “winds around” precise takes topology. The proof below avoids it. It finds a root as the point where $| 𝑝 |$ is smallest: at a point where $𝑝 \neq 0$ , a small step in a well-chosen direction always makes $| 𝑝 |$ smaller.

Figure 7.1.1. The images of the circles

| 𝑧 | = 𝑅

under

𝑝 (𝑧) = 𝑧^{3} + 𝑧 + 1

, with

0

marked in red. For

𝑅 = 1 / 2

the curve stays near

𝑝 (0) = 1

; for

𝑅 = 3 / 2

it winds three times around

0

. In between it sweeps across

0

three times: at

𝑅 \approx 0.68

, the modulus of the real root

- 0.68 \dots

, and at

𝑅 \approx 1.21

, the common modulus of the two nonreal roots

0.34 \dots \pm 1.16 \dots 𝑖

Proof of Theorem 7.1.32 (by minimizing $| 𝑝 |$ ).challengeBeyond 21-242

Uses. Definition B.1.7 (Modulus), Section B.1, the extreme value theorem: a continuous real function on a closed disk attains a minimum, every complex number has a $𝑘$ -th root, for every $𝑘 \geq 1$

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Show first that

| 𝑝 (𝑧) | > | 𝑝 (0) |

outside a large disk. Then

| 𝑝 |

has a global minimum at some

𝑧_{0}

, by the extreme value theorem.

Hint 2. Suppose

𝑝 (𝑧_{0}) \neq 0

. Write

𝑝 (𝑧_{0} + 𝑤) / 𝑝 (𝑧_{0})

1 + 𝑏_{𝑘} 𝑤^{𝑘}

plus higher powers of

𝑤

, with

𝑏_{𝑘} \neq 0

Hint 3. Choose

𝛽

with

𝛽^{𝑘} = - 1 / 𝑏_{𝑘}

. For small real

𝑡 > 0

, the value at

𝑤 = 𝑡 𝛽

has modulus about

1 - 𝑡^{𝑘} < 1

Sketch. For

| 𝑧 |

large,

| 𝑝 (𝑧) | \geq

| 𝑎_{𝑛} | | 𝑧 |^{𝑛} -

\sum_{𝑘 < 𝑛} | 𝑎_{𝑘} | | 𝑧 |^{𝑘} >

| 𝑝 (0) |

, so the minimum of

| 𝑝 |

on a large closed disk is a global minimum, attained at some

𝑧_{0}

. If

𝑝 (𝑧_{0}) \neq 0

, then

𝑔 (𝑤) =

𝑝 (𝑧_{0} + 𝑤) / 𝑝 (𝑧_{0}) =

1 +

𝑏_{𝑘} 𝑤^{𝑘} +

\dots

with

𝑏_{𝑘} \neq 0

has

| 𝑔 | \geq 1

. With

𝛽^{𝑘} = - 1 / 𝑏_{𝑘}

and small

𝑡 > 0

| 𝑔 (𝑡 𝛽) | \leq

1 -

𝑡^{𝑘} +

𝐶 𝑡^{𝑘 + 1} <

1

, a contradiction.

Let $𝑝 =$ $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ with $𝑛 \geq 1$ and $𝑎_{𝑛} \neq 0$ . We use the modulus $| 𝑧 |$ (Definition B.1.7), with $| 𝑧 𝑤 | = | 𝑧 | | 𝑤 |$ and $| 𝑧 + 𝑤 | \leq | 𝑧 | + | 𝑤 |$ , and two facts from outside algebra: the extreme value theorem, and the existence of $𝑘$ -th roots in $ℂ$ (polar form, Section B.1).

$| 𝑝 |$ attains a global minimum. Let $𝐴 =$ $| 𝑎_{0} | +$ $\dots +$ $| 𝑎_{𝑛 - 1} |$ . For $| 𝑧 | = 𝜌 \geq 1$ , we have $| 𝑎_{𝑘} 𝑧^{𝑘} | \leq$ $| 𝑎_{𝑘} | 𝜌^{𝑛 - 1}$ for $𝑘 < 𝑛$ , so

| 𝑝 (𝑧) | \geq | 𝑎_{𝑛} | 𝜌^{𝑛} - 𝐴 𝜌^{𝑛 - 1} = 𝜌^{𝑛 - 1} (| 𝑎_{𝑛} | 𝜌 - 𝐴) .

Let $𝑅 =$ $max (1, (𝐴 + | 𝑎_{0} | + 1) / | 𝑎_{𝑛} |)$ . For $| 𝑧 | > 𝑅$ the right side is at least $| 𝑎_{0} | + 1 > | 𝑝 (0) |$ . The function $𝑧 \mapsto | 𝑝 (𝑧) |$ is continuous, so it attains a minimum on the closed disk $| 𝑧 | \leq 𝑅$ , at some $𝑧_{0}$ . Then $| 𝑝 (𝑧_{0}) | \leq$ $| 𝑝 (0) | <$ $| 𝑝 (𝑧) |$ for $| 𝑧 | > 𝑅$ , so $| 𝑝 (𝑧_{0}) | \leq$ $| 𝑝 (𝑧) |$ for every $𝑧 \in ℂ$ .

The minimum is $0$ . Suppose $𝑝 (𝑧_{0}) \neq 0$ . Expanding each ${(𝑧_{0} + 𝑤)}^{𝑗}$ shows that $𝑔 (𝑤) =$ $𝑝 (𝑧_{0} + 𝑤) / 𝑝 (𝑧_{0})$ is a polynomial in $𝑤$ of degree $𝑛$ (its coefficient of $𝑤^{𝑛}$ is $𝑎_{𝑛} / 𝑝 (𝑧_{0})$ ), with $𝑔 (0) = 1$ and $| 𝑔 (𝑤) | \geq 1$ for all $𝑤$ . Write

𝑔 (𝑤) = 1 + 𝑏_{𝑘} 𝑤^{𝑘} + 𝑏_{𝑘 + 1} 𝑤^{𝑘 + 1} + \dots + 𝑏_{𝑛} 𝑤^{𝑛},

where $1 \leq 𝑘 \leq 𝑛$ and $𝑏_{𝑘} \neq 0$ . Choose $𝛽 \in ℂ$ with $𝛽^{𝑘} = - 1 / 𝑏_{𝑘}$ , and let $𝐶 =$ $\sum_{𝑗 = 𝑘 + 1}^{𝑛} | 𝑏_{𝑗} | | 𝛽 |^{𝑗}$ . For real $𝑡$ with $0 < 𝑡 \leq 1$ , we have $𝑏_{𝑘} {(𝑡 𝛽)}^{𝑘} =$ $- 𝑡^{𝑘}$ and $𝑡^{𝑗} \leq 𝑡^{𝑘 + 1}$ for $𝑗 > 𝑘$ , so

\begin{aligned} | 𝑔 (𝑡 𝛽) | & \leq | 1 - 𝑡^{𝑘} | + \sum_{𝑗 = 𝑘 + 1}^{𝑛} | 𝑏_{𝑗} | 𝑡^{𝑗} | 𝛽 |^{𝑗} \\ \leq 1 - 𝑡^{𝑘} + 𝐶 𝑡^{𝑘 + 1} = 1 - 𝑡^{𝑘} (1 - 𝐶 𝑡) . \end{aligned}

For $0 < 𝑡 < 1$ with $𝐶 𝑡 < 1$ , this is less than $1$ , contradicting $| 𝑔 | \geq 1$ . Hence $𝑝 (𝑧_{0}) = 0$ .

The details of both steps, and a second proof by linear algebra due to Derksen, are in Section C.1. □

Some analysis is unavoidable in any proof. The theorem fails for the field $ℚ (𝑖) =$ ${𝑎 + 𝑏 𝑖 | 𝑎, 𝑏 \in ℚ}$ , which satisfies all the field axioms and contains a square root of $- 1$ , but in which $𝑥^{2} - 2$ has no root. So no argument from the field axioms alone can prove it; every proof uses a property of $ℝ$ such as completeness.

Splitting into linear factors

Definition 7.1.33 (Splitting). A nonzero polynomial $𝑝 \in 𝐹 [𝑥]$ splits over $𝐹$ if

𝑝 = 𝑎 (𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛})

for some $𝑎, 𝜆_{1}, \dots, 𝜆_{𝑛} \in 𝐹$ .

Then $𝑛 = deg 𝑝$ and $𝑎$ is the leading coefficient, by Proposition 7.1.4. The polynomial $𝑥^{2} + 1$ does not split over $ℝ$ , since a factor $𝑥 - 𝜆$ would give a real root; it splits over $ℂ$ as $(𝑥 - 𝑖) (𝑥 + 𝑖)$ . The polynomial $𝑥^{2} - 2$ splits over $ℝ$ but not over $ℚ$ . When a polynomial splits, its factors record its roots and their multiplicities.

Proposition 7.1.34 (Roots of a split polynomial). Let

𝑝 =

𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})

with

𝑎 \in 𝐹

nonzero and

𝜆_{1}, \dots, 𝜆_{𝑛} \in 𝐹

. The roots of

𝑝

are exactly

𝜆_{1}, \dots, 𝜆_{𝑛}

, and each root of

𝑝

occurs in the list

𝜆_{1}, \dots, 𝜆_{𝑛}

exactly as many times as its multiplicity. In particular, the list is determined by

𝑝

up to order, and the multiplicities of the distinct roots of

𝑝

add up to

deg 𝑝

Proof.routine

Uses. Lemma 7.1.25 (Reading off a multiplicity), Proposition 7.1.10 (Evaluation respects sums and products), Proposition 1.1.17 (No zero divisors), Proposition 7.1.4 (Degree of a product)

Hint 1. Fix

𝜆 \in 𝐹

and let

𝑚

be the number of indices

𝑖

with

𝜆_{𝑖} = 𝜆

. Collect these factors in front.

Hint 2. What is the value at

𝜆

of the product of the remaining factors? Apply Lemma 7.1.25.

Sketch. For

𝜆 \in 𝐹

occurring

𝑚

times in the list,

𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞

with

𝑞 =

𝑎 \prod_{𝜆_{𝑖} \neq 𝜆} (𝑥 - 𝜆_{𝑖})

, and

𝑞 (𝜆) =

𝑎 \prod_{𝜆_{𝑖} \neq 𝜆} (𝜆 - 𝜆_{𝑖}) \neq

0

. By Lemma 7.1.25,

𝜆

has multiplicity

𝑚

. So the number of occurrences of each scalar is its multiplicity, which depends only on

𝑝

; summing over the distinct values in the list gives

𝑛 = deg 𝑝

Fix $𝜆 \in 𝐹$ , and let $𝑚$ be the number of indices $𝑖$ with $𝜆_{𝑖} = 𝜆$ (possibly $𝑚 = 0$ ). Reordering the factors,

𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞, where 𝑞 = 𝑎 \prod_{𝑖 : 𝜆_{𝑖} \neq 𝜆} (𝑥 - 𝜆_{𝑖}) .

By Proposition 7.1.10, $𝑞 (𝜆) =$ $𝑎 \prod_{𝑖 : 𝜆_{𝑖} \neq 𝜆} (𝜆 - 𝜆_{𝑖})$ , which is nonzero by Proposition 1.1.17, as each factor is. By Lemma 7.1.25, the multiplicity of $𝜆$ as a root of $𝑝$ is $𝑚$ . So $𝜆$ is a root exactly when it occurs in the list, and it occurs as many times as its multiplicity. The number of occurrences of each scalar is therefore determined by $𝑝$ , which means the list is determined up to order. Summing the numbers of occurrences over the distinct values in the list counts every index once, which gives $𝑛 = deg 𝑝$ (Proposition 7.1.4). □

Corollary 7.1.35 (Factorization over $ℂ$ ). Let $𝑝 \in ℂ [𝑥]$ be nonzero, of degree $𝑛$ and with leading coefficient $𝑎$ . Then

𝑝 = 𝑎 (𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛}),

where $𝜆_{1}, \dots, 𝜆_{𝑛}$ are the roots of $𝑝$ , each listed as many times as its multiplicity. The factorization is unique up to the order of the factors. In particular, counted with multiplicity, $𝑝$ has exactly $deg 𝑝$ roots in $ℂ$ .

Proof.routine

Uses. Theorem 7.1.32 (Fundamental Theorem of Algebra), Theorem 7.1.20 (Factor theorem), Proposition 7.1.4 (Degree of a product), Proposition 7.1.34 (Roots of a split polynomial), induction on $𝑛$

Hint 1. Induct on

𝑛

. Use Theorem 7.1.32 to find one root, and Theorem 7.1.20 to split it off.

Hint 2. Uniqueness and the statement about multiplicities are Proposition 7.1.34.

Sketch. For

𝑛 = 0

𝑝 = 𝑎

. For

𝑛 \geq 1

, Theorem 7.1.32 gives a root

𝜆_{𝑛}

, the factor theorem gives

𝑝 = (𝑥 - 𝜆_{𝑛}) 𝑞

with

deg 𝑞 = 𝑛 - 1

and leading coefficient

𝑎

, and induction factors

𝑞

. The rest is Proposition 7.1.34.

We show by induction on

𝑛

that

𝑝

splits. For

𝑛 = 0

𝑝 = 𝑎

is the empty product times

𝑎

. Let

𝑛 \geq 1

. By Theorem 7.1.32,

𝑝

has a root

𝜆_{𝑛} \in ℂ

, and by Theorem 7.1.20,

𝑝 = (𝑥 - 𝜆_{𝑛}) 𝑞

with

deg 𝑞 = 𝑛 - 1

. By Proposition 7.1.4, the leading coefficient of

𝑞

is that of

𝑝

, namely

𝑎

. By the induction hypothesis

𝑞 =

𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛 - 1})

, and so

𝑝 =

𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})

. By Proposition 7.1.34, the

𝜆_{𝑖}

are the roots of

𝑝

, each occurring as often as its multiplicity, and the list is determined by

𝑝

up to order. □

So over $ℂ$ the bound of Proposition 7.1.27 is an equality. This is the count behind “an $𝑛 \times 𝑛$ complex matrix has $𝑛$ eigenvalues, counted with multiplicity” in Section 7.4. The coefficients of a split polynomial are also expressed through its roots. We record the two that matter most later.

Proposition 7.1.36 (Sum and product of the roots). Let $𝑛 \geq 1$ and $𝜆_{1}, \dots, 𝜆_{𝑛} \in 𝐹$ . In $(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ , the coefficient of $𝑥^{𝑛 - 1}$ is $- (𝜆_{1} + \dots + 𝜆_{𝑛})$ and the constant term is ${(- 1)}^{𝑛} 𝜆_{1} 𝜆_{2} \dots 𝜆_{𝑛}$ . So for $𝑛 \geq 2$ ,

\begin{aligned} (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛}) & = 𝑥^{𝑛} - (𝜆_{1} + \dots + 𝜆_{𝑛}) 𝑥^{𝑛 - 1} \\ + \dots + {(- 1)}^{𝑛} 𝜆_{1} 𝜆_{2} \dots 𝜆_{𝑛}, \end{aligned}

where the omitted terms have degrees from $1$ to $𝑛 - 2$ .

Proof.routine

Uses. Proposition 7.1.10 (Evaluation respects sums and products), Proposition 7.1.3 ( $𝐹 [𝑥]$ is a commutative ring), induction on $𝑛$

Hint 1. The constant term of a polynomial is its value at

0

Hint 2. For the coefficient of

𝑥^{𝑛 - 1}

, induct on

𝑛

and multiply by

𝑥 - 𝜆_{𝑛 + 1}

Sketch. The constant term is the value at

0

, which is

\prod (0 - 𝜆_{𝑖}) =

{(- 1)}^{𝑛} \prod 𝜆_{𝑖}

. If

(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛}) =

𝑥^{𝑛} -

𝑒 𝑥^{𝑛 - 1} +

𝑟

with

deg 𝑟 \leq 𝑛 - 2

, then multiplying by

𝑥 - 𝜆_{𝑛 + 1}

gives

𝑥^{𝑛 + 1} -

(𝑒 + 𝜆_{𝑛 + 1}) 𝑥^{𝑛}

plus terms of degree at most

𝑛 - 1

Let $𝑃_{𝑛} =$ $(𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ . Its constant term is $𝑃_{𝑛} (0) =$ $(0 - 𝜆_{1}) \dots (0 - 𝜆_{𝑛}) =$ ${(- 1)}^{𝑛} 𝜆_{1} \dots 𝜆_{𝑛}$ by Proposition 7.1.10.

For the coefficient of $𝑥^{𝑛 - 1}$ we induct on $𝑛$ . For $𝑛 = 1$ , $𝑃_{1} = 𝑥 - 𝜆_{1}$ . Suppose $𝑃_{𝑛} =$ $𝑥^{𝑛} -$ $𝑒_{𝑛} 𝑥^{𝑛 - 1} +$ $𝑟$ with $𝑒_{𝑛} = 𝜆_{1} + \dots + 𝜆_{𝑛}$ and $deg 𝑟 \leq 𝑛 - 2$ . Then

\begin{aligned} 𝑃_{𝑛 + 1} & = (𝑥 - 𝜆_{𝑛 + 1}) 𝑃_{𝑛} \\ = 𝑥^{𝑛 + 1} - (𝑒_{𝑛} + 𝜆_{𝑛 + 1}) 𝑥^{𝑛} + (𝜆_{𝑛 + 1} 𝑒_{𝑛} 𝑥^{𝑛 - 1} + 𝑥 𝑟 - 𝜆_{𝑛 + 1} 𝑟), \end{aligned}

and the last group has degree at most $𝑛 - 1$ . So the coefficient of $𝑥^{𝑛}$ in $𝑃_{𝑛 + 1}$ is $- (𝜆_{1} + \dots + 𝜆_{𝑛 + 1})$ . □

By Corollary 7.1.35, for a monic $𝑝 =$ $𝑥^{𝑛} +$ $𝑐_{𝑛 - 1} 𝑥^{𝑛 - 1} +$ $\dots +$ $𝑐_{0} \in$ $ℂ [𝑥]$ , the sum of its roots counted with multiplicity is $- 𝑐_{𝑛 - 1}$ , and their product is ${(- 1)}^{𝑛} 𝑐_{0}$ . Applied to characteristic polynomials, this says that the trace of a complex matrix is the sum of its eigenvalues and the determinant is their product (compare the coefficients in Proposition 5.3.19; see Section 7.5). Exercise 7.1.59 computes the remaining coefficient of a cubic.

7.1.6Factorization over $ℝ$

A polynomial with real coefficients is also a polynomial with complex coefficients, so Corollary 7.1.35 factors it over $ℂ$ . The factors need not be real, but they come in conjugate pairs, and each pair multiplies to a real quadratic.

For $𝑓 =$ $\sum_{𝑘} 𝑐_{𝑘} 𝑥^{𝑘} \in$ $ℂ [𝑥]$ , write $𝑓 = \sum_{𝑘} 𝑐_{𝑘} 𝑥^{𝑘}$ for the polynomial with conjugated coefficients (Definition B.1.1).

Lemma 7.1.37 (Conjugating polynomials). For $𝑓, 𝑔 \in ℂ [𝑥]$ and $𝜆 \in ℂ$ :

(a) $𝑓 + 𝑔 = 𝑓 + 𝑔$ and $𝑓 𝑔 = 𝑓 𝑔$ ;
(b) $𝑓 (𝜆) = 𝑓 (𝜆)$ ;
(c) $𝑓 = 𝑓$ if and only if $𝑓 \in ℝ [𝑥]$ .

Proof.routine

Uses. Notation 6.1.1 (Real and complex scalars), Definition 7.1.1 (Product of polynomials), Definition 1.2.17 (Evaluation)

Hint. Conjugation of complex numbers respects sums and products (Notation 6.1.1). Apply it to the formulas for the coefficients of

𝑓 + 𝑔

and

𝑓 𝑔

, and to the formula for

𝑓 (𝜆)

Sketch. The

𝑘

-th coefficient of

𝑓 𝑔

\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} =

\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}

, that of

𝑓 𝑔

; sums are similar. Likewise

𝑓 (𝜆) = \sum 𝑐_{𝑘} 𝜆^{𝑘}

. A complex number equals its conjugate exactly when it is real.

Write $𝑓 = \sum_{𝑘} 𝑎_{𝑘} 𝑥^{𝑘}$ and $𝑔 = \sum_{𝑘} 𝑏_{𝑘} 𝑥^{𝑘}$ . We use $𝑧 + 𝑤 = 𝑧 + 𝑤$ , $𝑧 𝑤 = 𝑧 𝑤$ , and $𝑧 = 𝑧$ if and only if $𝑧 \in ℝ$ (Notation 6.1.1).

(a) The $𝑘$ -th coefficient of $𝑓 + 𝑔$ is $𝑎_{𝑘} + 𝑏_{𝑘} =$ $𝑎_{𝑘} +$ $𝑏_{𝑘}$ , that of $𝑓 + 𝑔$ . The $𝑘$ -th coefficient of $𝑓 𝑔$ is $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗} =$ $\sum_{𝑖 + 𝑗 = 𝑘} 𝑎_{𝑖} 𝑏_{𝑗}$ , that of $𝑓 𝑔$ .

(b) $𝑓 (𝜆) =$ $\sum_{𝑘} 𝑎_{𝑘} 𝜆^{𝑘} =$ $\sum_{𝑘} 𝑎_{𝑘} 𝜆^{𝑘} =$ $𝑓 (𝜆)$ .

(c) $𝑓 = 𝑓$ means $𝑎_{𝑘} = 𝑎_{𝑘}$ for every $𝑘$ , that is, $𝑎_{𝑘} \in ℝ$ for every $𝑘$ . □

Intuition. Conjugation is a symmetry of

ℂ

: it respects sums and products and fixes every real number. So it carries any equation with real coefficients to another true equation. Applied to

𝑝 (𝜆) = 0

for a real polynomial

𝑝

, it gives

𝑝 (𝜆) = 0

, and applied to a factorization, it shows that

𝜆

and

𝜆

occur equally often.

Proposition 7.1.38 (Conjugate roots). Let

𝑝 \in ℝ [𝑥]

be nonzero, regarded as an element of

ℂ [𝑥]

, and let

𝜆 \in ℂ

. Then

𝜆

and

𝜆

have the same multiplicity as roots of

𝑝

. In particular, the nonreal roots of

𝑝

come in pairs

𝜆 \neq 𝜆

Proof.standard

Uses. Lemma 7.1.37 (Conjugating polynomials), Lemma 7.1.25 (Reading off a multiplicity), Notation 6.1.1 (Real and complex scalars)

Hint 1. First show that

𝜆

is a root whenever

𝜆

is: conjugate the equation

𝑝 (𝜆) = 0

Hint 2. For multiplicities, conjugate a factorization

𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞

with

𝑞 (𝜆) \neq 0

, and apply Lemma 7.1.25 at

𝜆

Sketch. Let

𝑚

be the multiplicity of

𝜆

, so

𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞

with

𝑞 (𝜆) \neq 0

. Conjugating with Lemma 7.1.37, and using

𝑝 = 𝑝

and

𝑥 - 𝜆 = 𝑥 - 𝜆

, gives

𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞

with

𝑞 (𝜆) = 𝑞 (𝜆) \neq 0

. So

𝜆

has multiplicity

𝑚

Let $𝑚$ be the multiplicity of $𝜆$ , and write $𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞$ with $𝑞 (𝜆) \neq 0$ (Lemma 7.1.25). Since $𝑝$ has real coefficients, $𝑝 = 𝑝$ , and $𝑥 - 𝜆 = 𝑥 - 𝜆$ . By Lemma 7.1.37(a), applied to each factor,

𝑝 = 𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞,

and by Lemma 7.1.37(b), $𝑞 (𝜆) = 𝑞 (𝜆) \neq 0$ . By Lemma 7.1.25, $𝜆$ has multiplicity $𝑚$ as a root of $𝑝$ . If $𝜆$ is not real, then $𝜆 \neq 𝜆$ , so the nonreal roots of $𝑝$ come in pairs $𝜆, 𝜆$ of equal multiplicity. □

Theorem 7.1.39 (Factorization over $ℝ$ ). Every nonzero $𝑝 \in ℝ [𝑥]$ can be written as

𝑝 = 𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑘}) (𝑥^{2} + 𝑏_{1} 𝑥 + 𝑐_{1}) \dots (𝑥^{2} + 𝑏_{𝑙} 𝑥 + 𝑐_{𝑙}),

where $𝑎,$ $𝜆_{𝑖},$ $𝑏_{𝑗},$ $𝑐_{𝑗} \in$ $ℝ$ and $𝑏_{𝑗}^{2} < 4 𝑐_{𝑗}$ for each $𝑗$ (so $𝑘 + 2 𝑙 = deg 𝑝$ ). Here $𝜆_{1}, \dots, 𝜆_{𝑘}$ are the real roots of $𝑝$ , each listed as many times as its multiplicity. The factorization is unique up to the order of the factors.

Proof.standard

Uses. Corollary 7.1.35 (Factorization over $ℂ$ ), Proposition 7.1.38 (Conjugate roots), Proposition 7.1.34 (Roots of a split polynomial), Notation 6.1.1 (Real and complex scalars), Corollary 7.1.17 (Division does not depend on the field)

Hint 1. Factor

𝑝

over

ℂ

. The real roots give real linear factors. What is

(𝑥 - 𝜇) (𝑥 - 𝜇)

for a nonreal

𝜇

Hint 2.

(𝑥 - 𝜇) (𝑥 - 𝜇) =

𝑥^{2} -

2 (Re 𝜇) 𝑥 +

| 𝜇 |^{2}

. Use Proposition 7.1.38 to pair up all nonreal factors.

Hint 3. For uniqueness, split each real quadratic factor over

ℂ

into a conjugate pair, and compare with the complex factorization, which is unique by Proposition 7.1.34.

Sketch. Over

ℂ

𝑝 = 𝑎 \prod_{𝑖} (𝑥 - 𝜆_{𝑖})

with

𝑎

real. By Proposition 7.1.38, the nonreal roots with negative imaginary part are the conjugates of those with positive imaginary part, with the same multiplicities, so the nonreal factors pair up as

(𝑥 - 𝜇) (𝑥 - 𝜇) =

𝑥^{2} -

2 (Re 𝜇) 𝑥 +

| 𝜇 |^{2}

, a real quadratic with discriminant

- 4 {(Im 𝜇)}^{2} < 0

. Conversely, each real quadratic with

𝑏^{2} < 4 𝑐

(𝑥 - 𝜈) (𝑥 - 𝜈)

for a nonreal

𝜈

, so any real factorization gives the complex one; the real roots are the

𝜆_{𝑖}

, and the roots with positive imaginary part determine the quadratics.

Existence. By Corollary 7.1.35, $𝑝 =$ $𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ in $ℂ [𝑥]$ , where $𝑎$ is the leading coefficient of $𝑝$ , which is real, and the $𝜆_{𝑖}$ are the roots of $𝑝$ listed with multiplicity. Reorder them so that $𝜆_{1}, \dots, 𝜆_{𝑘}$ are the real ones. Let $𝜇_{1}, \dots, 𝜇_{𝑙}$ be the roots of $𝑝$ with positive imaginary part, each listed as many times as its multiplicity. By Proposition 7.1.38, conjugation maps the roots with positive imaginary part bijectively onto the roots with negative imaginary part, preserving multiplicities. So $𝜇_{1}, \dots, 𝜇_{𝑙}$ are the roots with negative imaginary part, listed with multiplicity. Hence, reordering factors,

𝑝 = 𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑘}) \prod_{𝑗 = 1}^{𝑙} (𝑥 - 𝜇_{𝑗}) (𝑥 - 𝜇_{𝑗}) .

For each $𝑗$ , using $𝜇 + 𝜇 = 2 Re 𝜇$ and $𝜇 𝜇 = | 𝜇 |^{2}$ (Notation 6.1.1),

(𝑥 - 𝜇_{𝑗}) (𝑥 - 𝜇_{𝑗}) = 𝑥^{2} - 2 (Re 𝜇_{𝑗}) 𝑥 + | 𝜇_{𝑗} |^{2} = 𝑥^{2} + 𝑏_{𝑗} 𝑥 + 𝑐_{𝑗},

with $𝑏_{𝑗} = - 2 Re 𝜇_{𝑗}$ and $𝑐_{𝑗} = | 𝜇_{𝑗} |^{2}$ real, and $𝑏_{𝑗}^{2} -$ $4 𝑐_{𝑗} =$ $4 {(Re 𝜇_{𝑗})}^{2} -$ $4 ({(Re 𝜇_{𝑗})}^{2} + {(Im 𝜇_{𝑗})}^{2}) =$ $- 4 {(Im 𝜇_{𝑗})}^{2} <$ $0$ . All factors now lie in $ℝ [𝑥]$ , and products in $ℝ [𝑥]$ are computed by the same formula as in $ℂ [𝑥]$ , so this is a factorization of the required form in $ℝ [𝑥]$ . The $𝜆_{𝑖}$ are the real roots listed with their multiplicities in $ℂ [𝑥]$ ; for a real root $𝜆$ this is also its multiplicity in $ℝ [𝑥]$ , because whether ${(𝑥 - 𝜆)}^{𝑚}$ divides $𝑝$ does not depend on the field (Corollary 7.1.17).

Uniqueness. Take any factorization of the stated form, with factors $𝑥 - 𝜆_{𝑖}^{'}$ ( $𝑖 \leq 𝑘^{'}$ ) and $𝑥^{2} + 𝑏_{𝑗}^{'} 𝑥 + 𝑐_{𝑗}^{'}$ ( $𝑗 \leq 𝑙^{'}$ ) and constant $𝑎^{'}$ . Comparing leading coefficients (Proposition 7.1.4), $𝑎^{'} = 𝑎$ . For each $𝑗$ , since $4 𝑐_{𝑗}^{'} - 𝑏_{𝑗}^{' 2} > 0$ , the number

𝜈_{𝑗} = \frac{- 𝑏_{𝑗}^{'} + 𝑖 \sqrt{4 𝑐_{𝑗}^{'} - 𝑏_{𝑗}^{' 2}}}{2}

is not real, and $𝜈_{𝑗} + 𝜈_{𝑗} = - 𝑏_{𝑗}^{'}$ and $𝜈_{𝑗} 𝜈_{𝑗} =$ $(𝑏_{𝑗}^{' 2} + (4 𝑐_{𝑗}^{'} - 𝑏_{𝑗}^{' 2})) / 4 =$ $𝑐_{𝑗}^{'}$ , so $𝑥^{2} +$ $𝑏_{𝑗}^{'} 𝑥 +$ $𝑐_{𝑗}^{'} =$ $(𝑥 - 𝜈_{𝑗}) (𝑥 - 𝜈_{𝑗})$ . Substituting, $𝑝$ splits over $ℂ$ with the list of roots $𝜆_{1}^{'},$ $\dots,$ $𝜆_{𝑘^{'}}^{'},$ $𝜈_{1},$ $𝜈_{1},$ $\dots,$ $𝜈_{𝑙^{'}},$ $𝜈_{𝑙^{'}}$ . By Proposition 7.1.34 this list is, up to order, the list of roots of $𝑝$ with multiplicity. Its real members are the $𝜆_{𝑖}^{'}$ , so these are the real roots of $𝑝$ listed with multiplicity. Its members with positive imaginary part are the $𝜈_{𝑗}$ , so these are the roots of $𝑝$ with positive imaginary part, listed with multiplicity. Both lists are determined by $𝑝$ , and each quadratic factor is determined by its $𝜈_{𝑗}$ , as $(𝑥 - 𝜈_{𝑗}) (𝑥 - 𝜈_{𝑗})$ . Hence the factors are determined by $𝑝$ up to order. □

Example 7.1.40 ( $𝑥^{4} + 4$ ). Since ${(1 + 𝑖)}^{2} = 2 𝑖$ , we get ${(1 + 𝑖)}^{4} = {(2 𝑖)}^{2} = - 4$ , and in the same way ${(\pm 1 \pm 𝑖)}^{4} = - 4$ for all four choices of signs. These are four distinct roots of $𝑥^{4} + 4$ , so by Corollary 7.1.35

𝑥^{4} + 4 = (𝑥 - 1 - 𝑖) (𝑥 - 1 + 𝑖) (𝑥 + 1 - 𝑖) (𝑥 + 1 + 𝑖) .

Pairing conjugates as in the proof, $(𝑥 - 1 - 𝑖) (𝑥 - 1 + 𝑖) =$ ${(𝑥 - 1)}^{2} +$ $1$ and $(𝑥 + 1 - 𝑖) (𝑥 + 1 + 𝑖) =$ ${(𝑥 + 1)}^{2} +$ $1$ , so

𝑥^{4} + 4 = (𝑥^{2} - 2 𝑥 + 2) (𝑥^{2} + 2 𝑥 + 2)

over $ℝ$ , and even over $ℚ$ , although $𝑥^{4} + 4$ has no real root. As Proposition 7.1.36 predicts, the roots add up to $0$ , the negative of the coefficient of $𝑥^{3}$ , and their product is $(1 + 1) (1 + 1) =$ $4 =$ ${(- 1)}^{4} \cdot$ $4$ .

The real quadratic factors cannot be split further over $ℝ$ . This is the real counterpart of the fact that linear factors cannot be split further over $ℂ$ .

Definition 7.1.41 (Irreducible polynomial). A polynomial

𝑝 \in 𝐹 [𝑥]

of degree at least

1

is irreducible over

𝐹

if it cannot be written as

𝑝 = 𝑔 ℎ

with

𝑔, ℎ \in 𝐹 [𝑥]

both of degree at least

1

. Otherwise, and if

deg 𝑝 \geq 1

, it is reducible.

Every polynomial of degree $1$ is irreducible, since degrees add (Proposition 7.1.4). Irreducibility depends on the field: $𝑥^{2} + 1$ is irreducible over $ℝ$ but equals $(𝑥 - 𝑖) (𝑥 + 𝑖)$ over $ℂ$ ; $𝑥^{2} + 𝑥 + 1$ is irreducible over $𝔽_{2}$ , since it has no root there (Exercise 7.1.61), but equals ${(𝑥 - 1)}^{2}$ over $𝔽_{3}$ . Irreducible polynomials play the role of prime numbers (Exercise 7.1.68).

Corollary 7.1.42 (Irreducible polynomials over

ℂ

and

ℝ

(a)A polynomial in $ℂ [𝑥]$ is irreducible over $ℂ$ if and only if it has degree $1$ .
(b)A polynomial in $ℝ [𝑥]$ is irreducible over $ℝ$ if and only if it has degree $1$ , or it is $𝑎 𝑥^{2} + 𝑏 𝑥 + 𝑐$ with $𝑎 \neq 0$ and $𝑏^{2} < 4 𝑎 𝑐$ .

Proof.routine

Uses. Corollary 7.1.35 (Factorization over $ℂ$ ), Theorem 7.1.39 (Factorization over $ℝ$ ), Theorem 7.1.20 (Factor theorem), Exercise 1.1.50, Proposition 7.1.4 (Degree of a product)

Hint 1. A polynomial of degree

1

is always irreducible. For larger degrees, read off a factorization from Corollary 7.1.35 or Theorem 7.1.39.

Hint 2. For a real quadratic, a factorization into two linear factors gives a real root. When does

𝑎 𝑥^{2} + 𝑏 𝑥 + 𝑐

have a real root?

Sketch. Degree

1

is irreducible because degrees add. Over

ℂ

, degree

𝑛 \geq 2

splits into

𝑛 \geq 2

linear factors. Over

ℝ

, degree at least

3

gives at least two factors in Theorem 7.1.39, as

𝑘 + 2 𝑙 \geq 3

. A real quadratic is reducible if and only if it has a real root, and by the quadratic formula (Exercise 1.1.50) that happens if and only if

𝑏^{2} - 4 𝑎 𝑐 \geq 0

Polynomials of degree $1$ are irreducible over every field, because in a product $𝑔 ℎ$ of two polynomials of degree at least $1$ , the degree is at least $2$ .

(a) If $𝑝 \in ℂ [𝑥]$ has degree $𝑛 \geq 2$ , then by Corollary 7.1.35 $𝑝 =$ $(𝑎 (𝑥 - 𝜆_{1})) \cdot$ $((𝑥 - 𝜆_{2}) \dots (𝑥 - 𝜆_{𝑛}))$ , a product of two polynomials of degrees $1$ and $𝑛 - 1 \geq 1$ .

(b) Let $𝑝 \in ℝ [𝑥]$ . If $deg 𝑝 \geq 3$ , then in Theorem 7.1.39 $𝑘 + 2 𝑙 = deg 𝑝 \geq 3$ , so there are at least two non-constant factors. Splitting off one of them (and absorbing $𝑎$ into it) writes $𝑝$ as a product of two polynomials of degree at least $1$ , so $𝑝$ is reducible.

Now let $𝑝 = 𝑎 𝑥^{2} + 𝑏 𝑥 + 𝑐$ with $𝑎 \neq 0$ . If $𝑝$ has a real root $𝑡$ , then $𝑝 = (𝑥 - 𝑡) 𝑞$ with $deg 𝑞 = 1$ (Theorem 7.1.20), so $𝑝$ is reducible. Conversely, if $𝑝 = 𝑔 ℎ$ with $deg 𝑔 = deg ℎ = 1$ , say $𝑔 = 𝑢 𝑥 + 𝑣$ with $𝑢 \neq 0$ , then $- 𝑣 / 𝑢$ is a root of $𝑔$ , hence of $𝑝$ . So $𝑝$ is irreducible if and only if it has no real root. By Exercise 1.1.50, $𝑝$ has a real root if and only if $𝑏^{2} - 4 𝑎 𝑐 = 𝑑^{2}$ for some $𝑑 \in ℝ$ , that is, if and only if $𝑏^{2} - 4 𝑎 𝑐 \geq 0$ . So $𝑝$ is irreducible if and only if $𝑏^{2} < 4 𝑎 𝑐$ . □

The last consequence concerns odd degree. It has a proof from the factorization and a proof that avoids $ℂ$ altogether.

Corollary 7.1.43 (Odd degree gives a real root). Every polynomial

𝑝 \in ℝ [𝑥]

of odd degree has a real root.

Proof (by conjugate pairs).routine

Uses. Theorem 7.1.39 (Factorization over $ℝ$ ), Proposition 7.1.10 (Evaluation respects sums and products)

Hint. In Theorem 7.1.39,

𝑘 + 2 𝑙 = deg 𝑝

. What does odd degree say about

𝑘

Sketch.

𝑘 + 2 𝑙 = deg 𝑝

is odd, so

𝑘 \geq 1

, and

𝜆_{1}

is a real root.

In the factorization of Theorem 7.1.39,

𝑘 + 2 𝑙 = deg 𝑝

is odd, so

𝑘

is odd and in particular

𝑘 \geq 1

. Then

𝜆_{1}

is a real root of

𝑝

, by Proposition 7.1.10. □

Proof (by the intermediate value theorem).standard

Uses. the intermediate value theorem

Hint 1. Assume the leading coefficient is positive. Show that

𝑝 (𝑡) > 0

for large positive

𝑡

and

𝑝 (𝑡) < 0

for large negative

𝑡

Hint 2. For

| 𝑡 | \geq 1

, bound the lower terms by

𝐴 | 𝑡 |^{𝑛 - 1}

, where

𝐴

is the sum of the absolute values of the lower coefficients.

Sketch. With

𝑎_{𝑛} > 0

and

𝐴 =

\sum_{𝑘 < 𝑛} | 𝑎_{𝑘} |

, for

| 𝑡 | \geq 1

the lower terms are at most

𝐴 | 𝑡 |^{𝑛 - 1}

in absolute value. At

𝑇 = 1 + 𝐴 / 𝑎_{𝑛}

this gives

𝑝 (𝑇) > 0 > 𝑝 (- 𝑇)

, because

𝑛

is odd. The intermediate value theorem gives a root in

(- 𝑇, 𝑇)

Let $𝑝 =$ $\sum_{𝑘 = 0}^{𝑛} 𝑎_{𝑘} 𝑥^{𝑘}$ with $𝑛$ odd and $𝑎_{𝑛} \neq 0$ . Replacing $𝑝$ by $- 𝑝$ , which has the same roots, we may assume $𝑎_{𝑛} > 0$ . Let $𝐴 =$ $| 𝑎_{0} | +$ $\dots +$ $| 𝑎_{𝑛 - 1} |$ . For real $𝑡$ with $| 𝑡 | \geq 1$ , we have $| 𝑎_{𝑘} 𝑡^{𝑘} | \leq$ $| 𝑎_{𝑘} | | 𝑡 |^{𝑛 - 1}$ for $𝑘 < 𝑛$ , so

| 𝑝 (𝑡) - 𝑎_{𝑛} 𝑡^{𝑛} | \leq 𝐴 | 𝑡 |^{𝑛 - 1} .

Let $𝑇 = 1 + 𝐴 / 𝑎_{𝑛} \geq 1$ , so that $𝑎_{𝑛} 𝑇 - 𝐴 = 𝑎_{𝑛} > 0$ . Then $𝑝 (𝑇) \geq$ $𝑎_{𝑛} 𝑇^{𝑛} -$ $𝐴 𝑇^{𝑛 - 1} =$ $𝑇^{𝑛 - 1} 𝑎_{𝑛} >$ $0$ , and since $𝑛$ is odd, ${(- 𝑇)}^{𝑛} = - 𝑇^{𝑛}$ and

𝑝 (- 𝑇) \leq - 𝑎_{𝑛} 𝑇^{𝑛} + 𝐴 𝑇^{𝑛 - 1} = - 𝑇^{𝑛 - 1} 𝑎_{𝑛} < 0 .

The function $𝑡 \mapsto 𝑝 (𝑡)$ is continuous on $[- 𝑇, 𝑇]$ , so by the intermediate value theorem it vanishes somewhere in $(- 𝑇, 𝑇)$ . □

The second proof is the more elementary one: it uses the completeness of $ℝ$ directly, through the intermediate value theorem, while the first relies on the Fundamental Theorem of Algebra, whose proof uses completeness in a much more elaborate way. On the other hand, the first proof gives more: the number of real roots, counted with multiplicity, has the same parity as $deg 𝑝$ . In Section 7.3, this corollary shows that every operator on a real vector space of odd dimension has an eigenvalue.

7.1.7Greatest common divisors Beyond 21-242

Greatest common divisors of polynomials are not covered in lecture. They are used in Section 7.6, Section 10.2, and Section 14.4.

The integers have greatest common divisors, computed by the Euclidean algorithm, and $gcd (𝑎, 𝑏)$ is an integer combination $𝑢 𝑎 + 𝑣 𝑏$ (Bézout’s identity). All of this carries over to $𝐹 [𝑥]$ , because the only tool it needs is division with remainder. The application to linear algebra is this: if $𝑝$ and $𝑠$ have no common factor, then $𝑢 𝑝 + 𝑣 𝑠 = 1$ for some polynomials $𝑢$ and $𝑣$ , and for a square matrix $𝐴$ , Remark 7.1.11 turns this into $𝑢 (𝐴) 𝑝 (𝐴) +$ $𝑣 (𝐴) 𝑠 (𝐴) =$ $𝐼_{𝑛}$ . Section 7.6 and Section 10.2 use such identities to split a space into the kernels of $𝑝 (𝐴)$ and $𝑠 (𝐴)$ .

Definition 7.1.44 (Greatest common divisor). Let

𝑝, 𝑠 \in 𝐹 [𝑥]

, not both

𝟎

. A greatest common divisor of

𝑝

and

𝑠

is a monic polynomial

𝑑

such that

𝑑 ∣ 𝑝

𝑑 ∣ 𝑠

, and every common divisor of

𝑝

and

𝑠

divides

𝑑

. If

1

is a greatest common divisor of

𝑝

and

𝑠

, they are coprime.

“Greatest” refers to divisibility, but it implies the largest degree: every common divisor divides $𝑑$ , so its degree is at most $deg 𝑑$ .

Theorem 7.1.45 (Bézout’s identity). Let $𝑝, 𝑠 \in 𝐹 [𝑥]$ , not both $𝟎$ . Then $𝑝$ and $𝑠$ have exactly one greatest common divisor $𝑑$ , written $gcd (𝑝, 𝑠)$ , and there are $𝑢, 𝑣 \in 𝐹 [𝑥]$ with

𝑑 = 𝑢 𝑝 + 𝑣 𝑠 .

Moreover, $𝑑$ is the monic polynomial of smallest degree of the form $𝑢 𝑝 + 𝑣 𝑠$ .

Intuition. Consider all combinations

𝑢 𝑝 + 𝑣 𝑠

. Every common divisor of

𝑝

and

𝑠

divides each of them, so a combination that itself divides

𝑝

and

𝑠

is automatically a greatest common divisor. The smallest nonzero combination is the natural candidate: dividing

𝑝

by it leaves a remainder that is again a combination, and smaller, so it must be

𝟎

Proof (by a combination of smallest degree).hard

Uses. Theorem 7.1.14 (Division with remainder), Definition 7.1.44 (Greatest common divisor), Definition 7.1.16 (Divisibility), Corollary 7.1.7 (No zero divisors, cancellation, and units)

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9), Uniqueness via two candidates (Technique 1.1.8), Compare degrees and leading coefficients (Technique 7.1.6)

Hint 1. Let

𝐼 =

{𝑢 𝑝 + 𝑣 𝑠 | 𝑢, 𝑣 \in 𝐹 [𝑥]}

. Choose a nonzero element of

𝐼

of smallest degree, and scale it to be monic.

Hint 2. Divide

𝑝

by this element

𝑑

. Show that the remainder lies in

𝐼

, and conclude from minimality that it is

𝟎

Hint 3. For uniqueness, two greatest common divisors divide each other, and both are monic.

Sketch. The set

𝐼

of combinations

𝑢 𝑝 + 𝑣 𝑠

is closed under sums and under multiplication by polynomials, and contains a nonzero element. Let

𝑑 \in 𝐼

be monic of smallest degree. The remainder of

𝑝

on division by

𝑑

𝑝 - 𝑞 𝑑 \in 𝐼

and has degree less than

deg 𝑑

, so it is

𝟎

; thus

𝑑 ∣ 𝑝

, and likewise

𝑑 ∣ 𝑠

. A common divisor of

𝑝

and

𝑠

divides

𝑢 𝑝 + 𝑣 𝑠 = 𝑑

. Two greatest common divisors divide each other and are monic, so they are equal.

Let $𝐼 =$ ${𝑢 𝑝 + 𝑣 𝑠 | 𝑢, 𝑣 \in 𝐹 [𝑥]}$ . It contains $𝑝 = 1 𝑝 + 𝟎 𝑠$ and $𝑠$ , so it contains a nonzero polynomial. It is closed under sums, since $(𝑢 𝑝 + 𝑣 𝑠) +$ $(𝑢^{'} 𝑝 + 𝑣^{'} 𝑠) =$ $(𝑢 + 𝑢^{'}) 𝑝 +$ $(𝑣 + 𝑣^{'}) 𝑠$ , and under multiplication by any $𝑤 \in 𝐹 [𝑥]$ , since $𝑤 (𝑢 𝑝 + 𝑣 𝑠) =$ $(𝑤 𝑢) 𝑝 +$ $(𝑤 𝑣) 𝑠$ .

Existence. Among the nonzero elements of $𝐼$ , choose one of smallest degree. Multiplying it by the inverse of its leading coefficient keeps it in $𝐼$ and makes it monic; call the result $𝑑 = 𝑢 𝑝 + 𝑣 𝑠$ . Divide $𝑝$ by $𝑑$ : $𝑝 = 𝑑 𝑞 + 𝑟$ with $deg 𝑟 < deg 𝑑$ (Theorem 7.1.14). Then

𝑟 = 𝑝 - 𝑞 𝑑 = (1 - 𝑞 𝑢) 𝑝 + (- 𝑞 𝑣) 𝑠 \in 𝐼 .

By the choice of $𝑑$ , no nonzero element of $𝐼$ has degree less than $deg 𝑑$ , so $𝑟 = 𝟎$ and $𝑑 ∣ 𝑝$ . In the same way $𝑑 ∣ 𝑠$ . If $𝑒$ divides both $𝑝$ and $𝑠$ , say $𝑝 = 𝑒 𝑝^{'}$ and $𝑠 = 𝑒 𝑠^{'}$ , then $𝑑 =$ $𝑢 𝑝 +$ $𝑣 𝑠 =$ $𝑒 (𝑢 𝑝^{'} + 𝑣 𝑠^{'})$ , so $𝑒 ∣ 𝑑$ . Hence $𝑑$ is a greatest common divisor, and it is a combination of $𝑝$ and $𝑠$ .

Uniqueness. If $𝑑$ and $𝑑^{'}$ are both greatest common divisors, then each divides the other, by the definition applied twice. As noted after Definition 7.1.16, two monic polynomials that divide each other are equal.

Smallest degree. We showed that the gcd is a monic element of $𝐼$ of smallest degree. Conversely, any monic $𝑑^{'} \in 𝐼$ of smallest degree is, by the existence argument applied to $𝑑^{'}$ , a greatest common divisor, so it equals $𝑑$ . □

The second proof computes $𝑑$ , and $𝑢$ and $𝑣$ as well, by repeated division.

Algorithm 7.1.46 (Euclidean algorithm)

Input: Polynomials $𝑝, 𝑠 \in 𝐹 [𝑥]$ with $𝑠 \neq 𝟎$ .
Output: $gcd (𝑝, 𝑠)$ .

Set

𝑟_{0} = 𝑝

and

𝑟_{1} = 𝑠

, and

𝑖 = 1

𝑟_{𝑖} = 𝟎

, output

𝑟_{𝑖 - 1}

divided by its leading coefficient, and stop.

Otherwise let

𝑟_{𝑖 + 1}

be the remainder of

𝑟_{𝑖 - 1}

on division by

𝑟_{𝑖}

, increase

𝑖

1

, and return to step 2.

Proof of Theorem 7.1.45 (by the Euclidean algorithm).hard

Uses. Theorem 7.1.14 (Division with remainder), Definition 7.1.44 (Greatest common divisor), Definition 7.1.16 (Divisibility)

Techniques. Algorithms as proofs: invariants and termination (Technique 3.3.5)

Hint 1. If

𝑠 = 𝟎

, the gcd is

𝑝

made monic. Otherwise run Algorithm 7.1.46. Why does it stop?

Hint 2. Find an invariant: compare the common divisors of

𝑟_{𝑖 - 1}

and

𝑟_{𝑖}

with those of

𝑟_{𝑖}

and

𝑟_{𝑖 + 1}

Hint 3. Show also by induction that every

𝑟_{𝑖}

is a combination

𝑢_{𝑖} 𝑝 + 𝑣_{𝑖} 𝑠

Sketch. The degrees

deg 𝑟_{1} > deg 𝑟_{2} > \dots

strictly decrease, so some

𝑟_{𝑁 + 1} = 𝟎

. Since

𝑟_{𝑖 + 1} =

𝑟_{𝑖 - 1} -

𝑞_{𝑖} 𝑟_{𝑖}

and

𝑟_{𝑖 - 1} =

𝑞_{𝑖} 𝑟_{𝑖} +

𝑟_{𝑖 + 1}

, the pairs

(𝑟_{𝑖 - 1}, 𝑟_{𝑖})

and

(𝑟_{𝑖}, 𝑟_{𝑖 + 1})

have the same common divisors. So the common divisors of

𝑝

and

𝑠

are those of

𝑟_{𝑁}

and

𝟎

, the divisors of

𝑟_{𝑁}

. Each

𝑟_{𝑖}

is a combination of

𝑝

and

𝑠

by induction. Making

𝑟_{𝑁}

monic gives

𝑑

; uniqueness is as in the first proof.

If $𝑠 = 𝟎$ , then $𝑝 \neq 𝟎$ , and the common divisors of $𝑝$ and $𝟎$ are the divisors of $𝑝$ . So $𝑝$ divided by its leading coefficient $𝑎$ is a greatest common divisor, and it equals $𝑎^{- 1} 𝑝 + 𝟎 𝑠$ . Now let $𝑠 \neq 𝟎$ and run Algorithm 7.1.46. Each $𝑟_{𝑖 + 1}$ is a remainder on division by $𝑟_{𝑖}$ , so $deg 𝑟_{𝑖 + 1} <$ $deg 𝑟_{𝑖}$ . A strictly decreasing sequence of nonnegative integers is finite, so some $𝑟_{𝑁 + 1} = 𝟎$ with $𝑟_{𝑁} \neq 𝟎$ , and the algorithm stops.

Invariant. Write $𝑟_{𝑖 - 1} =$ $𝑞_{𝑖} 𝑟_{𝑖} +$ $𝑟_{𝑖 + 1}$ . If $𝑒$ divides $𝑟_{𝑖 - 1}$ and $𝑟_{𝑖}$ , it divides $𝑟_{𝑖 + 1} =$ $𝑟_{𝑖 - 1} -$ $𝑞_{𝑖} 𝑟_{𝑖}$ ; if $𝑒$ divides $𝑟_{𝑖}$ and $𝑟_{𝑖 + 1}$ , it divides $𝑟_{𝑖 - 1}$ . So the pairs $(𝑟_{𝑖 - 1}, 𝑟_{𝑖})$ and $(𝑟_{𝑖}, 𝑟_{𝑖 + 1})$ have the same common divisors. Following the chain from $(𝑝, 𝑠) = (𝑟_{0}, 𝑟_{1})$ to $(𝑟_{𝑁}, 𝑟_{𝑁 + 1}) =$ $(𝑟_{𝑁}, 𝟎)$ , the common divisors of $𝑝$ and $𝑠$ are exactly the divisors of $𝑟_{𝑁}$ . In particular, with $𝑎$ the leading coefficient of $𝑟_{𝑁}$ , the monic polynomial $𝑑 = 𝑎^{- 1} 𝑟_{𝑁}$ divides $𝑝$ and $𝑠$ , and every common divisor divides $𝑑$ . So $𝑑$ is a greatest common divisor.

Combination. We show by induction on $𝑖$ that $𝑟_{𝑖} =$ $𝑢_{𝑖} 𝑝 +$ $𝑣_{𝑖} 𝑠$ for some $𝑢_{𝑖}, 𝑣_{𝑖}$ . This holds for $𝑟_{0} = 1 𝑝 + 𝟎 𝑠$ and $𝑟_{1} = 𝟎 𝑝 + 1 𝑠$ , and if it holds for $𝑟_{𝑖 - 1}$ and $𝑟_{𝑖}$ , then $𝑟_{𝑖 + 1} =$ $𝑟_{𝑖 - 1} -$ $𝑞_{𝑖} 𝑟_{𝑖} =$ $(𝑢_{𝑖 - 1} - 𝑞_{𝑖} 𝑢_{𝑖}) 𝑝 +$ $(𝑣_{𝑖 - 1} - 𝑞_{𝑖} 𝑣_{𝑖}) 𝑠$ . So $𝑑 =$ $𝑎^{- 1} 𝑢_{𝑁} 𝑝 +$ $𝑎^{- 1} 𝑣_{𝑁} 𝑠$ . Every nonzero combination $𝑢 𝑝 + 𝑣 𝑠$ is divisible by $𝑑$ , which divides $𝑝$ and $𝑠$ , so it has degree at least $deg 𝑑$ ; and a monic combination $𝑑^{'}$ of degree $deg 𝑑$ is divisible by $𝑑$ , so $𝑑^{'} = 𝑑$ (compare leading coefficients). Uniqueness of the gcd is proved as in the first proof. □

Example 7.1.47 (A greatest common divisor over $ℚ$ ). Let $𝑝 = 𝑥^{4} - 1$ and $𝑠 = 𝑥^{3} + 2 𝑥^{2} + 2 𝑥 + 1$ . The Euclidean algorithm, with $𝑟_{0} = 𝑝$ and $𝑟_{1} = 𝑠$ , gives

\begin{aligned} 𝑝 & = (𝑥 - 2) 𝑠 + 𝑟_{2}, & 𝑟_{2} & = 2 𝑥^{2} + 3 𝑥 + 1, \\ 𝑠 & = (\frac{1}{2} 𝑥 + \frac{1}{4}) 𝑟_{2} + 𝑟_{3}, & 𝑟_{3} & = \frac{3}{4} (𝑥 + 1), \\ 𝑟_{2} & = (\frac{8}{3} 𝑥 + \frac{4}{3}) 𝑟_{3} . \end{aligned}

The last nonzero remainder is $𝑟_{3} = \frac{3}{4} (𝑥 + 1)$ , so $gcd (𝑝, 𝑠) = 𝑥 + 1$ . Running the substitutions backwards, with $𝑟_{2} = 𝑝 - (𝑥 - 2) 𝑠$ and $𝑟_{3} =$ $𝑠 -$ $(\frac{1}{2} 𝑥 + \frac{1}{4}) 𝑟_{2}$ ,

𝑥 + 1 = \frac{4}{3} 𝑟_{3} = - (\frac{2}{3} 𝑥 + \frac{1}{3}) 𝑝 + (\frac{2}{3} 𝑥^{2} - 𝑥 + \frac{2}{3}) 𝑠 .

The factorizations $𝑝 =$ $(𝑥 - 1) (𝑥 + 1) (𝑥^{2} + 1)$ and $𝑠 =$ $(𝑥 + 1) (𝑥^{2} + 𝑥 + 1)$ confirm the answer.

Corollary 7.1.48 (Coprime polynomials). Let $𝑝, 𝑠 \in 𝐹 [𝑥]$ , not both $𝟎$ .

(a) $𝑝$ and $𝑠$ are coprime if and only if $𝑢 𝑝 + 𝑣 𝑠 = 1$ for some $𝑢, 𝑣 \in 𝐹 [𝑥]$ .
(b)If $𝐹 = ℂ$ , then $𝑝$ and $𝑠$ are coprime if and only if they have no common root.

Proof.standard

Uses. Theorem 7.1.45 (Bézout’s identity), Corollary 7.1.7 (No zero divisors, cancellation, and units), Theorem 7.1.20 (Factor theorem), Theorem 7.1.32 (Fundamental Theorem of Algebra)

Hint 1. For (a), “only if” is Theorem 7.1.45. For “if”, what can a common divisor of

𝑝

and

𝑠

be, if it divides

1

Hint 2. For (b), a common root

𝜆

gives the common factor

𝑥 - 𝜆

. Conversely, apply Theorem 7.1.32 to the gcd.

Sketch. (a) If

𝑝, 𝑠

are coprime, Bézout gives

𝑢 𝑝 + 𝑣 𝑠 = 1

. Conversely, every common divisor divides

𝑢 𝑝 + 𝑣 𝑠 = 1

, so it is a nonzero constant, and the monic gcd is

1

. (b) A common root

𝜆

makes

𝑥 - 𝜆

a common divisor of degree

1

, so the gcd is not

1

. If the gcd

𝑑

is not

1

, it is monic of degree at least

1

and has a root by Theorem 7.1.32, which is a root of

𝑝

and of

𝑠

(a) If $𝑝$ and $𝑠$ are coprime, Theorem 7.1.45 gives $𝑢 𝑝 +$ $𝑣 𝑠 =$ $gcd (𝑝, 𝑠) =$ $1$ . Conversely, suppose $𝑢 𝑝 + 𝑣 𝑠 = 1$ , and let $𝑑 = gcd (𝑝, 𝑠)$ . Then $𝑑$ divides $𝑢 𝑝 + 𝑣 𝑠 = 1$ , so $deg 𝑑 \leq 0$ , and $𝑑$ , being monic, is $1$ .

(b) If $𝜆$ is a common root, then $𝑥 - 𝜆$ divides $𝑝$ and $𝑠$ (Theorem 7.1.20), so it divides $gcd (𝑝, 𝑠)$ , which therefore has degree at least $1$ and is not $1$ . Conversely, if $𝑑 = gcd (𝑝, 𝑠) \neq 1$ , then $𝑑$ is monic of degree at least $1$ , since the only monic constant is $1$ . By Theorem 7.1.32, $𝑑$ has a root $𝜆 \in ℂ$ , and since $𝑑$ divides $𝑝$ and $𝑠$ , $𝜆$ is a root of both. □

Part (b) fails over $ℝ$ : $𝑥^{2} + 1$ and $𝑥^{4} - 1$ have no common real root, but their gcd is $𝑥^{2} + 1$ .

Exercises

Exercise 7.1.49.routine Let

𝑝 = 𝑥^{4} - 2 𝑥^{3} + 2 𝑥 - 1

. Factor

𝑝

into linear factors over

ℚ

, over

𝔽_{3}

, and over

𝔽_{2}

, and in each case list the roots of

𝑝

with their multiplicities.

Solution.

Uses. Theorem 7.1.20 (Factor theorem), Example 7.1.26 (Multiplicity depends on the field), Proposition 7.1.34 (Roots of a split polynomial)

Hint 1. Check that

1

is a root, and split off

𝑥 - 1

with Horner’s scheme.

Hint 2. The quotient is the polynomial of Example 7.1.26. The resulting identity has integer coefficients, so it can be read in

𝔽_{3}

and

𝔽_{2}

Sketch.

𝑝 =

(𝑥 - 1) (𝑥^{3} - 𝑥^{2} - 𝑥 + 1) =

{(𝑥 - 1)}^{3} (𝑥 + 1)

. Over

ℚ

1

with multiplicity

3

and

- 1

with multiplicity

1

. Over

𝔽_{3}

𝑥 + 1 = 𝑥 - 2

1

with multiplicity

3

and

2

with multiplicity

1

. Over

𝔽_{2}

𝑥 + 1 = 𝑥 - 1

1

with multiplicity

4

Since $𝑝 (1) = 1 - 2 + 2 - 1 = 0$ , Horner’s scheme with $𝑐 = 1$ applies to the coefficients $1, - 2, 0, 2, - 1$ : it gives $1$ , $- 2 + 1 = - 1$ , $0 - 1 = - 1$ , $2 - 1 = 1$ , and remainder $- 1 + 1 = 0$ . So $𝑝 =$ $(𝑥 - 1) (𝑥^{3} - 𝑥^{2} - 𝑥 + 1)$ , and by Example 7.1.26, $𝑥^{3} -$ $𝑥^{2} -$ $𝑥 +$ $1 =$ ${(𝑥 - 1)}^{2} (𝑥 + 1)$ . Hence

𝑝 = {(𝑥 - 1)}^{3} (𝑥 + 1) .

This identity was derived with integer arithmetic, so it holds over every field when the integers are read in that field. By Proposition 7.1.34, the roots and multiplicities can be read off from a factorization into linear factors.

Over $ℚ$ , the roots are $1$ , with multiplicity $3$ , and $- 1$ , with multiplicity $1$ . Over $𝔽_{3}$ , $𝑥 + 1 = 𝑥 - 2$ , so $𝑝 = {(𝑥 - 1)}^{3} (𝑥 - 2)$ : the roots are $1$ , with multiplicity $3$ , and $2$ , with multiplicity $1$ . Over $𝔽_{2}$ , $𝑥 + 1 = 𝑥 - 1$ , so $𝑝 = {(𝑥 - 1)}^{4}$ , and $1$ is the only root, with multiplicity $4$ . In each case the multiplicities add up to $4 = deg 𝑝$ .

Exercise 7.1.50.standard Over

ℚ

, find the remainder of

𝑥^{100}

on division by (a)

𝑥^{2} - 1

; (b)

𝑥^{2} + 1

; (c)

{(𝑥 - 1)}^{2}

Solution.

Uses. Theorem 7.1.14 (Division with remainder), Proposition 7.1.10 (Evaluation respects sums and products), Corollary 7.1.17 (Division does not depend on the field), Exercise 2.1.49

Hint 1. The remainder has the form

𝑎 𝑥 + 𝑏

. Evaluate

𝑥^{100} =

𝑠 𝑞 +

𝑎 𝑥 +

𝑏

at the roots of

𝑠

to get equations for

𝑎

and

𝑏

Hint 2. For (b), the roots

\pm 𝑖

are not rational. Why may you divide in

ℂ [𝑥]

instead? For (c), there is only one root; differentiate to get a second equation.

Sketch. (a) At

\pm 1

1 = 𝑎 + 𝑏

and

1 = - 𝑎 + 𝑏

, so the remainder is

1

. (b) Over

ℂ

, at

\pm 𝑖

𝑖^{100} = 1 = \pm 𝑎 𝑖 + 𝑏

, so the remainder is

1

; by Corollary 7.1.17 it is also the remainder over

ℚ

. (c) At

1

𝑎 + 𝑏 = 1

; differentiating,

100 𝑥^{99} =

2 (𝑥 - 1) 𝑞 +

{(𝑥 - 1)}^{2} 𝑞^{'} +

𝑎

, so

𝑎 = 100

and the remainder is

100 𝑥 - 99

In each case $𝑠$ has degree $2$ , so $𝑥^{100} =$ $𝑠 𝑞 +$ $𝑎 𝑥 +$ $𝑏$ for some $𝑞$ and some $𝑎, 𝑏 \in ℚ$ (Theorem 7.1.14). We evaluate with Proposition 7.1.10.

(a) With $𝑠 = 𝑥^{2} - 1$ , evaluating at $1$ and at $- 1$ gives $1 = 𝑎 + 𝑏$ and $1 = - 𝑎 + 𝑏$ . So $𝑎 = 0$ , $𝑏 = 1$ , and the remainder is $1$ .

(b) By Corollary 7.1.17, the quotient and remainder over $ℚ$ are also those over $ℂ$ , so we may evaluate at the complex roots $\pm 𝑖$ of $𝑥^{2} + 1$ . Since $𝑖^{4} = 1$ , ${(\pm 𝑖)}^{100} = 1$ , so $1 = 𝑎 𝑖 + 𝑏$ and $1 = - 𝑎 𝑖 + 𝑏$ . Adding and subtracting gives $𝑏 = 1$ and $𝑎 = 0$ . The remainder is $1$ .

(c) With $𝑠 = {(𝑥 - 1)}^{2}$ , evaluating at $1$ gives $1 = 𝑎 + 𝑏$ . To get a second equation, apply the formal derivative, using the product rule (Exercise 2.1.49):

100 𝑥^{99} = 2 (𝑥 - 1) 𝑞 + {(𝑥 - 1)}^{2} 𝑞^{'} + 𝑎 .

Evaluating at $1$ gives $100 = 𝑎$ , so $𝑏 = - 99$ , and the remainder is $100 𝑥 - 99$ .

Exercise 7.1.51.standard Let $𝑠 \in 𝐹 [𝑥]$ have degree $𝑚 \geq 1$ , let $𝑛 \geq 𝑚$ , and for $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ let $𝑅 (𝑝)$ be the remainder of $𝑝$ on division by $𝑠$ .

(a)Show that $𝑅 : {𝐹 [𝑥]}_{\leq 𝑛} \to$ ${𝐹 [𝑥]}_{\leq 𝑚 - 1}$ is linear.
(b)Show that $𝑅$ is surjective and that $ker 𝑅 =$ ${𝑠 𝑞 | 𝑞 \in {𝐹 [𝑥]}_{\leq 𝑛 - 𝑚}}$ .
(c)Verify the rank–nullity formula (Theorem 4.2.11) for $𝑅$ .

Solution.

Uses. Theorem 7.1.14 (Division with remainder), Proposition 1.2.18 (Degree and evaluation versus the operations), Proposition 7.1.4 (Degree of a product), Corollary 7.1.7 (No zero divisors, cancellation, and units), Theorem 4.2.11 (Rank–nullity), Example 4.1.7 (Dimensions of the standard spaces)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For (a), add two divisions

𝑝_{1} = 𝑠 𝑞_{1} + 𝑟_{1}

and

𝑝_{2} = 𝑠 𝑞_{2} + 𝑟_{2}

(one multiplied by

𝑐

), and use uniqueness in Theorem 7.1.14.

Hint 2. For (b), what is

𝑅 (𝑟)

when

deg 𝑟 < 𝑚

? For the kernel,

𝑅 (𝑝) = 𝟎

means

𝑠 ∣ 𝑝

; bound the degree of the quotient.

Hint 3. For (c),

𝑞 \mapsto 𝑠 𝑞

is an injective linear map from

{𝐹 [𝑥]}_{\leq 𝑛 - 𝑚}

onto

ker 𝑅

Sketch. (a)

𝑐 𝑝_{1} +

𝑝_{2} =

𝑠 (𝑐 𝑞_{1} + 𝑞_{2}) +

(𝑐 𝑟_{1} + 𝑟_{2})

with

deg (𝑐 𝑟_{1} + 𝑟_{2}) <

𝑚

, so by uniqueness

𝑅 (𝑐 𝑝_{1} + 𝑝_{2}) =

𝑐 𝑅 (𝑝_{1}) +

𝑅 (𝑝_{2})

. (b)

𝑅 (𝑟) = 𝑟

for

deg 𝑟 < 𝑚

𝑅 (𝑝) = 𝟎

iff

𝑝 = 𝑠 𝑞

, and then

deg 𝑞 =

deg 𝑝 -

𝑚 \leq

𝑛 -

𝑚

. (c)

dim ker 𝑅 = 𝑛 - 𝑚 + 1

and

dim im 𝑅 = 𝑚

add up to

𝑛 + 1

(a) Let $𝑝_{1}, 𝑝_{2} \in {𝐹 [𝑥]}_{\leq 𝑛}$ and $𝑐 \in 𝐹$ , with $𝑝_{1} = 𝑠 𝑞_{1} + 𝑟_{1}$ and $𝑝_{2} = 𝑠 𝑞_{2} + 𝑟_{2}$ , where $𝑟_{𝑖} = 𝑅 (𝑝_{𝑖})$ . Then

𝑐 𝑝_{1} + 𝑝_{2} = 𝑠 (𝑐 𝑞_{1} + 𝑞_{2}) + (𝑐 𝑟_{1} + 𝑟_{2}),

and $deg (𝑐 𝑟_{1} + 𝑟_{2}) <$ $𝑚$ by Proposition 1.2.18. By the uniqueness in Theorem 7.1.14, $𝑅 (𝑐 𝑝_{1} + 𝑝_{2}) =$ $𝑐 𝑟_{1} +$ $𝑟_{2} =$ $𝑐 𝑅 (𝑝_{1}) +$ $𝑅 (𝑝_{2})$ .

(b) If $deg 𝑟 \leq 𝑚 - 1$ , then $𝑟 = 𝑠 \cdot 𝟎 + 𝑟$ , so $𝑅 (𝑟) = 𝑟$ ; thus $𝑅$ is surjective onto ${𝐹 [𝑥]}_{\leq 𝑚 - 1}$ (note $𝑚 - 1 \leq 𝑛$ ). Next, $𝑅 (𝑝) = 𝟎$ if and only if $𝑝 = 𝑠 𝑞$ for some $𝑞$ . If $𝑝 = 𝑠 𝑞 \neq 𝟎$ has degree at most $𝑛$ , then $deg 𝑞 =$ $deg 𝑝 -$ $𝑚 \leq$ $𝑛 -$ $𝑚$ by Proposition 7.1.4. Conversely, if $deg 𝑞 \leq 𝑛 - 𝑚$ , then $deg (𝑠 𝑞) \leq 𝑛$ and $𝑅 (𝑠 𝑞) = 𝟎$ . So $ker 𝑅 =$ ${𝑠 𝑞 | 𝑞 \in {𝐹 [𝑥]}_{\leq 𝑛 - 𝑚}}$ .

(c) The map $𝑞 \mapsto 𝑠 𝑞$ from ${𝐹 [𝑥]}_{\leq 𝑛 - 𝑚}$ to $ker 𝑅$ is linear, onto by (b), and injective by Corollary 7.1.7(b). So $dim ker 𝑅 =$ $dim {𝐹 [𝑥]}_{\leq 𝑛 - 𝑚} =$ $𝑛 -$ $𝑚 +$ $1$ (Example 4.1.7), while $dim im 𝑅 =$ $dim {𝐹 [𝑥]}_{\leq 𝑚 - 1} =$ $𝑚$ . Their sum is $𝑛 + 1 = dim {𝐹 [𝑥]}_{\leq 𝑛}$ , as Theorem 4.2.11 requires.

Exercise 7.1.52.standard The definitions of this section make sense with coefficients in $ℤ / 8 ℤ$ , which is a commutative ring but not a field (Lemma 1.1.21).

(a)Show that $𝑥^{2} - 1$ has four roots in $ℤ / 8 ℤ$ , and that $𝑥^{2} -$ $1 =$ $(𝑥 - 1) (𝑥 + 1) =$ $(𝑥 - 3) (𝑥 + 3)$ in $(ℤ / 8 ℤ) [𝑥]$ .
(b)The proof of Proposition 7.1.22, run over $ℤ / 8 ℤ$ , would show that $𝑥^{2} - 1$ has at most two roots. Find the first step that fails.

Solution.

Uses. Proposition 7.1.22 (Counting roots), Proposition 1.1.17 (No zero divisors), Definition 1.1.19 (Integers modulo $𝑛$ )

Hint 1. Square each odd residue modulo

8

Hint 2. Follow the proof with

𝑐_{1} = 1

and

𝑐_{2} = 3

. After splitting off

𝑥 - 1

, what is

𝑞

, and what is

𝑞 (3)

Sketch. (a)

1^{2}, 3^{2}, 5^{2}, 7^{2}

are all

1

modulo

8

, and

(𝑥 - 3) (𝑥 + 3) =

𝑥^{2} -

9 =

𝑥^{2} -

1

. (b) With

𝑐_{1} = 1

𝑞 = 𝑥 + 1

, and

𝑝 (3) =

(3 - 1) 𝑞 (3) =

2 \cdot

4 =

0

although

𝑞 (3) = 4 \neq 0

. The step “the product of the differences is nonzero, so

𝑞 (𝑐_{𝑘}) = 0

” uses Proposition 1.1.17, which fails in

ℤ / 8 ℤ

(a) Modulo $8$ , $1^{2} = 1$ , $3^{2} = 9 = 1$ , $5^{2} = 25 = 1$ , and $7^{2} = 49 = 1$ , so $1, 3, 5, 7$ are roots of $𝑥^{2} - 1$ . Also $(𝑥 - 3) (𝑥 + 3) =$ $𝑥^{2} -$ $9 =$ $𝑥^{2} -$ $1$ , since $9 = 1$ in $ℤ / 8 ℤ$ . So $𝑥^{2} - 1$ has two different factorizations into monic linear factors.

(b) Take $𝑐_{1} = 1$ and $𝑐_{2} = 3$ . The factor theorem still holds, because dividing by the monic polynomial $𝑥 - 1$ never requires inverting a scalar, and it gives $𝑥^{2} - 1 = (𝑥 - 1) 𝑞$ with $𝑞 = 𝑥 + 1$ . The proof then evaluates at $𝑐_{2} = 3$ :

0 = 𝑝 (3) = (3 - 1) 𝑞 (3) = 2 \cdot 4 .

The next step concludes $𝑞 (3) = 0$ because $𝑐_{2} - 𝑐_{1} = 2$ is nonzero, using Proposition 1.1.17. In $ℤ / 8 ℤ$ this is false: $2 \cdot 4 = 0$ while $2 \neq 0$ and $𝑞 (3) = 4 \neq 0$ . That is the step that fails. (The degree formula of Proposition 7.1.4 also fails over $ℤ / 8 ℤ$ , for instance $(4 𝑥 + 1) (2 𝑥 + 1) =$ $6 𝑥 +$ $1$ , but the proof only uses it for monic factors, where it still holds.)

Exercise 7.1.53.standard Prove or disprove, for $𝑝, 𝑞, 𝑟 \in 𝐹 [𝑥]$ .

(a)If $𝑝 (𝑐) = 𝑞 (𝑐)$ for every $𝑐 \in 𝐹$ , then $𝑝 = 𝑞$ .
(b)If $𝑝 ∣ 𝑞$ and $𝑞 ∣ 𝑝$ , then $𝑝 = 𝑞$ .
(c)If $𝑝 ∣ 𝑞 𝑟$ , then $𝑝 ∣ 𝑞$ or $𝑝 ∣ 𝑟$ .
(d)If $𝑝 \in ℝ [𝑥]$ has no real root, then $deg 𝑝$ is even.
(e)If $𝑝 \in ℝ [𝑥]$ is nonzero, then the number of real roots of $𝑝$ , counted with multiplicity, has the same parity as $deg 𝑝$ .

Solution.

Uses. Corollary 7.1.23 (Polynomials and their values), Definition 7.1.16 (Divisibility), Corollary 7.1.43 (Odd degree gives a real root), Theorem 7.1.39 (Factorization over $ℝ$ )

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18), Try small cases and small fields (Technique 1.2.38)

Hint 1. Try small fields for (a), constants for (b), and repeated factors for (c).

Hint 2. For (d) and (e), use Theorem 7.1.39. What does it say about the number of real roots counted with multiplicity?

Sketch. (a) False over

𝔽_{2}

𝑥^{2} + 𝑥

and

𝟎

; true over infinite fields. (b) False:

𝑥

and

2 𝑥

over

ℚ

; true for monic polynomials. (c) False:

𝑥^{2} ∣ 𝑥 \cdot 𝑥

. (d) True by Corollary 7.1.43 (a polynomial with no real root is nonzero). (e) True: in Theorem 7.1.39,

𝑘

counts the real roots with multiplicity and

𝑘 + 2 𝑙 = deg 𝑝

(a) False. Over $𝔽_{2}$ , $𝑥^{2} + 𝑥$ and $𝟎$ both vanish at $0$ and $1$ (Aside (Polynomials versus polynomial functions)). It is true when $𝐹$ is infinite, by Corollary 7.1.23(b).

(b) False. Over $ℚ$ , $𝑥 ∣ 2 𝑥$ and $2 𝑥 ∣ 𝑥$ , since $𝑥 = \frac{1}{2} \cdot 2 𝑥$ . Polynomials that divide each other differ by a nonzero constant factor, so the statement is true if $𝑝$ and $𝑞$ are monic (see the remarks after Definition 7.1.16).

(c) False. $𝑥^{2}$ divides $𝑥 \cdot 𝑥$ but not $𝑥$ , by degrees. It is true when $𝑝$ is irreducible (Exercise 7.1.68).

(d) True. A polynomial with no real root is nonzero, since every real number is a root of $𝟎$ . If its degree were odd, it would have a real root by Corollary 7.1.43. So its degree is even (possibly $0$ ).

(e) True. In Theorem 7.1.39, $𝜆_{1}, \dots, 𝜆_{𝑘}$ are the real roots of $𝑝$ listed with multiplicity, so the number of real roots counted with multiplicity is $𝑘 = deg 𝑝 - 2 𝑙$ , which has the parity of $deg 𝑝$ .

Exercise 7.1.54.standard

(a)Let $𝑛 \geq 1$ . Show that $𝑥^{𝑛} - 1$ has $𝑛$ distinct roots in $ℂ$ .
(b)Let $𝑝$ be a prime. Show that $𝑥^{𝑝} - 1 = {(𝑥 - 1)}^{𝑝}$ in $𝔽_{𝑝} [𝑥]$ , so that $1$ is the only root of $𝑥^{𝑝} - 1$ in $𝔽_{𝑝}$ , with multiplicity $𝑝$ .

Solution.

Uses. Exercise 7.1.28, Corollary 7.1.35 (Factorization over $ℂ$ ), Proposition 7.1.34 (Roots of a split polynomial), the binomial theorem in a commutative ring

Hint 1. For (a), use Exercise 7.1.28: can

𝑥^{𝑛} - 1

and its derivative have a common root?

Hint 2. For (b), expand

{(𝑥 - 1)}^{𝑝}

with the binomial theorem. Which binomial coefficients

(\binom{𝑝}{𝑘})

are divisible by

𝑝

Sketch. (a) A repeated root

𝑐

would satisfy

𝑐^{𝑛} = 1

and

𝑛 𝑐^{𝑛 - 1} = 0

, which forces

𝑐 = 0

, but

0^{𝑛} \neq 1

. So all

𝑛

roots given by Corollary 7.1.35 are simple, hence distinct. (b) For

0 < 𝑘 < 𝑝

𝑝

divides

(\binom{𝑝}{𝑘}) =

𝑝! / (𝑘! (𝑝 - 𝑘)!)

, so

{(𝑥 - 1)}^{𝑝} =

𝑥^{𝑝} +

{(- 1)}^{𝑝} =

𝑥^{𝑝} -

1

𝔽_{𝑝} [𝑥]

(also for

𝑝 = 2

, where

1 = - 1

(a) The derivative of $𝑓 = 𝑥^{𝑛} - 1$ is $𝑓^{'} = 𝑛 𝑥^{𝑛 - 1}$ , where $𝑛 = 1 + \dots + 1 \neq 0$ in $ℂ$ . If $𝑐$ were a repeated root of $𝑓$ , then $𝑓^{'} (𝑐) =$ $𝑛 𝑐^{𝑛 - 1} =$ $0$ by Exercise 7.1.28. For $𝑛 = 1$ this is impossible, as $𝑓^{'} = 1$ ; for $𝑛 \geq 2$ it forces $𝑐 = 0$ , but $𝑓 (0) = - 1 \neq 0$ . So every root of $𝑓$ is simple. By Corollary 7.1.35, $𝑓$ has $𝑛$ roots counted with multiplicity, and since each multiplicity is $1$ , these are $𝑛$ distinct roots.

(b) $𝔽_{𝑝} [𝑥]$ is a commutative ring, so the binomial theorem holds there, with the usual inductive proof:

{(𝑥 - 1)}^{𝑝} = \sum_{𝑘 = 0}^{𝑝} (\binom{𝑝}{𝑘}) {(- 1)}^{𝑝 - 𝑘} 𝑥^{𝑘} .

For $0 < 𝑘 < 𝑝$ , the integer $(\binom{𝑝}{𝑘}) =$ $𝑝! / (𝑘! (𝑝 - 𝑘)!)$ is divisible by $𝑝$ , because the prime $𝑝$ divides the numerator but none of the factors $1, \dots, 𝑘$ and $1, \dots, 𝑝 - 𝑘$ of the denominator. So these coefficients are $0$ in $𝔽_{𝑝}$ , and ${(𝑥 - 1)}^{𝑝} =$ $𝑥^{𝑝} +$ ${(- 1)}^{𝑝}$ . For odd $𝑝$ , ${(- 1)}^{𝑝} = - 1$ , and for $𝑝 = 2$ , ${(- 1)}^{2} = 1 = - 1$ in $𝔽_{2}$ . Hence ${(𝑥 - 1)}^{𝑝} = 𝑥^{𝑝} - 1$ , and by Proposition 7.1.34, $1$ is the only root, with multiplicity $𝑝$ . The test of Exercise 7.1.28 does not separate roots here, since the derivative $𝑝 𝑥^{𝑝 - 1}$ is $𝟎$ in $𝔽_{𝑝} [𝑥]$ .

Exercise 7.1.55.hard Let $𝑝$ be a prime.

(a)Show that $𝑥^{𝑝} -$ $𝑥 =$ $\prod_{𝑎 \in 𝔽_{𝑝}} (𝑥 - 𝑎)$ in $𝔽_{𝑝} [𝑥]$ .
(b)Deduce Wilson’s theorem: $(𝑝 - 1)! \equiv - 1 (mod 𝑝)$ .

Solution.

Uses. Exercise 1.1.51, Proposition 7.1.22 (Counting roots), Proposition 7.1.4 (Degree of a product), Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 7.1.10 (Evaluation respects sums and products), Lemma 1.1.21 (Arithmetic in $ℤ / 𝑛 ℤ$ )

Techniques. Compare degrees and leading coefficients (Technique 7.1.6)

Hint 1. By Fermat’s little theorem (Exercise 1.1.51), every

𝑎 \in 𝔽_{𝑝}

is a root of

𝑥^{𝑝} - 𝑥

. What does Proposition 7.1.22 then say?

Hint 2. Both sides of (a) are monic of degree

𝑝

, and one divides the other.

Hint 3. For (b), cancel the factor

𝑥

from both sides of (a) and compare constant terms.

Sketch. Each

𝑎 \in 𝔽_{𝑝}

is a root of

𝑥^{𝑝} - 𝑥

(for

𝑎 \neq 0

𝑎^{𝑝 - 1} = 1

), so

𝜔 = \prod_{𝑎} (𝑥 - 𝑎)

divides

𝑥^{𝑝} - 𝑥

by Proposition 7.1.22. Both are monic of degree

𝑝

, so the quotient is

1

. Cancelling

𝑥

gives

𝑥^{𝑝 - 1} -

1 =

\prod_{𝑎 \neq 0} (𝑥 - 𝑎)

; at

0

this reads

- 1 =

{(- 1)}^{𝑝 - 1} (𝑝 - 1)!

𝔽_{𝑝}

, and

{(- 1)}^{𝑝 - 1} = 1

for odd

𝑝

, while

𝑝 = 2

is checked directly.

(a) Every $𝑎 \in 𝔽_{𝑝}$ is a root of $𝑥^{𝑝} - 𝑥$ : for $𝑎 = 0$ this is clear, and for $𝑎 \neq 0$ , $𝑎^{𝑝 - 1} = 1$ by Exercise 1.1.51, so $𝑎^{𝑝} = 𝑎$ . The $𝑝$ elements of $𝔽_{𝑝}$ are distinct roots, so by Proposition 7.1.22, $𝜔 =$ $\prod_{𝑎 \in 𝔽_{𝑝}} (𝑥 - 𝑎)$ divides $𝑥^{𝑝} - 𝑥$ , say $𝑥^{𝑝} - 𝑥 = 𝜔 ℎ$ . Both $𝜔$ and $𝑥^{𝑝} - 𝑥$ are monic of degree $𝑝$ , so by Proposition 7.1.4 $ℎ$ has degree $0$ and leading coefficient $1$ , that is, $ℎ = 1$ .

(b) Write $𝜔 = 𝑥 \prod_{𝑎 \neq 0} (𝑥 - 𝑎)$ and $𝑥^{𝑝} -$ $𝑥 =$ $𝑥 (𝑥^{𝑝 - 1} - 1)$ . Cancelling $𝑥$ (Corollary 7.1.7(b)) gives

𝑥^{𝑝 - 1} - 1 = \prod_{𝑎 \in 𝔽_{𝑝}, 𝑎 \neq 0} (𝑥 - 𝑎) .

Evaluating at $0$ (Proposition 7.1.10), $- 1 =$ $\prod_{𝑎 \neq 0} (- 𝑎) =$ ${(- 1)}^{𝑝 - 1} \cdot$ $(1 \cdot 2 \dots (𝑝 - 1))$ , where the product is computed in $𝔽_{𝑝}$ , so it is $(𝑝 - 1)! mod 𝑝$ (Lemma 1.1.21). If $𝑝$ is odd, ${(- 1)}^{𝑝 - 1} = 1$ , so $(𝑝 - 1)! \equiv - 1 (mod 𝑝)$ . If $𝑝 = 2$ , then $(𝑝 - 1)! =$ $1 \equiv$ $- 1 (mod 2)$ directly.

Exercise 7.1.56.standard Consider $𝑓 \in 𝐹 [𝑥]$ with $𝑓 (𝑥 + 1) = 𝑓$ .

(a)Show that if $𝐹$ has characteristic $0$ (Definition 1.1.28), then $𝑓$ is constant.
(b)Let $𝑝$ be a prime. Find a nonconstant $𝑓 \in 𝔽_{𝑝} [𝑥]$ with $𝑓 (𝑥 + 1) = 𝑓$ .

Solution.

Uses. Corollary 7.1.12 (Substituting twice), Definition 1.1.28 (Characteristic), Corollary 7.1.23 (Polynomials and their values), Exercise 7.1.55, Proposition 7.1.10 (Evaluation respects sums and products)

Hint 1. Evaluate

𝑓 (𝑥 + 1) = 𝑓

𝑡 \in 𝐹

with Corollary 7.1.12. What does this say about

𝑓 (0),

𝑓 (1),

𝑓 (1 + 1),

\dots

Hint 2. In characteristic

0

, the elements

𝑘 \cdot 1

for

𝑘 = 0, 1, 2, \dots

are distinct. For (b), substitute

𝑥 + 1

into the factorization of Exercise 7.1.55.

Sketch. (a)

𝑓 (𝑡 + 1) = 𝑓 (𝑡)

for all

𝑡

, so

𝑓 (𝑘 \cdot 1) = 𝑓 (0)

for all

𝑘 \geq 0

. In characteristic

0

these are infinitely many distinct points, so

𝑓 - 𝑓 (0)

𝟎

. (b)

𝑓 =

𝑥^{𝑝} -

𝑥 =

\prod_{𝑎} (𝑥 - 𝑎)

; substituting

𝑥 + 1

gives

\prod_{𝑎} (𝑥 - (𝑎 - 1))

, the same product reordered.

(a) By Corollary 7.1.12 with $𝑟 = 𝑥 + 1$ , for every $𝑡 \in 𝐹$ we have $𝑓 (𝑡 + 1) =$ $(𝑓 (𝑥 + 1)) (𝑡) =$ $𝑓 (𝑡)$ . By induction, $𝑓 (𝑘 \cdot 1) = 𝑓 (0)$ for every integer $𝑘 \geq 0$ , where $𝑘 \cdot 1 = 1 + \dots + 1$ . In characteristic $0$ these elements are distinct: if $𝑗 \cdot 1 = 𝑘 \cdot 1$ with $𝑗 < 𝑘$ , then $(𝑘 - 𝑗) \cdot 1 = 0$ with $𝑘 - 𝑗 \geq 1$ , which is impossible by Definition 1.1.28. So $𝑓 - 𝑓 (0)$ has infinitely many roots, hence $𝑓 - 𝑓 (0) = 𝟎$ by Corollary 7.1.23(b), and $𝑓$ is the constant $𝑓 (0)$ .

(b) Let $𝑓 = 𝑥^{𝑝} - 𝑥$ , which has degree $𝑝 \geq 2$ . By Exercise 7.1.55, $𝑓 =$ $\prod_{𝑎 \in 𝔽_{𝑝}} (𝑥 - 𝑎)$ . Substituting $𝑥 + 1$ and using Proposition 7.1.10 for the product,

\begin{aligned} 𝑓 (𝑥 + 1) & = \prod_{𝑎 \in 𝔽_{𝑝}} (𝑥 + 1 - 𝑎) = \prod_{𝑎 \in 𝔽_{𝑝}} (𝑥 - (𝑎 - 1)) \\ = \prod_{𝑏 \in 𝔽_{𝑝}} (𝑥 - 𝑏) = 𝑓, \end{aligned}

because $𝑎 \mapsto 𝑎 - 1$ is a bijection of $𝔽_{𝑝}$ , so the last two products have the same factors in a different order. (Alternatively, ${(𝑥 + 1)}^{𝑝} = 𝑥^{𝑝} + 1$ in $𝔽_{𝑝} [𝑥]$ by the binomial argument of Exercise 7.1.54.)

Exercise 7.1.57.standard Let $𝑎, 𝑏, 𝑐, 𝑑 \in 𝐹$ .

(a)Show that there is exactly one $𝑓 \in {𝐹 [𝑥]}_{\leq 3}$ with $𝑓 (0) = 𝑎$ , $𝑓^{'} (0) = 𝑏$ , $𝑓 (1) = 𝑐$ , and $𝑓^{'} (1) = 𝑑$ , where $𝑓^{'}$ is the formal derivative.
(b)Find $𝑓$ over $ℚ$ for $(𝑎, 𝑏, 𝑐, 𝑑) =$ $(1, 0, 0, 0)$ .

Solution.

Uses. Exercise 7.1.28, Proposition 7.1.27 (Multiplicities add up to at most the degree), Corollary 4.2.18 (Injective if and only if surjective), Example 2.1.9 (Maps of polynomials), Example 4.1.7 (Dimensions of the standard spaces)

Techniques. Uniqueness gives existence (Technique 3.4.21), Dimension counting (Technique 4.2.24)

Hint 1. The map

𝑓 \mapsto

(𝑓 (0), 𝑓^{'} (0), 𝑓 (1), 𝑓^{'} (1))

from

{𝐹 [𝑥]}_{\leq 3}

𝐹^{4}

is linear, and both spaces have dimension

4

. So it is enough to show that it is injective.

Hint 2. If all four values are

0

, then

0

and

1

are repeated roots of

𝑓

(Exercise 7.1.28). Count multiplicities.

Hint 3. For (b),

1

is a repeated root, so

𝑓 =

{(𝑥 - 1)}^{2} (𝑢 𝑥 + 𝑣)

Sketch. The map

𝑇 (𝑓) =

(𝑓 (0), 𝑓^{'} (0), 𝑓 (1), 𝑓^{'} (1))

is linear from a

4

-dimensional space to

𝐹^{4}

. If

𝑇 (𝑓) = 𝟎

and

𝑓 \neq 𝟎

, then

0

and

1

are roots of multiplicity at least

2

, so

4 \leq deg 𝑓 \leq 3

by Proposition 7.1.27, which is impossible. So

𝑇

is injective, hence bijective. For (b),

𝑓 =

{(𝑥 - 1)}^{2} (𝑢 𝑥 + 𝑣)

with

𝑣 = 1

and

𝑢 - 2 𝑣 = 0

, so

𝑓 =

{(𝑥 - 1)}^{2} (2 𝑥 + 1) =

2 𝑥^{3} -

3 𝑥^{2} +

1

(a) Let $𝑇 : {𝐹 [𝑥]}_{\leq 3} \to 𝐹^{4}$ , $𝑇 (𝑓) =$ $(𝑓 (0), 𝑓^{'} (0), 𝑓 (1), 𝑓^{'} (1))$ . Evaluation and the formal derivative are linear (Example 2.1.9), so $𝑇$ is linear. Suppose $𝑇 (𝑓) = 𝟎$ and $𝑓 \neq 𝟎$ . By Exercise 7.1.28, $0$ and $1$ are repeated roots of $𝑓$ , so each has multiplicity at least $2$ , and Proposition 7.1.27 gives $2 + 2 \leq deg 𝑓 \leq 3$ , which is impossible. So $ker 𝑇 = {𝟎}$ , and $𝑇$ is injective. Since $dim {𝐹 [𝑥]}_{\leq 3} =$ $4 =$ $dim 𝐹^{4}$ (Example 4.1.7), $𝑇$ is bijective by Corollary 4.2.18. So each $(𝑎, 𝑏, 𝑐, 𝑑)$ is $𝑇 (𝑓)$ for exactly one $𝑓$ .

(b) Here $𝑓 (1) = 𝑓^{'} (1) = 0$ , so $1$ is a repeated root (or $𝑓 = 𝟎$ , which is excluded by $𝑓 (0) = 1$ ), and ${(𝑥 - 1)}^{2}$ divides $𝑓$ . Since $deg 𝑓 \leq 3$ , $𝑓 =$ ${(𝑥 - 1)}^{2} (𝑢 𝑥 + 𝑣)$ for some $𝑢, 𝑣 \in ℚ$ . Then $𝑓 (0) = 𝑣 = 1$ , and by the product rule $𝑓^{'} =$ $2 (𝑥 - 1) (𝑢 𝑥 + 𝑣) +$ $𝑢 {(𝑥 - 1)}^{2}$ , so $𝑓^{'} (0) = - 2 𝑣 + 𝑢 = 0$ and $𝑢 = 2$ . Hence

𝑓 = {(𝑥 - 1)}^{2} (2 𝑥 + 1) = 2 𝑥^{3} - 3 𝑥^{2} + 1 .

Check: $𝑓 (0) = 1$ , $𝑓 (1) = 0$ , and $𝑓^{'} = 6 𝑥^{2} - 6 𝑥$ vanishes at $0$ and $1$ .

Exercise 7.1.58.standard Let $𝑛 \geq 1$ , let $𝑐_{0}, \dots, 𝑐_{𝑛} \in 𝐹$ be distinct, let $𝐿_{0}, \dots, 𝐿_{𝑛}$ be the Lagrange polynomials (Definition 3.4.26), and let $𝜔 =$ $(𝑥 - 𝑐_{0}) \dots (𝑥 - 𝑐_{𝑛})$ .

(a)Show that $𝐿_{0} + 𝐿_{1} + \dots + 𝐿_{𝑛} = 1$ and $𝑐_{0} 𝐿_{0} +$ $𝑐_{1} 𝐿_{1} +$ $\dots +$ $𝑐_{𝑛} 𝐿_{𝑛} =$ $𝑥$ .
(b)Show that $𝜔^{'} (𝑐_{𝑖}) =$ $\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})$ , and deduce that $𝐿_{𝑖} =$ $𝜔_{𝑖} / 𝜔^{'} (𝑐_{𝑖})$ , where $𝜔_{𝑖} =$ $\prod_{𝑗 \neq 𝑖} (𝑥 - 𝑐_{𝑗})$ .

Solution.

Uses. Proposition 3.4.27 (Lagrange’s formula), Theorem 3.4.24 (Polynomial interpolation), Proposition 7.1.29 (Lagrange polynomials in closed form), Exercise 2.1.49, Proposition 7.1.10 (Evaluation respects sums and products)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. For (a), both sides of each identity have degree at most

𝑛

. Compare their values at the nodes.

Hint 2. For (b), write

𝜔 = (𝑥 - 𝑐_{𝑖}) 𝜔_{𝑖}

and differentiate with the product rule.

Sketch. (a) By Proposition 3.4.27,

\sum_{𝑖} 𝑑_{𝑖} 𝐿_{𝑖}

is the interpolant of the values

𝑑_{𝑖}

. The constant

1

and the polynomial

𝑥

(of degree

1 \leq 𝑛

) interpolate the values

1

and

𝑐_{𝑖}

, so they equal

\sum_{𝑖} 𝐿_{𝑖}

and

\sum_{𝑖} 𝑐_{𝑖} 𝐿_{𝑖}

. (b)

𝜔^{'} =

𝜔_{𝑖} +

(𝑥 - 𝑐_{𝑖}) 𝜔_{𝑖^{'}}

, so

𝜔^{'} (𝑐_{𝑖}) =

𝜔_{𝑖} (𝑐_{𝑖}) =

\prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗})

, and Proposition 7.1.29 gives

𝐿_{𝑖} =

𝜔_{𝑖} / 𝜔^{'} (𝑐_{𝑖})

(a) By Proposition 3.4.27, for any values $𝑑_{0}, \dots, 𝑑_{𝑛}$ , the polynomial $\sum_{𝑖} 𝑑_{𝑖} 𝐿_{𝑖}$ is the unique element of ${𝐹 [𝑥]}_{\leq 𝑛}$ taking the value $𝑑_{𝑘}$ at $𝑐_{𝑘}$ . The constant polynomial $1$ lies in ${𝐹 [𝑥]}_{\leq 𝑛}$ and takes the value $1$ at every node, so $\sum_{𝑖} 𝐿_{𝑖} = 1$ . Since $𝑛 \geq 1$ , the polynomial $𝑥$ lies in ${𝐹 [𝑥]}_{\leq 𝑛}$ and takes the value $𝑐_{𝑘}$ at $𝑐_{𝑘}$ , so $\sum_{𝑖} 𝑐_{𝑖} 𝐿_{𝑖} = 𝑥$ .

(b) Write $𝜔 = (𝑥 - 𝑐_{𝑖}) 𝜔_{𝑖}$ . By the product rule (Exercise 2.1.49), $𝜔^{'} =$ $𝜔_{𝑖} +$ $(𝑥 - 𝑐_{𝑖}) 𝜔_{𝑖^{'}}$ , so by Proposition 7.1.10

𝜔^{'} (𝑐_{𝑖}) = 𝜔_{𝑖} (𝑐_{𝑖}) + 0 = \prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗}) .

This is nonzero, and by Proposition 7.1.29, $𝐿_{𝑖} =$ $𝜔_{𝑖} / \prod_{𝑗 \neq 𝑖} (𝑐_{𝑖} - 𝑐_{𝑗}) =$ $𝜔_{𝑖} / 𝜔^{'} (𝑐_{𝑖})$ .

Exercise 7.1.59.routine Let $𝜆_{1}, 𝜆_{2}, 𝜆_{3}$ be the roots of $𝑥^{3} - 2 𝑥 + 5$ in $ℂ$ , listed with multiplicity.

(a)Expand $(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) (𝑥 - 𝜆_{3})$ .
(b)Compute $𝜆_{1} + 𝜆_{2} + 𝜆_{3}$ , $𝜆_{1} 𝜆_{2} +$ $𝜆_{1} 𝜆_{3} +$ $𝜆_{2} 𝜆_{3}$ , $𝜆_{1} 𝜆_{2} 𝜆_{3}$ , and $𝜆_{1}^{2} + 𝜆_{2}^{2} + 𝜆_{3}^{2}$ .

Solution.

Uses. Corollary 7.1.35 (Factorization over $ℂ$ ), Proposition 7.1.36 (Sum and product of the roots)

Hint 1. Multiply out one factor at a time.

Hint 2. By Corollary 7.1.35,

𝑥^{3} -

2 𝑥 +

5 =

(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) (𝑥 - 𝜆_{3})

. Compare coefficients. For the last sum, square

𝜆_{1} + 𝜆_{2} + 𝜆_{3}

Sketch. (a)

𝑥^{3} -

𝑒_{1} 𝑥^{2} +

𝑒_{2} 𝑥 -

𝑒_{3}

with

𝑒_{1} = \sum 𝜆_{𝑖}

𝑒_{2} =

\sum_{𝑖 < 𝑗} 𝜆_{𝑖} 𝜆_{𝑗}

𝑒_{3} = 𝜆_{1} 𝜆_{2} 𝜆_{3}

. (b) Comparing with

𝑥^{3} - 2 𝑥 + 5

𝑒_{1} = 0

𝑒_{2} = - 2

𝑒_{3} = - 5

, and

\sum 𝜆_{𝑖}^{2} =

𝑒_{1}^{2} -

2 𝑒_{2} =

4

(a) First $(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) =$ $𝑥^{2} -$ $(𝜆_{1} + 𝜆_{2}) 𝑥 +$ $𝜆_{1} 𝜆_{2}$ . Multiplying by $𝑥 - 𝜆_{3}$ ,

(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) (𝑥 - 𝜆_{3}) = 𝑥^{3} - 𝑒_{1} 𝑥^{2} + 𝑒_{2} 𝑥 - 𝑒_{3},

where $𝑒_{1} = 𝜆_{1} + 𝜆_{2} + 𝜆_{3}$ , $𝑒_{2} =$ $𝜆_{1} 𝜆_{2} +$ $𝜆_{1} 𝜆_{3} +$ $𝜆_{2} 𝜆_{3}$ , and $𝑒_{3} = 𝜆_{1} 𝜆_{2} 𝜆_{3}$ . The first and last agree with Proposition 7.1.36.

(b) By Corollary 7.1.35, $𝑥^{3} -$ $2 𝑥 +$ $5 =$ $(𝑥 - 𝜆_{1}) (𝑥 - 𝜆_{2}) (𝑥 - 𝜆_{3})$ , so comparing coefficients with (a) gives $𝑒_{1} = 0$ , $𝑒_{2} = - 2$ , and $- 𝑒_{3} = 5$ , that is, $𝑒_{3} = - 5$ . Finally, expanding the square gives $𝑒_{1}^{2} =$ $𝜆_{1}^{2} +$ $𝜆_{2}^{2} +$ $𝜆_{3}^{2} +$ $2 𝑒_{2}$ , so

𝜆_{1}^{2} + 𝜆_{2}^{2} + 𝜆_{3}^{2} = 𝑒_{1}^{2} - 2 𝑒_{2} = 0 - 2 (- 2) = 4 .

Exercise 7.1.60.standard Factor

𝑥^{4} + 1

and

𝑥^{6} - 1

into irreducible polynomials over

ℂ

and over

ℝ

Solution.

Uses. Corollary 7.1.35 (Factorization over $ℂ$ ), Theorem 7.1.39 (Factorization over $ℝ$ ), Corollary 7.1.42 (Irreducible polynomials over $ℂ$ and $ℝ$ ), Proposition 7.1.34 (Roots of a split polynomial)

Hint 1. For

𝑥^{4} + 1

, find a complex number whose square is

𝑖

; its fourth power is

- 1

Hint 2. Over

ℝ

, pair conjugate roots as in the proof of Theorem 7.1.39. For

𝑥^{6} - 1

, start from

(𝑥^{3} - 1) (𝑥^{3} + 1)

Sketch. The roots of

𝑥^{4} + 1

are

(\pm 1 \pm 𝑖) / \sqrt{2}

, and pairing conjugates gives

𝑥^{4} +

1 =

(𝑥^{2} - \sqrt{2} 𝑥 + 1) (𝑥^{2} + \sqrt{2} 𝑥 + 1)

over

ℝ

. Also

𝑥^{6} -

1 =

(𝑥 - 1) (𝑥 + 1) (𝑥^{2} + 𝑥 + 1) (𝑥^{2} - 𝑥 + 1)

over

ℝ

, and the quadratics split over

ℂ

with roots

(- 1 \pm 𝑖 \sqrt{3}) / 2

and

(1 \pm 𝑖 \sqrt{3}) / 2

By Corollary 7.1.42, the irreducible factors over $ℂ$ are linear, and those over $ℝ$ are linear or quadratics with negative discriminant.

$𝑥^{4} + 1$ . Let $𝜁 = (1 + 𝑖) / \sqrt{2}$ . Then $𝜁^{2} =$ $(1 + 2 𝑖 - 1) / 2 =$ $𝑖$ , so $𝜁^{4} = - 1$ . The same computation shows that all four numbers $(\pm 1 \pm 𝑖) / \sqrt{2}$ , that is, $\pm 𝜁$ and $\pm 𝜁$ , have squares $\pm 𝑖$ and are roots. They are distinct, so by Corollary 7.1.35

𝑥^{4} + 1 = (𝑥 - 𝜁) (𝑥 - 𝜁) (𝑥 + 𝜁) (𝑥 + 𝜁) .

Pairing conjugates, $(𝑥 - 𝜁) (𝑥 - 𝜁) =$ $𝑥^{2} -$ $2 (Re 𝜁) 𝑥 +$ $| 𝜁 |^{2} =$ $𝑥^{2} -$ $\sqrt{2} 𝑥 +$ $1$ , and similarly for $- 𝜁$ . So over $ℝ$ ,

𝑥^{4} + 1 = (𝑥^{2} - \sqrt{2} 𝑥 + 1) (𝑥^{2} + \sqrt{2} 𝑥 + 1),

and both quadratics have discriminant $2 - 4 < 0$ . Check: the product is ${(𝑥^{2} + 1)}^{2} -$ $2 𝑥^{2} =$ $𝑥^{4} +$ $1$ .

$𝑥^{6} - 1$ . Since $𝑥^{3} -$ $1 =$ $(𝑥 - 1) (𝑥^{2} + 𝑥 + 1)$ and $𝑥^{3} +$ $1 =$ $(𝑥 + 1) (𝑥^{2} - 𝑥 + 1)$ ,

𝑥^{6} - 1 = (𝑥 - 1) (𝑥 + 1) (𝑥^{2} + 𝑥 + 1) (𝑥^{2} - 𝑥 + 1)

over $ℝ$ , and the two quadratics have discriminant $1 - 4 < 0$ , so they are irreducible. Over $ℂ$ , by the quadratic formula, $𝑥^{2} +$ $𝑥 +$ $1 =$ $(𝑥 - 𝜔) (𝑥 - 𝜔)$ with $𝜔 = (- 1 + 𝑖 \sqrt{3}) / 2$ , and $𝑥^{2} -$ $𝑥 +$ $1 =$ $(𝑥 + 𝜔) (𝑥 + 𝜔)$ , so

𝑥^{6} - 1 = (𝑥 - 1) (𝑥 + 1) (𝑥 - 𝜔) (𝑥 - 𝜔) (𝑥 + 𝜔) (𝑥 + 𝜔) .

The six roots $\pm 1, \pm 𝜔, \pm 𝜔$ are distinct, consistent with Exercise 7.1.54(a).

Exercise 7.1.61.routine

(a)Let $𝑝 \in 𝐹 [𝑥]$ have degree $2$ or $3$ . Show that $𝑝$ is irreducible over $𝐹$ if and only if $𝑝$ has no root in $𝐹$ .
(b)Show that (a) fails in degree $4$ : find a polynomial of degree $4$ over $ℚ$ , and one over $𝔽_{2}$ , that has no root but is reducible.
(c)Which of $𝑥^{2} + 𝑥 + 1$ , $𝑥^{3} + 𝑥 + 1$ , and $𝑥^{3} + 1$ are irreducible over $𝔽_{2}$ ?

Solution.

Uses. Definition 7.1.41 (Irreducible polynomial), Theorem 7.1.20 (Factor theorem), Proposition 7.1.4 (Degree of a product), Example 7.1.40 ( $𝑥^{4} + 4$ ), Exercise 7.1.8

Hint 1. If

𝑝 = 𝑔 ℎ

with both factors of degree at least

1

and

deg 𝑔 + deg ℎ \leq 3

, then one factor has degree

1

Hint 2. For (b), look for a product of two quadratics without roots. Example 7.1.40 and Exercise 7.1.8 have candidates.

Sketch. (a) A root

𝑐

gives

𝑝 = (𝑥 - 𝑐) 𝑞

with

deg 𝑞 \geq 1

. Conversely, in a factorization

𝑝 = 𝑔 ℎ

the degrees add to

2

3

, so one factor is

𝑢 𝑥 + 𝑣

with

𝑢 \neq 0

, and

- 𝑣 / 𝑢

is a root of

𝑝

. (b)

𝑥^{4} +

4 =

(𝑥^{2} - 2 𝑥 + 2) (𝑥^{2} + 2 𝑥 + 2)

over

ℚ

and

𝑥^{4} +

𝑥^{2} +

1 =

{(𝑥^{2} + 𝑥 + 1)}^{2}

over

𝔽_{2}

. (c) The first two have no root in

𝔽_{2}

, so they are irreducible;

𝑥^{3} + 1

has the root

1

(a) If $𝑝$ has a root $𝑐$ , then $𝑝 = (𝑥 - 𝑐) 𝑞$ with $deg 𝑞 = deg 𝑝 - 1 \geq 1$ (Theorem 7.1.20), so $𝑝$ is reducible. Conversely, suppose $𝑝 = 𝑔 ℎ$ with $deg 𝑔, deg ℎ \geq 1$ . Since $deg 𝑔 +$ $deg ℎ =$ $deg 𝑝 \leq$ $3$ (Proposition 7.1.4), one of the factors, say $𝑔$ , has degree $1$ : $𝑔 = 𝑢 𝑥 + 𝑣$ with $𝑢 \neq 0$ . Then $𝑐 = - 𝑣 / 𝑢$ satisfies $𝑔 (𝑐) = 0$ , so $𝑝 (𝑐) =$ $𝑔 (𝑐) ℎ (𝑐) =$ $0$ , and $𝑝$ has a root.

(b) Over $ℚ$ , $𝑥^{4} +$ $4 =$ $(𝑥^{2} - 2 𝑥 + 2) (𝑥^{2} + 2 𝑥 + 2)$ (Example 7.1.40) is reducible, and it has no root even in $ℝ$ , since $𝑡^{4} + 4 \geq 4$ . Over $𝔽_{2}$ , ${(𝑥^{2} + 𝑥 + 1)}^{2} =$ $𝑥^{4} +$ $𝑥^{2} +$ $1$ (Exercise 7.1.8), and $𝑥^{4} + 𝑥^{2} + 1$ takes the value $1$ at both $0$ and $1$ , so it has no root.

(c) The polynomial $𝑥^{2} + 𝑥 + 1$ takes the values $1$ and $1 + 1 + 1 = 1$ at $0$ and $1$ , and $𝑥^{3} + 𝑥 + 1$ takes the values $1$ and $1$ , so by (a) both are irreducible over $𝔽_{2}$ . But $1$ is a root of $𝑥^{3} + 1$ , so it is reducible: $𝑥^{3} +$ $1 =$ $(𝑥 + 1) (𝑥^{2} + 𝑥 + 1)$ .

Exercise 7.1.62.standard Let

𝑝

be a prime. Show that there are exactly

𝑝 (𝑝 - 1) / 2

monic irreducible polynomials of degree

2

𝔽_{𝑝} [𝑥]

, and list them for

𝑝 = 3

Solution.

Uses. Exercise 7.1.61, Theorem 7.1.20 (Factor theorem), Proposition 7.1.34 (Roots of a split polynomial)

Hint 1. Count all monic quadratics, then count the reducible ones. By Exercise 7.1.61, a reducible monic quadratic has a root.

Hint 2. A reducible monic quadratic is

(𝑥 - 𝑎) (𝑥 - 𝑏)

. By Proposition 7.1.34, how many choices of

𝑎, 𝑏

give the same polynomial?

Sketch. There are

𝑝^{2}

monic quadratics

𝑥^{2} + 𝑏 𝑥 + 𝑐

. The reducible ones are the products

(𝑥 - 𝑎) (𝑥 - 𝑏)

, and by Proposition 7.1.34 two such products are equal exactly when the pairs agree up to order. There are

𝑝 +

𝑝 (𝑝 - 1) / 2 =

𝑝 (𝑝 + 1) / 2

unordered pairs, so

𝑝^{2} -

𝑝 (𝑝 + 1) / 2 =

𝑝 (𝑝 - 1) / 2

are irreducible. For

𝑝 = 3

𝑥^{2} + 1

𝑥^{2} + 𝑥 + 2

𝑥^{2} + 2 𝑥 + 2

A monic quadratic is $𝑥^{2} + 𝑏 𝑥 + 𝑐$ with $𝑏, 𝑐 \in 𝔽_{𝑝}$ , so there are $𝑝^{2}$ of them. If one is reducible, it has a root $𝑎$ (Exercise 7.1.61), and then it equals $(𝑥 - 𝑎) 𝑞$ with $𝑞$ monic of degree $1$ (Theorem 7.1.20, comparing leading coefficients), so it is $(𝑥 - 𝑎) (𝑥 - 𝑏)$ for some $𝑎, 𝑏 \in 𝔽_{𝑝}$ . Conversely every such product is a reducible monic quadratic. By Proposition 7.1.34, $(𝑥 - 𝑎) (𝑥 - 𝑏) =$ $(𝑥 - 𝑎^{'}) (𝑥 - 𝑏^{'})$ if and only if the lists $𝑎, 𝑏$ and $𝑎^{'}, 𝑏^{'}$ agree up to order. So the reducible monic quadratics correspond to unordered pairs ${𝑎, 𝑏}$ with repetition allowed: $𝑝$ with $𝑎 = 𝑏$ , and $𝑝 (𝑝 - 1) / 2$ with $𝑎 \neq 𝑏$ . That makes $𝑝 (𝑝 + 1) / 2$ reducible ones, and

𝑝^{2} - 𝑝 \frac{𝑝 + 1}{2} = 𝑝 \frac{𝑝 - 1}{2}

irreducible ones.

For $𝑝 = 3$ there are $3$ . Checking values at $0, 1, 2$ : $𝑥^{2} + 1$ takes the values $1, 2, 2$ ; $𝑥^{2} + 𝑥 + 2$ takes $2, 1, 2$ ; and $𝑥^{2} + 2 𝑥 + 2$ takes $2, 2, 1$ . None has a root, so these are the three monic irreducible quadratics over $𝔽_{3}$ .

Exercise 7.1.63.standard Let

𝑓 \in {ℂ [𝑥]}_{\leq 𝑛}

, and suppose that

𝑓 (𝑡_{𝑘}) \in ℝ

for

𝑛 + 1

distinct real numbers

𝑡_{0}, \dots, 𝑡_{𝑛}

. Show that

𝑓

has real coefficients. Show by an example that the hypothesis

deg 𝑓 \leq 𝑛

cannot be dropped.

Solution.

Uses. Lemma 7.1.37 (Conjugating polynomials), Corollary 7.1.23 (Polynomials and their values)

Hint 1. Compare

𝑓

with the conjugate polynomial

𝑓

at the points

𝑡_{𝑘}

Hint 2. For the example, take a polynomial that vanishes at all the

𝑡_{𝑘}

Sketch. For real

𝑡_{𝑘}

𝑓 (𝑡_{𝑘}) =

𝑓 (𝑡_{𝑘}) =

𝑓 (𝑡_{𝑘}) =

𝑓 (𝑡_{𝑘})

. So

𝑓

and

𝑓

, both of degree at most

𝑛

, agree at

𝑛 + 1

points, and

𝑓 = 𝑓 \in ℝ [𝑥]

. Without the degree bound,

𝑖 (𝑥 - 𝑡_{0}) \dots (𝑥 - 𝑡_{𝑛})

is real (zero) at every

𝑡_{𝑘}

The conjugate polynomial $𝑓$ has the same degree as $𝑓$ , so it lies in ${ℂ [𝑥]}_{\leq 𝑛}$ . For each $𝑘$ , since $𝑡_{𝑘}$ is real and $𝑓 (𝑡_{𝑘})$ is real, Lemma 7.1.37(b) gives

𝑓 (𝑡_{𝑘}) = 𝑓 (𝑡_{𝑘}) = 𝑓 (𝑡_{𝑘}) = 𝑓 (𝑡_{𝑘}) .

So $𝑓$ and $𝑓$ agree at the $𝑛 + 1$ distinct points $𝑡_{0}, \dots, 𝑡_{𝑛}$ , and $𝑓 = 𝑓$ by Corollary 7.1.23(a). By Lemma 7.1.37(c), $𝑓 \in ℝ [𝑥]$ .

The degree bound is needed: $𝑔 =$ $𝑖 (𝑥 - 𝑡_{0}) (𝑥 - 𝑡_{1}) \dots (𝑥 - 𝑡_{𝑛})$ has $𝑔 (𝑡_{𝑘}) = 0 \in ℝ$ for every $𝑘$ , but its leading coefficient $𝑖$ is not real.

Exercise 7.1.64.hard Let

𝑝 \in ℝ [𝑥]

satisfy

𝑝 (𝑡) \geq 0

for every

𝑡 \in ℝ

. Show that

𝑝 = 𝑓^{2} + 𝑔^{2}

for some

𝑓, 𝑔 \in ℝ [𝑥]

Solution.

Uses. Theorem 7.1.39 (Factorization over $ℝ$ ), Lemma 7.1.37 (Conjugating polynomials), Lemma 7.1.25 (Reading off a multiplicity), continuity of polynomial functions

Hint 1. First show that every real root of

𝑝

has even multiplicity: a root of odd multiplicity is a point where

𝑝

changes sign.

Hint 2. Then factor

𝑝

as in Theorem 7.1.39, show

𝑎 > 0

, and split each quadratic factor over

ℂ

(𝑥 - 𝜇) (𝑥 - 𝜇)

Hint 3. Find

ℎ \in ℂ [𝑥]

with

𝑝 = ℎ ℎ

, and write

ℎ = 𝑓 + 𝑖 𝑔

with

𝑓, 𝑔 \in ℝ [𝑥]

Sketch. If a real root

𝜆

had odd multiplicity

𝑚

, then

𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞

with

𝑞 (𝜆) \neq 0

, and

𝑝

would change sign at

𝜆

. So

𝑝 =

𝑎 \prod {(𝑥 - 𝜆_{𝑖})}^{2 𝑘_{𝑖}} \prod (𝑥 - 𝜇_{𝑗}) (𝑥 - 𝜇_{𝑗})

with

𝑎 > 0

. Let

ℎ =

\sqrt{𝑎} \prod {(𝑥 - 𝜆_{𝑖})}^{𝑘_{𝑖}} \prod (𝑥 - 𝜇_{𝑗})

. Then

ℎ =

\sqrt{𝑎} \prod {(𝑥 - 𝜆_{𝑖})}^{𝑘_{𝑖}} \prod (𝑥 - 𝜇_{𝑗})

, so

𝑝 = ℎ ℎ

, and with

ℎ = 𝑓 + 𝑖 𝑔

this is

(𝑓 + 𝑖 𝑔) (𝑓 - 𝑖 𝑔) =

𝑓^{2} +

𝑔^{2}

If $𝑝 = 𝟎$ , take $𝑓 = 𝑔 = 𝟎$ . Let $𝑝 \neq 𝟎$ .

Real roots have even multiplicity. Let $𝜆 \in ℝ$ be a root of multiplicity $𝑚$ , and write $𝑝 = {(𝑥 - 𝜆)}^{𝑚} 𝑞$ with $𝑞 (𝜆) \neq 0$ (Lemma 7.1.25). The function $𝑡 \mapsto 𝑞 (𝑡)$ is continuous, so it has constant sign on some interval $(𝜆 - 𝛿, 𝜆 + 𝛿)$ . If $𝑚$ were odd, ${(𝑡 - 𝜆)}^{𝑚}$ would be negative for $𝑡 < 𝜆$ and positive for $𝑡 > 𝜆$ , so $𝑝 (𝑡) =$ ${(𝑡 - 𝜆)}^{𝑚} 𝑞 (𝑡)$ would take both signs near $𝜆$ , contradicting $𝑝 \geq 0$ . So $𝑚$ is even.

Factor. By Theorem 7.1.39, whose real linear factors are the real roots listed with multiplicity, and grouping equal linear factors,

𝑝 = 𝑎 \prod_{𝑖 = 1}^{𝑟} {(𝑥 - 𝜆_{𝑖})}^{2 𝑘_{𝑖}} \prod_{𝑗 = 1}^{𝑙} (𝑥^{2} + 𝑏_{𝑗} 𝑥 + 𝑐_{𝑗}),

with distinct real $𝜆_{𝑖}$ , each of even multiplicity $2 𝑘_{𝑖}$ by the first step, and $𝑏_{𝑗}^{2} < 4 𝑐_{𝑗}$ . Each quadratic factor is positive on $ℝ$ , since $𝑡^{2} +$ $𝑏_{𝑗} 𝑡 +$ $𝑐_{𝑗} =$ ${(𝑡 + 𝑏_{𝑗} / 2)}^{2} +$ $(𝑐_{𝑗} - 𝑏_{𝑗}^{2} / 4)$ . Choose $𝑡 \in ℝ$ that is not a root of $𝑝$ (there are finitely many roots). Then $𝑝 (𝑡) > 0$ and every factor other than $𝑎$ is positive at $𝑡$ , so $𝑎 > 0$ .

Write $𝑝 = ℎ ℎ$ . As in the proof of Theorem 7.1.39, $𝑥^{2} +$ $𝑏_{𝑗} 𝑥 +$ $𝑐_{𝑗} =$ $(𝑥 - 𝜇_{𝑗}) (𝑥 - 𝜇_{𝑗})$ for some $𝜇_{𝑗} \in ℂ$ . Let

ℎ = \sqrt{𝑎} \prod_{𝑖 = 1}^{𝑟} {(𝑥 - 𝜆_{𝑖})}^{𝑘_{𝑖}} \prod_{𝑗 = 1}^{𝑙} (𝑥 - 𝜇_{𝑗}) \in ℂ [𝑥] .

By Lemma 7.1.37(a), and since $\sqrt{𝑎}$ and the $𝜆_{𝑖}$ are real, $ℎ =$ $\sqrt{𝑎} \prod_{𝑖} {(𝑥 - 𝜆_{𝑖})}^{𝑘_{𝑖}} \prod_{𝑗} (𝑥 - 𝜇_{𝑗})$ . Hence $ℎ ℎ = 𝑝$ .

Real and imaginary parts. Write $ℎ = 𝑓 + 𝑖 𝑔$ , where $𝑓, 𝑔 \in ℝ [𝑥]$ have as coefficients the real and imaginary parts of the coefficients of $ℎ$ . Then $ℎ = 𝑓 - 𝑖 𝑔$ , and

𝑝 = ℎ ℎ = (𝑓 + 𝑖 𝑔) (𝑓 - 𝑖 𝑔) = 𝑓^{2} + 𝑔^{2} .

Both sides lie in $ℝ [𝑥]$ , and the identity holds there because the operations of $ℝ [𝑥]$ are those of $ℂ [𝑥]$ .

Exercise 7.1.65.hard

(a)Let $𝐹$ be a field with $1 + 1 \neq 0$ . Find all $𝑝 \in 𝐹 [𝑥]$ with $𝑝 (𝑥^{2}) = 𝑝^{2}$ .
(b)Show that every $𝑝 \in 𝔽_{2} [𝑥]$ satisfies $𝑝 (𝑥^{2}) = 𝑝^{2}$ .

Solution.

Uses. Definition 7.1.9 (Substitution), Definition 7.1.1 (Product of polynomials), Proposition 7.1.4 (Degree of a product)

Techniques. Compare degrees and leading coefficients (Technique 7.1.6)

Hint 1. Try small cases: which monomials

𝑎 𝑥^{𝑛}

work? Compare leading coefficients.

Hint 2. Suppose

𝑝 =

𝑥^{𝑛} +

𝑎_{𝑘} 𝑥^{𝑘} +

\dots

, where

𝑘 < 𝑛

𝑎_{𝑘} \neq 0

, and the omitted terms have degree less than

𝑘

. Compute the coefficient of

𝑥^{𝑛 + 𝑘}

on both sides.

Hint 3. On the right it is

2 𝑎_{𝑘}

. On the left,

𝑝 (𝑥^{2})

has only even powers

𝑥^{2 𝑗}

, and

𝑥^{𝑛 + 𝑘}

would need

𝑗 = (𝑛 + 𝑘) / 2

, strictly between

𝑘

and

𝑛

Sketch. (a) The solutions are

𝟎

and

𝑥^{𝑛}

𝑛 \geq 0

. For

𝑝 \neq 𝟎

of degree

𝑛

with leading coefficient

𝑎

, comparing leading coefficients gives

𝑎 = 𝑎^{2}

, so

𝑎 = 1

. If

𝑝

had another nonzero coefficient, let

𝑎_{𝑘}

be the one with the largest

𝑘 < 𝑛

. The coefficient of

𝑥^{𝑛 + 𝑘}

2 𝑎_{𝑘} \neq 0

𝑝^{2}

, but

0

𝑝 (𝑥^{2})

. (b) Over

𝔽_{2}

𝑝^{2} =

\sum 𝑎_{𝑖}^{2} 𝑥^{2 𝑖} +

2 \sum_{𝑖 < 𝑗} 𝑎_{𝑖} 𝑎_{𝑗} 𝑥^{𝑖 + 𝑗} =

\sum 𝑎_{𝑖} 𝑥^{2 𝑖}

(a) The solutions are $𝑝 = 𝟎$ and $𝑝 = 𝑥^{𝑛}$ for $𝑛 \geq 0$ ; these work, since ${(𝑥^{2})}^{𝑛} =$ $𝑥^{2 𝑛} =$ ${(𝑥^{𝑛})}^{2}$ . Conversely, let $𝑝 =$ $\sum_{𝑗 = 0}^{𝑛} 𝑎_{𝑗} 𝑥^{𝑗}$ with $𝑎_{𝑛} \neq 0$ satisfy $𝑝 (𝑥^{2}) = 𝑝^{2}$ . The polynomial $𝑝 (𝑥^{2}) =$ $\sum_{𝑗} 𝑎_{𝑗} 𝑥^{2 𝑗}$ has leading coefficient $𝑎_{𝑛}$ , and $𝑝^{2}$ has leading coefficient $𝑎_{𝑛}^{2}$ (Proposition 7.1.4). So $𝑎_{𝑛}^{2} = 𝑎_{𝑛}$ , and $𝑎_{𝑛} = 1$ .

Suppose $𝑝 \neq 𝑥^{𝑛}$ , and let $𝑘 < 𝑛$ be the largest index below $𝑛$ with $𝑎_{𝑘} \neq 0$ . In $𝑝^{2}$ , the coefficient of $𝑥^{𝑛 + 𝑘}$ is $\sum_{𝑖 + 𝑗 = 𝑛 + 𝑘} 𝑎_{𝑖} 𝑎_{𝑗}$ . A nonzero term needs $𝑎_{𝑖} \neq 0$ and $𝑎_{𝑗} \neq 0$ , so each of $𝑖, 𝑗$ is $𝑛$ or at most $𝑘$ . If $𝑖 \leq 𝑘$ , then $𝑗 = 𝑛 + 𝑘 - 𝑖 \geq 𝑛$ , so $𝑗 = 𝑛$ and $𝑖 = 𝑘$ ; similarly if $𝑗 \leq 𝑘$ . So only the pairs $(𝑛, 𝑘)$ and $(𝑘, 𝑛)$ contribute, and the coefficient is $2 𝑎_{𝑛} 𝑎_{𝑘} = 2 𝑎_{𝑘}$ , which is nonzero because $1 + 1 \neq 0$ and $𝐹$ has no zero divisors. In $𝑝 (𝑥^{2}) =$ $\sum_{𝑗} 𝑎_{𝑗} 𝑥^{2 𝑗}$ , the coefficient of $𝑥^{𝑛 + 𝑘}$ is $0$ if $𝑛 + 𝑘$ is odd, and $𝑎_{(𝑛 + 𝑘) / 2}$ if it is even. Since $𝑘 <$ $(𝑛 + 𝑘) / 2 <$ $𝑛$ , this is $0$ by the choice of $𝑘$ . The two sides differ, a contradiction. So $𝑝 = 𝑥^{𝑛}$ .

(b) Let $𝑝 =$ $\sum_{𝑖} 𝑎_{𝑖} 𝑥^{𝑖} \in$ $𝔽_{2} [𝑥]$ . Expanding the square and grouping the pairs $(𝑖, 𝑗)$ and $(𝑗, 𝑖)$ with $𝑖 \neq 𝑗$ ,

\begin{aligned} 𝑝^{2} & = \sum_{𝑖, 𝑗} 𝑎_{𝑖} 𝑎_{𝑗} 𝑥^{𝑖 + 𝑗} = \sum_{𝑖} 𝑎_{𝑖}^{2} 𝑥^{2 𝑖} + \sum_{𝑖 < 𝑗} 2 𝑎_{𝑖} 𝑎_{𝑗} 𝑥^{𝑖 + 𝑗} \\ = \sum_{𝑖} 𝑎_{𝑖} 𝑥^{2 𝑖} = 𝑝 (𝑥^{2}), \end{aligned}

because $2 = 0$ and $𝑎^{2} = 𝑎$ for both elements $𝑎$ of $𝔽_{2}$ .

Exercise 7.1.66.challengeBeyond 21-242 (Gauss–Lucas) Let

𝑝 \in ℂ [𝑥]

have degree

𝑛 \geq 2

and roots

𝜆_{1}, \dots, 𝜆_{𝑛}

, listed with multiplicity. Show that every root

𝑤

𝑝^{'}

is a convex combination of the roots of

𝑝

𝑤 =

𝑡_{1} 𝜆_{1} +

\dots +

𝑡_{𝑛} 𝜆_{𝑛}

for some real

𝑡_{𝑖} \geq 0

with

𝑡_{1} + \dots + 𝑡_{𝑛} = 1

Solution.

Uses. Corollary 7.1.35 (Factorization over $ℂ$ ), Exercise 2.1.49, Proposition 7.1.10 (Evaluation respects sums and products), Notation 6.1.1 (Real and complex scalars)

Hint 1. If

𝑤

is a root of

𝑝

, the claim is easy. Otherwise, compute

𝑝^{'}

from

𝑝 = 𝑎 \prod (𝑥 - 𝜆_{𝑖})

with the product rule.

Hint 2. You should find

𝑝^{'} (𝑤) =

𝑝 (𝑤) \sum_{𝑖} 1 / (𝑤 - 𝜆_{𝑖})

, so

\sum_{𝑖} 1 / (𝑤 - 𝜆_{𝑖}) = 0

Hint 3. Write

1 / (𝑤 - 𝜆_{𝑖}) =

𝑤 - 𝜆_{𝑖} / | 𝑤 -

𝜆_{𝑖} |^{2}

, and conjugate the equation.

Sketch. If

𝑝 (𝑤) = 0

, then

𝑤 = 𝜆_{𝑖}

for some

𝑖

. Otherwise

𝑝^{'} =

𝑎 \sum_{𝑖} \prod_{𝑗 \neq 𝑖} (𝑥 - 𝜆_{𝑗})

gives

0 =

𝑝^{'} (𝑤) =

𝑝 (𝑤) \sum_{𝑖} 1 / (𝑤 - 𝜆_{𝑖})

, so

\sum_{𝑖} 𝑤 - 𝜆_{𝑖} / | 𝑤 -

𝜆_{𝑖} |^{2} =

0

. Conjugating,

\sum_{𝑖} 𝑠_{𝑖} (𝑤 - 𝜆_{𝑖}) =

0

with

𝑠_{𝑖} =

| 𝑤 -

𝜆_{𝑖} |^{- 2} >

0

, so

𝑤 =

\sum_{𝑖} (𝑠_{𝑖} / \sum_{𝑗} 𝑠_{𝑗}) 𝜆_{𝑖}

If $𝑝 (𝑤) = 0$ , then $𝑤 = 𝜆_{𝑖}$ for some $𝑖$ (Corollary 7.1.35), and $𝑡_{𝑖} = 1$ , $𝑡_{𝑗} = 0$ for $𝑗 \neq 𝑖$ works. So suppose $𝑝 (𝑤) \neq 0$ .

Write $𝑝 =$ $𝑎 (𝑥 - 𝜆_{1}) \dots (𝑥 - 𝜆_{𝑛})$ . Applying the product rule (Exercise 2.1.49) $𝑛 - 1$ times, by induction on the number of factors,

𝑝^{'} = 𝑎 \sum_{𝑖 = 1}^{𝑛} \prod_{𝑗 \neq 𝑖} (𝑥 - 𝜆_{𝑗}) .

Evaluating at $𝑤$ (Proposition 7.1.10) and using $𝑎 \prod_{𝑗 \neq 𝑖} (𝑤 - 𝜆_{𝑗}) =$ $𝑝 (𝑤) / (𝑤 - 𝜆_{𝑖})$ , which is valid since $𝑤 \neq 𝜆_{𝑖}$ ,

0 = 𝑝^{'} (𝑤) = 𝑝 (𝑤) \sum_{𝑖 = 1}^{𝑛} \frac{1}{𝑤 - 𝜆_{𝑖}} .

Since $𝑝 (𝑤) \neq 0$ , $\sum_{𝑖} 1 / (𝑤 - 𝜆_{𝑖}) = 0$ . For $𝑧 \neq 0$ , $1 / 𝑧 = 𝑧 / | 𝑧 |^{2}$ (Notation 6.1.1), so with $𝑠_{𝑖} =$ $1 / | 𝑤 -$ $𝜆_{𝑖} |^{2} >$ $0$ we get $\sum_{𝑖} 𝑠_{𝑖} 𝑤 - 𝜆_{𝑖} = 0$ . Conjugating, $\sum_{𝑖} 𝑠_{𝑖} (𝑤 - 𝜆_{𝑖}) =$ $0$ , that is,

𝑤 = \sum_{𝑖 = 1}^{𝑛} (\frac{𝑠_{𝑖}}{𝑠_{1} + \dots + 𝑠_{𝑛}}) 𝜆_{𝑖} .

The coefficients $𝑡_{𝑖} =$ $𝑠_{𝑖} / (𝑠_{1} + \dots + 𝑠_{𝑛})$ are positive and add up to $1$ .

Geometrically, the roots of $𝑝^{'}$ lie in the smallest convex polygon containing the roots of $𝑝$ . For real-rooted $𝑝$ this is the interval between the smallest and the largest root.

Exercise 7.1.67.standardBeyond 21-242 Let $𝑝 =$ $𝑥^{4} +$ $𝑥^{3} +$ $2 𝑥^{2} +$ $𝑥 +$ $1$ and $𝑠 = 𝑥^{3} - 1$ .

(a)Over $ℚ$ , compute $gcd (𝑝, 𝑠)$ with the Euclidean algorithm, and find $𝑢, 𝑣 \in ℚ [𝑥]$ with $𝑢 𝑝 +$ $𝑣 𝑠 =$ $gcd (𝑝, 𝑠)$ .
(b)Compute $gcd (𝑝, 𝑠)$ over $𝔽_{2}$ . Why is the answer different?

Solution.

Uses. Algorithm 7.1.46 (Euclidean algorithm), Theorem 7.1.45 (Bézout’s identity), Definition 7.1.44 (Greatest common divisor)

Hint 1. Over

ℚ

the algorithm takes two divisions.

Hint 2. Over

𝔽_{2}

𝑝 = 𝑥^{4} + 𝑥^{3} + 𝑥 + 1

. Divide it by

𝑠 = 𝑥^{3} + 1

Sketch. (a)

𝑝 =

(𝑥 + 1) 𝑠 +

2 (𝑥^{2} + 𝑥 + 1)

and

𝑠 =

(\frac{1}{2} 𝑥 - \frac{1}{2}) \cdot

2 (𝑥^{2} + 𝑥 + 1)

, so

gcd (𝑝, 𝑠) =

𝑥^{2} +

𝑥 +

1 =

\frac{1}{2} 𝑝 -

\frac{1}{2} (𝑥 + 1) 𝑠

. (b) Over

𝔽_{2}

𝑝 = (𝑥 + 1) 𝑠

exactly, so

gcd (𝑝, 𝑠) =

𝑠 =

𝑥^{3} +

1

. Reducing modulo

2

is not an inclusion of fields, so the remainders, and with them the gcd, can change.

(a) Dividing, $𝑝 =$ $(𝑥 + 1) (𝑥^{3} - 1) +$ $(2 𝑥^{2} + 2 𝑥 + 2)$ : indeed $(𝑥 + 1) (𝑥^{3} - 1) =$ $𝑥^{4} +$ $𝑥^{3} -$ $𝑥 -$ $1$ , and $𝑝$ minus this is $2 𝑥^{2} + 2 𝑥 + 2$ . Next, $𝑥^{3} -$ $1 =$ $(\frac{1}{2} 𝑥 - \frac{1}{2}) (2 𝑥^{2} + 2 𝑥 + 2)$ exactly, since $(𝑥 - 1) (𝑥^{2} + 𝑥 + 1) =$ $𝑥^{3} -$ $1$ . The last nonzero remainder is $2 𝑥^{2} + 2 𝑥 + 2$ , so $gcd (𝑝, 𝑠) =$ $𝑥^{2} +$ $𝑥 +$ $1$ , and from the first division

𝑥^{2} + 𝑥 + 1 = \frac{1}{2} (𝑝 - (𝑥 + 1) 𝑠) = \frac{1}{2} 𝑝 - \frac{1}{2} (𝑥 + 1) 𝑠 .

Consistently, $𝑝 =$ $(𝑥^{2} + 1) (𝑥^{2} + 𝑥 + 1)$ and $𝑠 =$ $(𝑥 - 1) (𝑥^{2} + 𝑥 + 1)$ .

(b) Over $𝔽_{2}$ , $𝑝 = 𝑥^{4} + 𝑥^{3} + 𝑥 + 1$ and $𝑠 = 𝑥^{3} + 1$ , and $(𝑥 + 1) (𝑥^{3} + 1) =$ $𝑥^{4} +$ $𝑥^{3} +$ $𝑥 +$ $1 =$ $𝑝$ . So $𝑠 ∣ 𝑝$ , the algorithm stops after one division, and $gcd (𝑝, 𝑠) = 𝑥^{3} + 1$ . The answer has larger degree than over $ℚ$ , because in $𝔽_{2} [𝑥]$ the factor $𝑥^{2} + 1$ of $𝑝$ becomes ${(𝑥 + 1)}^{2}$ , which shares the factor $𝑥 + 1 = 𝑥 - 1$ with $𝑠$ . Reducing the coefficients modulo $2$ is not a passage to a larger field, so nothing like Corollary 7.1.17 applies; already the remainders change, as in Exercise 7.1.18. For a subfield $𝐹 \subseteq 𝐾$ , on the other hand, the gcd computed in $𝐾 [𝑥]$ is the one computed in $𝐹 [𝑥]$ , since the Euclidean algorithm only takes remainders.

Exercise 7.1.68.hardBeyond 21-242

(a)(Euclid’s lemma) Let $𝑝 \in 𝐹 [𝑥]$ be irreducible and $𝑔, ℎ \in 𝐹 [𝑥]$ . Show that if $𝑝 ∣ 𝑔 ℎ$ , then $𝑝 ∣ 𝑔$ or $𝑝 ∣ ℎ$ .
(b)Show that every polynomial of degree at least $1$ is a product of irreducible polynomials, and that the factorization is unique in the following sense: if $𝑎 𝑝_{1} \dots 𝑝_{𝑘} =$ $𝑏 𝑞_{1} \dots 𝑞_{𝑙}$ with $𝑎, 𝑏 \in 𝐹$ nonzero and all $𝑝_{𝑖}, 𝑞_{𝑗}$ monic irreducible, then $𝑎 = 𝑏$ , $𝑘 = 𝑙$ , and the $𝑞_{𝑗}$ are the $𝑝_{𝑖}$ in some order.

Solution.

Uses. Theorem 7.1.45 (Bézout’s identity), Definition 7.1.41 (Irreducible polynomial), Definition 7.1.16 (Divisibility), Corollary 7.1.7 (No zero divisors, cancellation, and units), Proposition 7.1.4 (Degree of a product)

Techniques. Strong induction and well-ordering (Technique 5.2.12)

Hint 1. For (a), let

𝑑 = gcd (𝑝, 𝑔)

. Since

𝑝

is irreducible,

𝑑

1

𝑝

made monic. In the first case use Bézout and multiply by

ℎ

Hint 2. For existence in (b), use strong induction on the degree. For uniqueness, apply (a) repeatedly to see that

𝑝_{1}

divides some

𝑞_{𝑗}

, and cancel.

Sketch. (a)

𝑑 = gcd (𝑝, 𝑔)

divides the irreducible

𝑝

, so

𝑑 = 1

𝑑

𝑝

made monic. In the second case

𝑝 ∣ 𝑔

. In the first,

𝑢 𝑝 + 𝑣 𝑔 = 1

, so

ℎ = 𝑢 𝑝 ℎ + 𝑣 𝑔 ℎ

is divisible by

𝑝

. (b) A reducible polynomial is a product of two of smaller degree, so strong induction gives existence. For uniqueness, compare leading coefficients, then

𝑝_{1} ∣ 𝑞_{1} \dots 𝑞_{𝑙}

, so

𝑝_{1} ∣ 𝑞_{𝑗}

for some

𝑗

by (a); both are monic irreducible, so

𝑝_{1} = 𝑞_{𝑗}

; cancel and induct on

𝑘

(a) Let $𝑑 = gcd (𝑝, 𝑔)$ (Theorem 7.1.45). Since $𝑑 ∣ 𝑝$ , write $𝑝 = 𝑑 𝑒$ . As $𝑝$ is irreducible, $deg 𝑑 = 0$ or $deg 𝑒 = 0$ . If $deg 𝑑 = 0$ , then $𝑑 = 1$ , being monic, and Bézout gives $𝑢 𝑝 + 𝑣 𝑔 = 1$ for some $𝑢, 𝑣$ . Multiplying by $ℎ$ , $ℎ = 𝑢 𝑝 ℎ + 𝑣 𝑔 ℎ$ . Both terms are divisible by $𝑝$ , the second because $𝑝 ∣ 𝑔 ℎ$ , so $𝑝 ∣ ℎ$ . If $deg 𝑒 = 0$ , then $𝑒$ is a nonzero constant and $𝑝 = 𝑒 𝑑$ divides $𝑔$ , because $𝑑$ does.

(b) Existence, by strong induction on $deg 𝑓$ for $𝑓$ of degree at least $1$ . If $𝑓$ is irreducible, it is a product of one irreducible. Otherwise $𝑓 = 𝑔 ℎ$ with $1 \leq$ $deg 𝑔,$ $deg ℎ <$ $deg 𝑓$ , and by the induction hypothesis both $𝑔$ and $ℎ$ are products of irreducibles, hence so is $𝑓$ . Writing each irreducible factor as a constant times a monic one, $𝑓 = 𝑎 𝑝_{1} \dots 𝑝_{𝑘}$ with $𝑝_{𝑖}$ monic irreducible.

Uniqueness. The product of monic polynomials is monic, so comparing leading coefficients gives $𝑎 = 𝑏$ , and cancelling $𝑎$ leaves $𝑝_{1} \dots 𝑝_{𝑘} = 𝑞_{1} \dots 𝑞_{𝑙}$ . We induct on $𝑘$ . If $𝑘 = 0$ , the left side is $1$ , so $𝑙 = 0$ by degrees. If $𝑘 \geq 1$ , then $𝑙 \geq 1$ , since otherwise $𝑝_{1} \dots 𝑝_{𝑘} = 1$ would have degree $0 < 𝑘$ . So $𝑝_{1}$ divides $𝑞_{1} \dots 𝑞_{𝑙}$ , and by (a) applied $𝑙 - 1$ times, $𝑝_{1} ∣ 𝑞_{𝑗}$ for some $𝑗$ . Since $𝑞_{𝑗}$ is irreducible and $deg 𝑝_{1} \geq 1$ , $𝑞_{𝑗} = 𝑝_{1} 𝑐$ with $𝑐$ constant, and as both are monic, $𝑐 = 1$ . Cancelling $𝑝_{1} = 𝑞_{𝑗}$ from both sides (Corollary 7.1.7(b)) leaves products of $𝑘 - 1$ and $𝑙 - 1$ monic irreducibles, and the induction hypothesis finishes the proof.

Exercise 7.1.69.hardBeyond 21-242 (Chinese remainder theorem) Let $𝑚_{1}, 𝑚_{2} \in 𝐹 [𝑥]$ be coprime, of degrees $𝑑_{1}, 𝑑_{2} \geq 1$ , and let $𝑟_{1}, 𝑟_{2} \in 𝐹 [𝑥]$ .

(a)Show that there is exactly one $𝑝 \in 𝐹 [𝑥]$ with $deg 𝑝 < 𝑑_{1} + 𝑑_{2}$ such that $𝑚_{1} ∣ 𝑝 - 𝑟_{1}$ and $𝑚_{2} ∣ 𝑝 - 𝑟_{2}$ .
(b)Explain why polynomial interpolation at two nodes (Theorem 3.4.24 with $𝑛 = 1$ ) is the special case $𝑚_{𝑖} = 𝑥 - 𝑐_{𝑖}$ .

Solution.

Uses. Theorem 7.1.45 (Bézout’s identity), Corollary 7.1.48 (Coprime polynomials), Theorem 7.1.14 (Division with remainder), Theorem 7.1.20 (Factor theorem), Proposition 7.1.4 (Degree of a product)

Techniques. Compare degrees and leading coefficients (Technique 7.1.6)

Hint 1. Use

𝑢 𝑚_{1} + 𝑣 𝑚_{2} = 1

. The polynomial

𝑣 𝑚_{2}

1

“modulo

𝑚_{1}

” and

0

“modulo

𝑚_{2}

”.

Hint 2. Take

𝑃 =

𝑟_{1} 𝑣 𝑚_{2} +

𝑟_{2} 𝑢 𝑚_{1}

, then reduce it modulo

𝑚_{1} 𝑚_{2}

. For uniqueness, show that

𝑚_{1} 𝑚_{2}

divides the difference of two solutions.

Sketch. With

𝑢 𝑚_{1} + 𝑣 𝑚_{2} = 1

𝑃 =

𝑟_{1} 𝑣 𝑚_{2} +

𝑟_{2} 𝑢 𝑚_{1}

satisfies

𝑃 -

𝑟_{1} =

(𝑟_{2} - 𝑟_{1}) 𝑢 𝑚_{1}

and

𝑃 -

𝑟_{2} =

(𝑟_{1} - 𝑟_{2}) 𝑣 𝑚_{2}

. Its remainder

𝑝

on division by

𝑚_{1} 𝑚_{2}

still works and has degree less than

𝑑_{1} + 𝑑_{2}

. If

𝑝, 𝑝^{'}

both work, then

𝑝 - 𝑝^{'} = 𝑚_{1} 𝑔

and

𝑚_{2} ∣ 𝑚_{1} 𝑔

, so

𝑚_{2} ∣

𝑔 =

𝑢 𝑚_{1} 𝑔 +

𝑣 𝑚_{2} 𝑔

; hence

𝑚_{1} 𝑚_{2} ∣ 𝑝 - 𝑝^{'}

, and degrees force

𝑝 = 𝑝^{'}

. For (b),

𝑥 - 𝑐_{𝑖}

divides

𝑝 - 𝑟_{𝑖}

iff

𝑝 (𝑐_{𝑖}) =

𝑟_{𝑖} (𝑐_{𝑖})

(a) By Theorem 7.1.45 there are $𝑢, 𝑣$ with $𝑢 𝑚_{1} + 𝑣 𝑚_{2} = 1$ .

Existence. Let $𝑃 =$ $𝑟_{1} 𝑣 𝑚_{2} +$ $𝑟_{2} 𝑢 𝑚_{1}$ . Using $𝑣 𝑚_{2} = 1 - 𝑢 𝑚_{1}$ and $𝑢 𝑚_{1} = 1 - 𝑣 𝑚_{2}$ ,

\begin{aligned} 𝑃 - 𝑟_{1} & = 𝑟_{1} (𝑣 𝑚_{2} - 1) + 𝑟_{2} 𝑢 𝑚_{1} = (𝑟_{2} - 𝑟_{1}) 𝑢 𝑚_{1}, \\ 𝑃 - 𝑟_{2} & = 𝑟_{1} 𝑣 𝑚_{2} + 𝑟_{2} (𝑢 𝑚_{1} - 1) = (𝑟_{1} - 𝑟_{2}) 𝑣 𝑚_{2} . \end{aligned}

So $𝑚_{1} ∣ 𝑃 - 𝑟_{1}$ and $𝑚_{2} ∣ 𝑃 - 𝑟_{2}$ . Divide $𝑃$ by $𝑚_{1} 𝑚_{2}$ , which has degree $𝑑_{1} + 𝑑_{2}$ (Proposition 7.1.4): $𝑃 = 𝑚_{1} 𝑚_{2} 𝑞 + 𝑝$ with $deg 𝑝 < 𝑑_{1} + 𝑑_{2}$ (Theorem 7.1.14). Then $𝑝 -$ $𝑟_{1} =$ $(𝑃 - 𝑟_{1}) -$ $𝑚_{1} 𝑚_{2} 𝑞$ is divisible by $𝑚_{1}$ , and likewise $𝑚_{2} ∣ 𝑝 - 𝑟_{2}$ .

Uniqueness. Suppose $𝑝$ and $𝑝^{'}$ both have the property. Then $𝑚_{1}$ and $𝑚_{2}$ both divide $𝑒 = 𝑝 - 𝑝^{'}$ , since $𝑒 =$ $(𝑝 - 𝑟_{𝑖}) -$ $(𝑝^{'} - 𝑟_{𝑖})$ . Write $𝑒 = 𝑚_{1} 𝑔$ . Then

𝑔 = (𝑢 𝑚_{1} + 𝑣 𝑚_{2}) 𝑔 = 𝑢 𝑒 + 𝑣 𝑚_{2} 𝑔,

and $𝑚_{2}$ divides both terms, so $𝑚_{2} ∣ 𝑔$ and $𝑚_{1} 𝑚_{2} ∣ 𝑒$ . But $deg 𝑒 <$ $𝑑_{1} +$ $𝑑_{2} =$ $deg (𝑚_{1} 𝑚_{2})$ , so $𝑒 = 𝟎$ by Proposition 7.1.4. Hence $𝑝 = 𝑝^{'}$ .

(b) Let $𝑐_{1} \neq 𝑐_{2}$ and $𝑦_{1}, 𝑦_{2} \in 𝐹$ , and let $𝑚_{𝑖} = 𝑥 - 𝑐_{𝑖}$ and $𝑟_{𝑖} = 𝑦_{𝑖}$ (constants). These are coprime, since $(𝑥 - 𝑐_{1}) -$ $(𝑥 - 𝑐_{2}) =$ $𝑐_{2} -$ $𝑐_{1}$ is a nonzero constant and Corollary 7.1.48(a) applies after dividing by it. By Theorem 7.1.20, $𝑥 - 𝑐_{𝑖}$ divides $𝑝 - 𝑦_{𝑖}$ if and only if $𝑝 (𝑐_{𝑖}) = 𝑦_{𝑖}$ . So (a) says that there is exactly one $𝑝$ of degree less than $2$ with $𝑝 (𝑐_{1}) = 𝑦_{1}$ and $𝑝 (𝑐_{2}) = 𝑦_{2}$ , which is Theorem 3.4.24 for two nodes. With more coprime moduli, the same argument by induction gives interpolation at any number of nodes. Moduli ${(𝑥 - 𝑐)}^{2}$ give interpolation with prescribed values and first derivatives, as in Exercise 7.1.57; higher powers ${(𝑥 - 𝑐)}^{𝑘}$ prescribe higher derivatives, at least in characteristic $0$ .

More practice

The practice bank has 32 exercises on this section’s topics.