A polynomial f(x) divides a polynomial g(x) if there exists a polynomial q(x) such that $g(x)=f(x)q(x)$.

Our first result shows that the familiar long division process for polynomials with real coefficients is valid for polynomials with coefficients from an arbitrary field.

We begin by establishing the existence of q(x) and r(x) that satisfy (1). If $n<m$, take $q(x)=0$ and $r(x)=f(x)$ to satisfy (1). Otherwise, if $0\le m\le n$, we apply mathematical induction on n. First suppose that $n=0$. Then $m=0$, and it follows that f(x) and g(x) are nonzero constants. Hence we may take $q(x)=f(x)/g(x)$ and $r(x)=0$ to satisfy (1).

Now suppose that the result is valid for all polynomials with degree less than n for some fixed $n>0$, and assume that f(x) has degree n. Suppose that

and

and let h(x) be the polynomial defined by

Then h(x) is a polynomial of degree $k<n$, and therefore we may apply the induction hypothesis or the case where $k<m$ (whichever is relevant) to obtain polynomials $q_1(x)$ and r(x) such that r(x) has degree less than m and

Combining (2) and (3) and solving for f(x) gives us $f(x)=q(x)g(x)+r(x)$ with $q(x)=a_n{b}_m^{-1}{x}^{n-m}+q_1(x)$, which establishes the existence of q(x) and r(x) by mathematical induction.

We now show the uniqueness of q(x) and r(x). Suppose that $q_1(x),q_2(x),r_1(x)$, and $r_2(x)$ exist such that $r_1(x)$ and $r_2(x)$ each has degree less than m and

Then

The right side of (4) is a polynomial of degree less than m. Since g(x) has degree m, it must follow that $q_1(x)-q_2(x)$ is the zero polynomial. Hence $q_1(x)=q_2(x)$, and thus $r_1(x)=r_2(x)$ by (4).

In the context of Theorem E.1, we call q(x) and r(x) the quotient and remainder, respectively, for the division of f(x) by g(x). For example, suppose that F is the field of complex numbers. Then the quotient and remainder for the division of

by

are, respectively,

Let f(x) be a polynomial of positive degree, and let $a\in F$. Then $f(a)=0$ if and only if $x-a$ divides f(x).

Suppose that $x-a$ divides f(x). Then there exists a polynomial q(x) such that $f(x)=(x-a)q(x)$. Thus $f(a)=(a-a)q(a)=0\cdot q(a)=0$.

Conversely, suppose that $f(a)=0$. By the division algorithm, there exist polynomials q(x) and r(x) such that r(x) has degree less than 1 and

Substituting a for x in the equation above, we obtain $r(a)=0$. Since r(x) has degree less than 1, it must be the constant polynomial $r(x)=\mathit{0}$. Thus $f(x)=q(x)(x-a)$.

For any polynomial f(x) with coefficients from a field F, an element $a\in F$ is called a zero of f(x) if $f(a)=0$. With this terminology, the preceding corollary states that a is a zero of f(x) if and only if $x-a$ divides f(x).

Any polynomial of degree $n\ge 1$ has at most n distinct zeros.

The proof is by mathematical induction on n. The result is obvious if $n=1$. Now suppose that the result is true for some positive integer n, and let f(x) be a polynomial of degree $n+1$. If f(x) has no zeros, then there is nothing to prove. Otherwise, if a is a zero of f(x), then by Corollary 1 we may write $f(x)=(x-a)q(x)$ for some polynomial q(x). Note that q(x) must be of degree n; therefore, by the induction hypothesis, q(x) can have at most n distinct zeros. Since any zero of f(x) distinct from a is also a zero of q(x), it follows that f(x) can have at most $n+1$ distinct zeros.

Polynomials having no common divisors arise naturally in the study of canonical forms. (See Chapter 7.)

Polynomials $f_1(x),f_2(x),\dots ,f_n(x)$ are called relatively prime if no polynomial of positive degree divides all of them.

For example, the polynomials with real coefficients $f(x)=x^2(x-1)$ and $h(x)=(x-1)(x-2)$ are not relatively prime because $x-1$ divides each of them. On the other hand, consider f(x) and $g(x)=(x-2)(x-3)$, which do not appear to have common factors. Could other factorizations of f(x) and g(x) reveal a hidden common factor? We will soon see (Theorem E.9) that the preceding factors are the only ones. Thus f(x) and g(x) are relatively prime because they have no common factors of positive degree.

If $f_1(x)$ and $f_2(x)$ are relatively prime polynomials, there exist polynomials $q_1(x)$ and $q_2(x)$ such that

where 1 denotes the constant polynomial with value 1.

Without loss of generality, assume that the degree of $f_1(x)$ is greater than or equal to the degree of $f_2(x)$. The proof is by mathematical induction on the degree of $f_2(x)$. If $f_2(x)$ has degree 0, then $f_2(x)$ is a nonzero constant c. In this case, we can take $q_1(x)=\mathit{0}$ and $q_2(x)=1/c$.

