In the parallel development of \(F[x]\) and \(\mathbb{Z}\), the next step is to consider criteria for irreducibility of polynomials (the analogue of primality testing for integers). Unlike the situation in the integers, there are a number of such criteria for polynomials whose implementation does not depend on a computer. Most of them are based on the fact that every polynomial in \(F[x]\) induces a function from \(F \rightarrow F\). The properties of this function (in particular, the places where it is zero) are closely related to the reducibility or irreducibility of the polynomial.

Throughout this section, \(R\) is a commutative ring. Associated with each polynomial \(a_nx^n + \cdots + a_2x^2 + a_1x + a_0\) in \(R[x]\) is a function \(f: R \rightarrow R\) whose rule is

\[ f(r) = a_n r^n + \cdots + a_2 r^2 + a_1r + a_0 \]

for each \(r \in R\). The function \(f\) induced by a polynomial in this way is called a polynomial function.

Example 1

The polynomial \(x^2 + 5x + 3 \in \mathbb{R}[x]\) induces the function \(f: \mathbb{R} \rightarrow \mathbb{R}\) whose rule is \(f(r) = r^2 + 5r + 3\) for each \(r \in \mathbb{R}\).

Example 2

The polynomial \(x^4 + x + 1 \in \mathbb{Z}_3[x]\) induces the function \(f: \mathbb{Z}_3 \rightarrow \mathbb{Z}_3\) whose rule is \(f(r) = r^4 + r + 1\). Thus,

\[ f(0) = 0^4 + 0 + 1 = 1, \quad f(1) = 1^4 + 1 + 1 = 0, \quad f(2) = 2^4 + 2 + 1 = 1. \]

The polynomial \(x^3 + x^2 + 1 \in \mathbb{Z}_3[x]\) induces the function \(g: \mathbb{Z}_3 \rightarrow \mathbb{Z}_3\) given by

\[ g(0) = 0^3 + 0^2 + 1 = 1, \quad g(1) = 1^3 + 1^2 + 1 = 0, \quad g(2) = 2^3 + 2^2 + 1 = 1. \]

Thus, \(f\) and \(g\) are the same function on \(\mathbb{Z}_3\), even though they are induced by different polynomials in \(\mathbb{Z}_3[x]\).

Although the distinction between a polynomial and the polynomial function it induces is clear, the customary notation is quite ambiguous. For example, you will see a statement such as \(f(x) = x^2 - 3x + 2\). Depending on the context, \(f(x)\) might denote the polynomial \(x^2 - 3x + 2 \in R[x]\) or the rule of its induced function \(f: R \rightarrow R\). The symbol \(x\) is being used in two different ways here. In the polynomial ring \(R[x]\), \(x\) is an indeterminate (transcendental element) of the ring \(R[x]\). But in the function notation \(f: R \rightarrow R\), the symbol \(x\) is used as a variable to describe the rule of the function. It might be better to use one symbol for an indeterminate and another for a variable, but the practice of using \(x\) for both is so widespread you may as well get used to it.

The use of the same notation for both the polynomial and its induced function also affects the language that is used. For instance, one says "evaluate the polynomial \(3x^2 - 5x + 4\) at \(x = 2\)" or "substitute \(x = 2\) in \(3x^2 - 5x + 4\)" when what is really meant is "find \(f(2)\) when \(f\) is the function induced by the polynomial \(3x^2 - 5x + 4\)".

The truth or falsity of certain statements depends on whether \(x\) is treated as an indeterminate or a variable. For instance, in the ring \(R[x]\), where \(x\) is an indeterminate (special element of the ring), the statement \(x^2 - 3x + 2 = 0\) is false because in Theorem 4.1, a polynomial is zero if and only if all its coefficients are zero. When \(x\) is a variable, however, as in the rule of the polynomial function \(f(x) = x^2 - 3x + 2\), things are different. Here it is perfectly reasonable to ask which elements of \(R\) are mapped to \(0\) by the function \(f\), that is, for which values of the variable is it true that \(x^2 - 3x + 2 = 0\).

Roots of Polynomials

Questions about the reducibility of a polynomial can sometimes be answered by considering its induced polynomial function. The key to this analysis is the concept of a root.

Definition

Let \(R\) be a commutative ring and \(f(x) \in R[x]\). An element \(a\) of \(R\) is said to be a root (or zero) of the polynomial \(f(x)\) if \(f(a) = 0_R\), that is, if the induced function \(f: R \rightarrow R\) maps \(a\) to \(0_R\).