Now suppose that the theorem holds whenever the polynomial of lesser degree has degree less than n for some positive integer n, and suppose that $f_2(x)$ has degree n. By the division algorithm, there exist polynomials q(x) and r(x) such that r(x) has degree less than n and

Since $f_1(x)$ and $f_2(x)$ are relatively prime, r(x) is not the zero polynomial. We claim that $f_2(x)$ and r(x) are relatively prime. Suppose otherwise; then there exists a polynomial g(x) of positive degree that divides both $f_2(x)$ and r(x). Hence, by (5), g(x) also divides $f_1(x)$, contradicting the fact that $f_1(x)$ and $f_2(x)$ are relatively prime. Since r(x) has degree less than n, we may apply the induction hypothesis to $f_2(x)$ and r(x). Thus there exist polynomials $g_1(x)$ and $g_2(x)$ such that

Combining (5) and (6), we have

Thus, setting $q_1(x)=g_2(x)$ and $q_2(x)=g_1(x)-g_2(x)q(x)$, we obtain the desired result.

The proof is by mathematical induction on n, the number of polynomials. The preceding lemma establishes the case $n=2$.

Now assume the result is true for fewer than n polynomials, for some $n\ge 3$. We will first consider the trivial case where the first $n-1$ polynomials are relatively prime. By the induction hypothesis, there exist polynomials $q_1(x),q_2(x),\dots ,q_{n-1}(x)$ such that

Setting $q_n(x)=\mathit{0}$, the zero polynomial, we have

which proves the result if the first $n-1$ polynomials are relatively prime.

Now suppose that the first $n-1$ polynomials are not relatively prime, and let g(x) be the monic polynomial of maximum positive degree that divides each of these polynomials. For $k=1,2,\dots ,n-1$, let $h_k(x)$ be the polynomial defined by $f_k(x)=g(x)h_k(x)$. Then the polynomials $h_1(x),h_2(x),\dots ,h_{n-1}(x)$ are relatively prime. So by the induction hypothesis, there exist polynomials ${\varphi }_1(x),{\varphi }_2(x),\dots ,{\varphi }_{n-1}(x)$ such that

Multiplying both sides of this equation by g(x), we obtain

Note that g(x) and $f_n(x)$ are relatively prime, and hence there exist polynomials p(x) and $q_n(x)$ such that

Let $q_i(x)=p(x){\varphi }_i(x)$ for $i=1,2,\dots ,n-1$. Then combining the two preceding equations yields

which completes the induction argument.

Let

be a polynomial with coefficients from a field F. If T is a linear operator on a vector space V over F, we define

Similarly, if A is an $n\times n$ matrix with entries from F, we define

Exercise.

Exercise.

Exercise.

In Chapters 5 and 7, we are concerned with determining when a linear operator T on a finite-dimensional vector space can be diagonalized and with finding a simple (canonical) representation of T. Both of these problems are affected by the factorization of a certain polynomial determined by T (the characteristic polynomial of T). In this setting, particular types of polynomials play an important role.

A polynomial f(x) with coefficients from a field F is called monic if its leading coefficient is 1. If f(x) has positive degree and cannot be expressed as a product of polynomials with coefficients from F each having positive degree, then f(x) is called irreducible.

Observe that whether a polynomial is irreducible depends on the field F from which its coefficients come. For example, $f(x)=x^2+1$ is irreducible over the field of real numbers, but it is not irreducible over the field of complex numbers since $x^2+1=(x+i)(x-i)$.

Clearly any polynomial of degree 1 is irreducible. Moreover, for polynomials with coefficients from an algebraically closed field, the polynomials of degree 1 are the only irreducible polynomials.

The following facts are easily established.

Exercise.

Exercise.

Suppose that $\varphi (x)$ does not divide f(x). Then $\varphi (x)$ and f(x) are relatively prime by Theorem E.6, and so there exist polynomials $q_1(x)$ and $q_2(x)$ such that

Multiplying both sides of this equation by g(x) yields

Since $\varphi (x)$ divides f(x)g(x), there is a polynomial h(x) such that $f(x)g(x)=\varphi (x)h(x).$ Thus (7) becomes

So $\varphi (x)$ divides g(x).

Let $\varphi (x),{\varphi }_1(x),{\varphi }_2(x),\dots ,{\varphi }_n(x)$ be irreducible monic polynomials. If $\varphi (x)$ divides the product ${\varphi }_1(x){\varphi }_2(x)\cdots {\varphi }_n(x),$ then $\varphi (x)={\varphi }_i(x)$ for some $i(i=1,2,\dots ,n)$.