Example 3

The roots of the polynomial \(f(x) = x^2 - 3x + 2 \in R[x]\) are the values of the variable \(x\) for which \(f(x) = 0\), that is, the solutions of the equation \(x^2 - 3x + 2 = 0\). It is easy to see that the roots are \(1\) and \(2\).

Example 4

The polynomial \(x^2 + 1 \in R[x]\) has no roots in \(\mathbb{R}\) because there are no real-number solutions of the equation \(x^2 + 1 = 0\). However, if \(x^2 + 1\) is considered as a polynomial in \(\mathbb{C}[x]\), then it has \(i\) and \(-i\) as roots because these are the solutions in \(\mathbb{C}\) of \(x^2 + 1 = 0\).

Theorem 4.15: The Remainder Theorem

Let \(F\) be a field, \(f(x) \in F[x]\), and \(a \in F\). The remainder when \(f(x)\) is divided by the polynomial \(x - a\) is \(f(a)\).

Example 5

To find the remainder when \(f(x) = x^{79} + 3x^{24} + 5\) is divided by \(x - 1\), we apply the Remainder Theorem with \(a = 1\). The remainder is

\[ f(1) = 1^{79} + 3 \cdot 1^{24} + 5 = 1 + 3 + 5 = 9. \]

Example 6

To find the remainder when \(f(x) = 3x^4 - 8x^2 + 11x + 5\) is divided by \(x + 2\), we apply the Remainder Theorem carefully. The divisor in the theorem is \(x - a\), not \(x + a\). So we rewrite \(x + 2\) as \(x - (-2)\) and apply the Remainder Theorem with \(a = -2\). The remainder is

\[ f(-2) = 3(-2)^4 - 8(-2)^2 + 11(-2) + 5 = 48 - 32 - 22 + 1 = -5. \]

Proof of Theorem 4.15

By the Division Algorithm, \(f(x) = (x - a)q(x) + r(x)\), where the remainder \(r(x)\) either is \(0_F\) or has smaller degree than the divisor \(x - a\). Thus \(\text{deg}(r(x)) = 0\) or \(r(x) = 0_F\). In either case, \(r(x)\) is some \(c \in F\). Hence, \(f(x) = (x - a)q(x) + c\), so that \(f(a) = (a - a)q(a) + c = 0_F + c = c\).

Theorem 4.16: The Factor Theorem

Let \(F\) be a field, \(f(x) \in F[x]\), and \(a \in F\). Then \(a\) is a root of the polynomial \(f(x)\) if and only if \(x - a\) is a factor of \(f(x)\) in \(F[x]\).

Proof

First assume that \(a\) is a root of \(f(x)\). Then we have