We prove the corollary by mathematical induction on n. For $n=1,$ the result is an immediate consequence of Theorem E.7. Suppose then that for some $n>1,$ the corollary is true for any $n-1$ irreducible monic polynomials, and let ${\varphi }_1(x),{\varphi }_2(x),\dots ,{\varphi }_n(x)$ be n irreducible polynomials. If $\varphi (x)$ divides

then $\varphi (x)$ divides the product ${\varphi }_1(x){\varphi }_2(x)\cdots {\varphi }_{n-1}(x)$ or $\varphi (x)$ divides ${\varphi }_n(x)$ by Theorem E.8. In the first case, $\varphi (x)={\varphi }_i(x)$ for some $i(i=1,2,\dots ,n-1)$ by the induction hypothesis; in the second case, $\varphi (x)={\varphi }_n(x)$ by Theorem E.7.

We are now able to establish the unique factorization theorem, which is used throughout Chapters 5 and 7. This result states that every polynomial of positive degree is uniquely expressible as a constant times a product of irreducible monic polynomials.

We begin by showing the existence of such a factorization using mathematical induction on the degree of f(x). If f(x) is of degree 1, then $f(x)=ax+b$ for some constants a and b with $a\ne 0.$ Setting $\varphi (x)=x+b/a,$ we have $f(x)=a\varphi (x).$ Since $\varphi (x)$ is an irreducible monic polynomial, the result is proved in this case. Now suppose that the conclusion is true for any polynomial with positive degree less than some integer $n>1,$ and let f(x) be a polynomial of degree n. Then

for some constants $a_i$ with $a_n\ne 0.$ If f(x) is irreducible, then

is a representation of f(x) as a product of $a_n$ and an irreducible monic polynomial. If f(x) is not irreducible, then $f(x)=g(x)h(x)$ for some polynomials g(x) and h(x), each of positive degree less than n. The induction hypothesis guarantees that both g(x) and h(x) factor as products of a constant and powers of distinct irreducible monic polynomials. Consequently $f(x)=g(x)h(x)$ also factors in this way. Thus, in either case, f(x) can be factored as a product of a constant and powers of distinct irreducible monic polynomials.

It remains to establish the uniqueness of such a factorization. Suppose that

where c and d are constants, ${\varphi }_i(x)$ and ${\psi }_j(x)$ are irreducible monic polynomials, and $n_i$ and $m_j$ are positive integers for $i=1,2,\dots ,k$ and $j=1,2,\dots ,r.$ Clearly both c and d must be the leading coefficient of f(x); hence $c=d.$ Dividing by c, we find that (8) becomes

So ${\varphi }_i(x)$ divides the right side of (9) for $i=1,2,\dots ,k.$ Consequently, by the corollary to Theorem E.8, each ${\varphi }_i(x)$ equals some ${\psi }_j(x),$ and similarly, each ${\psi }_j(x)$ equals some ${\varphi }_i(x).$ We conclude that $r=k$ and that, by renumbering if necessary, ${\varphi }_i(x)={\psi }_i(x)$ for $i=1,2,\dots ,k.$ Suppose that $n_i\ne m_i$ for some i. Without loss of generality, we may suppose that $i=1$ and $n_1>m_1.$ Then by canceling ${[{\varphi }_1(x)]}^{m_1}$ from both sides of (9), we obtain

Since $n_1-m_1>0,{\varphi }_1(x)$ divides the left side of (10) and hence divides the right side also. So ${\varphi }_1(x)={\varphi }_i(x)$ for some $i=2,\dots ,k$ by the corollary to Theorem E.8. But this contradicts that ${\varphi }_1(x),{\varphi }_2(x),\dots ,{\varphi }_k(x)$ are distinct. Hence the factorizations of f(x) in (8) are the same.

It is often useful to regard a polynomial $f(x)=a_n{x}^n+\cdots +a_{1}x+a_0$ with coefficients from a field F as a function $f:F\to F.$ In this case, the value of f at $c\in F$ is $f(c)=a_n{c}^n+\cdots +a_{1}c+a_0.$ Unfortunately, for arbitrary fields there is not a one-to-one correspondence between polynomials and polynomial functions. For example, if $f(x)=x^2$ and $g(x)=x$ are two polynomials over the field $Z_2$ (defined in Example 4 of Appendix C), then f(x) and g(x) have different degrees and hence are not equal as polynomials. But $f(a)=g(a)$ for all $a\in Z_2,$ so that f and g are equal polynomial functions. Our final result shows that this anomaly cannot occur over an infinite field.

Suppose that $f(a)=g(a)$ for all $a\in F.$ Define $h(x)=f(x)-g(x),$ and suppose that h(x) is of degree $n\ge 1.$ It follows from Corollary 2 to Theorem E.1 that h(x) can have at most n zeroes. But

for every $a\in F,$ contradicting the assumption that h(x) has positive degree. Thus h(x) is a constant polynomial, and since $h(a)=0$ for each $a\in F,$ it follows that h(x) is the zero polynomial. Hence $f(x)=g(x)$.