\[ f(x) = (x - a)q(x) + r(x) \quad \text{[Division Algorithm]} \] \[ f(x) = (x - a)q(x) + f(a) \quad \text{[Remainder Theorem]} \] \[ f(x) = (x - a)q(x) \quad \text{[since \(a\) is a root of \(f(x)\), so \(f(a) = 0_F\)} \]

Therefore, \(x - a\) is a factor of \(f(x)\).

Conversely, assume that \(x - a\) is a factor of \(f(x)\), say \(f(x) = (x - a)g(x)\). Then \(a\) is a root of \(f(x)\) because

\[ f(a) = (a - a)g(a) = 0_F \cdot g(a) = 0_F. \blacksquare \]

Example 7

To show that \(x^7 - x^5 + 2x^4 - 3x^2 + x + 2\) is reducible in \(\mathbb{Q}[x]\), note that \(1\) is a root of this polynomial. Therefore, \(x - 1\) is a factor.

Corollary 4.17

Let \(F\) be a field and \(f(x)\) a nonzero polynomial of degree \(n\) in \(F[x]\). Then \(f(x)\) has at most \(n\) roots in \(F\).

Proof

If \(f(x)\) has a root \(a_1\) in \(F\), then by the Factor Theorem, \(f(x) = (x - a_1)h_1(x)\) for some \(h_1(x) \in F[x]\). If \(h_1(x)\) has a root \(a_2\) in \(F\), then by the Factor Theorem

\[ f(x) = (x - a_1)(x - a_2)h_2(x) \]

for some \(h_2(x) \in F[x]\). If \(h_2(x)\) has a root \(a_3\) in \(F\), repeat this procedure and continue doing so until you reach one of these situations:

1. \(f(x) = (x - a_1)(x - a_2) \cdots (x - a_n)h_n(x)\) with \(h_n(x)\) having no root in \(F\).
2. \(f(x) = (x - a_1)(x - a_2) \cdots (x - a_k)h_k(x)\) and \(h_k(x)\) has no root in \(F\).

In Case (1), by Theorem 4.2, we have

\[ \text{deg}(f(x)) = \text{deg}(x - a_1) + \text{deg}(x - a_2) + \cdots + \text{deg}(x - a_n) + \text{deg}(h_n(x)) n = 1 + 1 + \cdots + 1 + \text{deg}(h_n(x)) = n + \text{deg}(h_n(x)). \]

Thus, \(\text{deg}(h_n(x)) = 0\), so \(h_n(x) = c\) for some constant \(c \in F\), and \(f(x)\) factors as

\[ f(x) = (x - a_1)(x - a_2) \cdots (x - a_n). \]

Clearly, the \(n\) numbers \(a_1, a_2, \ldots, a_n\) are the only roots of \(f(x)\).

The argument in Case (2) is essentially the same (just replace \(n\) by \(k\) and leads to this conclusion: \(n = \text{deg}(f(x)) = k + \text{deg}(h_k(x))\). So the number of roots is \(k\) and \(k \leq n\). \(\blacksquare\)

Corollary 4.18

Let \(F\) be a field and \(f(x) \in F[x]\), with \(\text{deg}(f(x)) \geq 2\). If \(f(x)\) is irreducible in \(F[x]\), then \(f(x)\) has no roots in \(F\).

Proof

If \(f(x)\) is irreducible, then it has no factor of the form \(x - a\) in \(F[x]\). Therefore, \(f(x)\) has no roots in \(F\) by the Factor Theorem. \(\blacksquare\)

See exercise 29 for alternative proof by induction.

The converse of Corollary 4.18 is false in general. For example, \(x^4 + 2x^2 + 1 = (x^2 + 1)(x^2 + 1)\) has no roots in \(\mathbb{Q}\) but is reducible in \(\mathbb{Q}[x]\). However, the converse is true for degrees 2 and 3.

Corollary 4.19

Let \(F\) be a field and let \(f(x) \in F[x]\) be a polynomial of degree 2 or 3. Then \(f(x)\) is irreducible in \(F[x]\) if and only if \(f(x)\) has no roots in \(F\).

Proof

Suppose \(f(x)\) is irreducible. Then \(f(x)\) has no roots in \(F\) by Corollary 4.18. Conversely, suppose that \(f(x)\) has no roots in \(F\). Then \(f(x)\) has no first-degree factor in \(F[x]\) because every first-degree polynomial \(x + d\) in \(F[x]\) has a root in \(F\), namely \(-c^{-1}d\). Therefore, if \(f(x) = r(x)s(x)\), neither \(r(x)\) nor \(s(x)\) has degree 1. By Theorem 4.2, \(\text{deg}(f(x)) = \text{deg}(r(x)) + \text{deg}(s(x))\). Since \(f(x)\) has degree 2 or 3, the only possibilities for \((\text{deg}(r(x)), \text{deg}(s(x)))\) are \((2,0)\) or \((0,2)\) and \((3,0)\) or \((0,3)\). So either \(r(x)\) or \(s(x)\) must have degree 0, that is, either \(r(x)\) or \(s(x)\) is a nonzero constant. Hence, \(f(x)\) is irreducible by Theorem 4.12. \(\blacksquare\)

Example 8

To show that \(x^3 + x + 1\) is irreducible in \(\mathbb{Z}_5[x]\), you need only verify that none of \(0, 1, 2, 3, 4 \in \mathbb{Z}_5\) is a root.

Corollary 4.20

Let \(F\) be an infinite field and \(f(x), g(x) \in F[x]\). Then \(f(x)\) and \(g(x)\) induce the same function from \(F\) to \(F\) if and only if \(f(x) = g(x)\) in \(F[x]\).

Proof

Suppose that \(f(x)\) and \(g(x)\) induce the same function from \(F\) to \(F\). Then \(f(a) = g(a)\), so that \(f(a) - g(a) = 0_F\), for every \(a \in F\). This means that every element of \(F\) is a root of the polynomial \(f(x) - g(x)\). Since \(F\) is infinite, this is impossible by Corollary 4.17 unless \(f(x) - g(x)\) is the zero polynomial, that is, \(f(x) = g(x)\). The converse is obvious. \(\blacksquare\)