§4.1 Polynomial Arithmetic and the Division Algorithm
The underlying idea here is to define "polynomial" in a way that is the obvious extension of polynomials with real-number coefficients. Let \( R \) be any ring. A polynomial with coefficients in \( R \) is an expression of the form
\[ a_0 + a_1x + a_2x^2 + \cdots + a_nx^n, \]
where \( n \) is a nonnegative integer and \( a_i \in R \).
This informal definition raises several questions: What is \( x \)? Is it an element of \( R \)? If not, what does it mean to multiply \( x \) by a ring element? In order to answer these questions, note that an expression of the form \( a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \) makes sense, provided that the \( a_i \) and \( x \) are all elements of some larger ring. An analogy might be helpful here. The number \( x \) is not in the ring \( \mathbb{Z} \) of integers, but expressions such as \( 3 - 4\pi + 12\pi^2 + \pi^3 \) and \( 8 - \pi^2 + 6\pi^3 \) make sense in the real numbers. Furthermore, it is not difficult to verify that the set of all numbers of the form
\[ a_0 + a_1\pi + a_2\pi^2 + \cdots + a_n\pi^n, \]
where \( n \geq 0 \) and \( a_i \in \mathbb{Z} \)
is a subring of \( \mathbb{R} \) that contains both \( \mathbb{Z} \) and \( \pi \) (Exercise 2).
For the present we shall think of polynomials with coefficients in a ring \( R \) much the same way, as elements of a larger ring that contains both \( R \) and a special element \( x \) that is not in \( R \). This is analogous to the situation in the preceding paragraph with \( R \) in place of \( \mathbb{Z} \) and \( x \) in place of \( \pi \), except that here we do not need to identify the element \( x \) or even if such a larger ring exists. The following theorem provides the answer, as well as a definition of "polynomial."
Theorem 4.1
If \( R \) is a ring, then there exists a ring \( T \) containing an element \( x \) that is not in \( R \) and has these properties:
- \( R \) is a subring of \( T \).
- \( xa = ax \) for every \( a \in R \).
- The set \( R[x] \) of all elements of \( T \) of the form \[ a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \quad \text{(where } n \geq 0 \text{ and } a_i \in R) \] is a subring of \( T \) that contains \( R \).
- The representation of elements of \( R[x] \) is unique: If \( n \leq m \) and \[ a_0 + a_1x + \cdots + a_nx^n = b_0 + b_1x + \cdots + b_mx^m, \] then \( a_i = b_i \) for \( i = 1, 2, \dots, n \) and \( b_i = 0_R \) for each \( i > n \).
- \[ a_0 + a_1x + a_2x^2 + \cdots + a_nx^n = 0_R \] if and only if \( a_i = 0_R \) for every \( i \).
Proof: See Appendix G. We shall assume Theorem 4.1 here.
The elements of the ring \( R[x] \) in Theorem 4.1 (iii) are called polynomials with coefficients in \( R \) and the elements \( a_i \) are called coefficients. The special element \( x \) is called the indeterminate.
To avoid any misunderstandings in Theorem 4.1, please note the following facts:
- Property (ii) of Theorem 4.1 does not imply that the ring \( T \) is commutative, but only that the special element \( x \) commutes with each element of the subring \( R \) (whose elements may not necessarily commute with each other).
- Property (v) is the special case of property (iv) when each \( b_i = 0_R \).
- The first expression in property (v) is not an equation to be solved for \( x \). In this context, asking what value of \( x \) makes \[ a_0 + a_1x + a_2x^2 + \cdots + a_nx^n = 0_R \] is as meaningless as asking what value of \( \pi \) makes \[ 3 + 5\pi - 7\pi^2 = 0 \] because \( x \) (like \( \pi \)) is a specific element of a ring, not a variable that can be assigned values.
Example 1
The rings \( \mathbb{Z}[x] \), \( \mathbb{Q}[x] \), and \( \mathbb{R}[x] \) are the rings you are familiar with from high school. For instance, \( 3 + 5x - 7x^2 \) is in all three of these rings, but \( 3 + 7.5x^2 \) is only in \( \mathbb{Q}[x] \) and \( \mathbb{R}[x] \) because the coefficient 7.5 is not an integer. Similarly, \( 4.2 + 3x + \sqrt{5}x^4 \) is in \( \mathbb{R}[x] \) but not in the other two rings since \( \sqrt{5} \) is not a rational number. Terms with zero coefficients are usually omitted, as they were in the preceding sentence.
Example 2
Let \( E \) be the ring of even integers. Then \( 4 - 6x + 4x^3 \in E[x] \). However, the polynomial \( x \) is not in \( E[x] \), because it cannot be written with even coefficients.
Polynomial Arithmetic
The rules for adding and multiplying polynomials follow directly from the fact that \( R[x] \) is a ring.
Example 3
If \( f(x) = 1 + 5x - x^2 + 4x^3 + 2x^4 \) and \( g(x) = 4 + 2x + 3x^2 + x^3 \) in \( \mathbb{Z}_7[x] \), then the commutative, associative, and distributive laws show that
\[ \begin{align*} f(x) + g(x) & = (1 + 5x - x^2 + 4x^3 + 2x^4) + (4 + 2x + 3x^2 + x^3) \\ & = (1 + 4) + (5 + 2)x + (-1 + 3)x^2 + (4 + 1)x^3 + (2 + 0)x^4 \\ & = 5 + 7x + 2x^2 + 5x^3 + 2x^4 \quad = 5 + 0x + 2x^2 + 5x^3 + 2x^4. \end{align*} \]Example 4
The product of \( 1 - 7x + x^2 \) and \( 2 + 3x \) in \( \mathbb{Q}[x] \) is found by using the distributive law repeatedly:
\[ \begin{align*} (1 - 7x + x^2)(2 + 3x) & = 1(2 + 3x) - 7x(2 + 3x) + x^2(2 + 3x) \\ & = 1(2) + 1(3x) - 7x(2) - 7x(3x) + x^2(2) + x^2(3x) \\ & = 2 + 3x - 14x - 21x^2 + 2x^2 + 3x^3 \\ & = 2 - 11x - 19x^2 + 3x^3. \end{align*} \]The preceding examples are typical of the general case. You add polynomials by adding the corresponding coefficients, and you multiply polynomials by using the distributive laws and collecting like powers of \( x \). Thus polynomial addition is given by the rule:
\[ (a_0 + a_1x + a_2x^2 + \cdots + a_nx^n) + (b_0 + b_1x + b_2x^2 + \cdots + b_mx^m) = (a_0 + b_0) + (a_1 + b_1)x + (a_2 + b_2)x^2 + \cdots + (a_n + b_n)x^n \]and polynomial multiplication is given by the rule:
\[ (a_0 + a_1x + a_2x^2 + \cdots + a_nx^n)(b_0 + b_1x + b_2x^2 + \cdots + b_mx^m) \]The product is:
\[ a_0b_0 + a_0b_1x + a_0b_2x^2 + \cdots + a_0b_mx^m + a_1b_0x + a_1b_1x^2 + \cdots + a_nb_mx^{n+m}. \]It follows readily from this description of multiplication in \( R[x] \) that if \( R \) is commutative, then so is \( R[x] \) (Exercise 7). Furthermore, if \( R \) has a multiplicative identity \( 1_R \), then \( 1_R \) is also the multiplicative identity of \( R[x] \) (Exercise 8).
Definition
Let \( f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \) be a polynomial in \( R[x] \) with \( a_n \neq 0_R \). Then \( a_n \) is called the leading coefficient of \( f(x) \). The degree of \( f(x) \) is the integer \( n \); it is denoted "deg \( f(x) \)". In other words, the degree of \( f(x) \) is the largest exponent of \( x \) that appears with a nonzero coefficient, and this coefficient is the leading coefficient.
Example 5
The degree of \( 3 - x + 4x^2 - 7x^3 \in \mathbb{R}[x] \) is 3, and its leading coefficient is \( -7 \). Similarly, deg \( (3 + 5x) = 1 \) and deg \( (x^{12}) = 12 \). The degree of \( 2 + x + 4x^2 - 0x^3 + 0x^5 \) (the largest exponent of \( x \) with a nonzero coefficient) is 2; its leading coefficient is 4.
The ring \( R \) that we start with is a subring of the polynomial ring \( R[x] \). The elements of \( R \), considered as polynomials in \( R[x] \), are called constant polynomials. The polynomials of degree 0 in \( R[x] \) are precisely the nonzero constant polynomials. Note that the constant polynomial \( 0_R \) does not have a degree (because no power of \( x \) appears with a nonzero coefficient).
Theorem 4.2
If \( R \) is an integral domain and \( f(x), g(x) \) are nonzero polynomials in \( R[x] \), then
\[ \text{deg}(f(x)g(x)) = \text{deg}(f(x)) + \text{deg}(g(x)). \]Proof: Suppose \( f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n \) and \( g(x) = b_0 + b_1x + b_2x^2 + \cdots + b_mx^m \) with \( a_n \neq 0_R \) and \( b_m \neq 0_R \), so that \( \text{deg}(f(x)) = n \) and \( \text{deg}(g(x)) = m \). Then
\[ f(x)g(x) = a_0b_0 + (a_0b_1 + a_1b_0)x + (a_0b_2 + a_1b_1 + a_2b_0)x^2 + \cdots + a_nb_mx^{n+m}. \]The largest exponent of \( x \) that can possibly have a nonzero coefficient is \( n + m \). But \( a_nb_m \neq 0_R \) because \( R \) is an integral domain and \( a_n \neq 0_R \) and \( b_m \neq 0_R \). Therefore, \( f(x)g(x) \) is nonzero and \( \text{deg}(f(x)g(x)) = n + m = \text{deg}(f(x)) + \text{deg}(g(x)) \). \( \blacksquare \)
Corollary 4.3
If \( R \) is an integral domain, then so is \( R[x] \).
Proof: Since \( R \) is a commutative ring with identity, so is \( R[x] \) (Exercises 7 and 8). The proof of Theorem 4.2 shows that the product of nonzero polynomials in \( R[x] \) is nonzero. Therefore, \( R[x] \) is an integral domain. \( \blacksquare \)
The first five lines of the proof of Theorem 4.2 are valid in any ring and lead to this conclusion.
Corollary 4.4
Let \( R \) be a ring. If \( f(x), g(x) \), and \( f(x)g(x) \) are nonzero in \( R[x] \), then
\[ \text{deg}(f(x)g(x)) \leq \text{deg}(f(x)) + \text{deg}(g(x)). \]Example 6
In \( \mathbb{Z}_6[x] \), let \( f(x) = 2x^4 \) and \( g(x) = 5x \). Then \( f(x)g(x) = (2x^4)(5x) = 4x^5 \), so \( \text{deg}(f(x)g(x)) = \text{deg}(f(x)) + \text{deg}(g(x)) \). However, if \( g(x) = 1 + 3x^2 \), then
\[ f(x)g(x) = 2x^4(1 + 3x^2) = 2x^4 + 2 \cdot 3x^6 = 2x^4 + 6x^6 = 2x^4, \]which has degree 4. But \( \text{deg}(f(x)) + \text{deg}(g(x)) = 6 \). So, \( \text{deg}(f(x)g(x)) < \text{deg}(f(x)) + \text{deg}(g(x)) \).
For information on the degree of the sum of polynomials, see Exercises 4 and 12.
Corollary 4.5
Let \( R \) be an integral domain and \( f(x) \in R[x] \). Then \( f(x) \) is a unit in \( R[x] \) if and only if \( f(x) \) is a constant polynomial that is a unit in \( R \). In particular, if \( F \) is a field, the units in \( F[x] \) are the nonzero constants in \( F \).
Remember that the proof of an "if and only if" statement requires two separate proofs.
Example 7
The only units in \( \mathbb{Z}[x] \) are 1 and -1, since these are the only units in \( \mathbb{Z} \). The units in \( \mathbb{R}[x] \), \( \mathbb{Q}[x] \), or \( \mathbb{C}[x] \) are all nonzero constants, since \( \mathbb{R} \), \( \mathbb{Q} \), and \( \mathbb{C} \) are fields.
Corollary 4.5 may be false if \( R \) is not an integral domain (Exercise 11).
Example 8
\( 5x + 1 \) is a unit in \( \mathbb{Z}_5[x] \) that is not a constant because (as you should verify)
\[ (5x + 1)(20x + 1) = 1. \]The Division Algorithm in \( F[x] \)
Our principal interest in the rest of this chapter will be polynomials with coefficients in a field \( F \) (such as \( \mathbb{Q} \) or \( \mathbb{R} \) or \( \mathbb{Z}_5 \)). As noted in the chapter introduction, the domain \( F[x] \) has many of the same properties as the domain \( \mathbb{Z} \) of integers, including the Division Algorithm (Theorem 1.1), which states that for any integers \( a \) and \( b \) with \( b \) positive, there exist unique integers \( q \) and \( r \) such that
\[ a = bq + r \quad \text{and} \quad 0 \leq r < b. \]For polynomials, the only changes are to require the divisor to be nonzero and to replace the statement "0 \leq r < b" by a statement involving degrees. Here is the formal statement (with \( f(x) \) in place of \( a \), \( g(x) \) in place of \( b \), and \( r(x) \) in place of \( q \), respectively):
Theorem 4.6: The Division Algorithm in \( F[x] \)
Let \( F \) be a field and \( f(x), g(x) \in F[x] \) with \( g(x) \neq 0_F \). Then there exist unique polynomials \( q(x) \) and \( r(x) \) such that
\[ f(x) = g(x)q(x) + r(x) \]and either \( r(x) = 0_F \) or \( \text{deg}(r(x)) < \text{deg}(g(x)) \).
Example 9 shows how polynomial division works and why the Division Algorithm is valid in one particular case.
Example 9
We shall divide \( f(x) = 3x^5 + 2x^4 + 2x^3 + 4x^2 + x - 2 \) by \( g(x) = 2x^3 + 1 \). The italic column on the right keeps track of what happens at each step:
\[ \begin{array}{r} \frac{3}{2}x^2 + \phantom{0} x + \phantom{00} 1 \phantom{00000000000000} \\ 2x^3 + 1 \enclose{longdiv}{3x^5 + 2x^4 + 2x^3 + 4x^2 + x - 2}\\ \underline{3x^5 +\phantom{00000000000} \frac{3}{2}x^2 \phantom{0000000}}\\ 2x^4 + 2x^3 + \frac{5}{2}x^2 + x - 2 \\ \underline{2x^4 \phantom{00000000000} + x \phantom{0000}} \\ 2x^3 + \frac{5}{2}x^2 \phantom{0000} - 2 \\ \underline{2x^3 \phantom{0000000000} + 1} \\ \frac{5}{2}x^2 \phantom{0000} - 3 \\ \end{array} \]We start by dividing the leading term of \( f(x) \), \( 3x^5 \), by the leading term of \( g(x) \), \( 2x^3 \), which gives the first term of the quotient, \( \frac{3}{2}x^2 \). We then multiply \( \frac{3}{2}x^2 \) by \( g(x) \), subtract the result from \( f(x) \), and proceed with the next term, repeating the process until the remainder has a degree smaller than the divisor.
This results in:
\[ f(x) - \left(\frac{3}{2}x^2\right)g(x) - xg(x) - 1g(x) = f(x) - g(x)\left(\frac{3}{2}x^2 + x + 1\right) = f(x) - g(x)q(x). \]Where \( g(x) = 2x^3 + 1 \) is the divisor and \( r(x) = \frac{5}{2}x^2 - 3 \) is the remainder. Thus, we have:
\[ f(x) = g(x)q(x) + r(x). \]Therefore, the Division Algorithm holds for the polynomials \( f(x) \) and \( g(x) \).
Division Refresher: The first term of the quotient \( \left(\frac{3}{2}x^2\right) \) is obtained by dividing the leading term of the dividend (\( 3x^5 \)) by the leading term of the divisor (\( 2x^3 \)): \( 3x^5/2x^3 = \frac{3}{2}x^2 \). The product of this term and the divisor \( \left(\frac{3}{2}x^2g(x)\right) \) is then subtracted from the dividend, resulting in \( 2x^3 + 5/2x^2 + x - 2 \), as shown. The process is repeated, using this last expression as the dividend and the same divisor, and continues until you reach a polynomial with degree smaller than the degree of the divisor.
Of course, an example is not a proof, even though you can readily convince yourself that the same procedure works with other divisors and dividends (Exercise 5). Consequently, skipping the proof until you are familiar with the mathematical induction would be quite reasonable. That’s why the proof of Theorem 4.6 is marked as optional.
Proof of Theorem 4.6: The Division Algorithm
We first prove the existence of the polynomials \( q(x) \) and \( r(x) \).
Case 1: If \( f(x) = 0_F \) or if \( \text{deg}(f) < \text{deg}(g) \), then the theorem is true with \( q(x)=0 \) and \( r(x)=f(x) \) because \( f(x)=g(x)0_F + f(x) \).
Case 2: If \( f(x) \neq 0_F \) and \( \text{deg}(g) \leq \text{deg}(f) \), then the proof of existence is by induction on the degree of the dividend \( f(x) \). If \( \text{deg}(f(x)) = 0 \), then \( \text{deg}(g(x)) = 0 \) also. Hence, \( f(x) = a = g(x) = b \) for some nonzero \( a, b \in F \). Since \( F \) is a field, \( b \) is a unit and \( a = b(b^{-1}a) + 0_F \). Thus, the theorem is true with \( g(x) = b^{-1}a \) and \( r(x) = 0_F \).
Assume inductively that the theorem is true whenever the dividend has degree less than \( n \). This part of the proof is presented in two columns. The left-hand column is the formal proof, while the right-hand column refers to Example 9. The example will help you understand what’s being done in the proof.
Proof
We must show that the theorem is true whenever the dividend \( f(x) \) has degree \( n \), say
\[ f(x) = a_nx^n + \cdots + a_1x + a_0 \]with \( a_n \neq 0_F \). The divisor \( g(x) \) must have the form
\[ g(x) = b_mx^m + \cdots + b_1x + b_0 \]with \( b_m \neq 0_F \) and \( m \leq n \). We begin as we would in the long division of \( g(x) \) into \( f(x) \). Since \( F \) is a field and \( b_m \neq 0_F \), \( b_m \) is a unit. Multiply the divisor \( g(x) \) by \( a_nb_m^{-1}x^{n-m} \) to obtain:
\[ a_nb_m^{-1}x^{n-m}g(x) = a_nb_m^{-1}b_mx^{n-m} + \cdots + a_nb_m^{-1}b_0x^{n-m}. \]Subtract this from \( f(x) \) to obtain a polynomial of degree less than \( n \):
Example 10
Let \( n = 5 \):
\[ f(x) = 3x^5 + 2x^4 + 2x^3 + 4x^2 + x - 2 \] \[ a_nx^n = 3x^5 \]Let \( m = 3 \):
\[ g(x) = 2x^3 + 1 \] \[ b_mx^m = 2x^3 \]Multiply to obtain:
\[ a_nb_m^{-1}x^{n-m}g(x) = 3 \cdot 2^{-1}x^{5-3} = \frac{3}{2}x^2 \]This gives us the first term of the quotient:
\[ \frac{3}{2}x^2 \]Subtract to obtain:
\[ 2x^4 + 2x^3 + \frac{5}{2}x^2 + x - 2 \]This is the dividend for the next step.
We use the Principle of Complete Induction; see Appendix C.
So,
\[ f(x) - a_nb_m^{-1}x^{n-m}g(x) = f(x) - \left( 3x^5 + \frac{3}{2}x^2 \right) = 2x^4 + 2x^3 + \frac{5}{2}x^2 + x - 2 \]\( q_1(x) = x + 1 \) is the last part of the quotient, and \( r(x) = \frac{5}{2}x^2 - 3 \) is the remainder.
Since \( a_nb_m^{-1}x^{n-m}g(x) \) and \( f(x) \) have the same degree and the same leading coefficient, the difference
\[ f(x) - a_nb_m^{-1}x^{n-m}g(x) \]is a polynomial of degree less than \( n \) (or possibly the zero polynomial). Now apply the induction hypothesis with \( g(x) \) as divisor and the polynomial \( f(x) - a_nb_m^{-1}x^{n-m}g(x) \) as dividend (or use Case 1 if this dividend is zero). By induction, there exist polynomials \( q_1(x) \) and \( r(x) \) such that
\[ f(x) - a_nb_m^{-1}x^{n-m}g(x) = g(x)q_1(x) + r(x) \]and \( r(x) = 0_F \) or \( \text{deg}(r(x)) < \text{deg}(g(x)) \). Therefore, \[ f(x)=g(x)\left( a_nb_m^{-1}x^{n-m} + q_1(x) \right) + r(x) \]
and \( r(x) = 0_F \) or \( \text{deg}(r(x)) < \text{deg}(g(x)) \).
Thus, the theorem is true with \( q(x) = a_nb_m^{-1}x^{n-m} + q_1(x) \) when \( \text{deg}(f(x)) = n \). This completes the induction and shows that \( q(x) \) and \( r(x) \) always exist for any divisor and dividend.
To prove that \( q(x) \) and \( r(x) \) are unique, suppose that \( q_2(x) \) and \( r_2(x) \) are polynomials such that
\[ f(x) = g(x)q_2(x) + r_2(x) \]and \( r_2(x) = 0_F \) or \( \text{deg}(r_2(x)) < \text{deg}(g(x)) \). Then
\[ g(x)q_1(x) + r(x) = g(x)q_2(x) + r_2(x) \]so that
\[ g(x)(q_1(x) - q_2(x)) = r_2(x) - r(x). \]If \( q_1(x) - q_2(x) \) is nonzero, then by Theorem 4.2 the degree of the left side is \( \text{deg}(g(x)) + \text{deg}(q_1(x) - q_2(x)) \), a number greater than or equal to \( \text{deg}(g(x)) \). However, both \( r_2(x) \) and \( r(x) \) have degree strictly less than \( \text{deg}(g(x)) \), and so the right-hand side of the equation must also have degree strictly less than \( \text{deg}(g(x)) \) (Exercise 12). This is a contradiction. Therefore, \( q_1(x) - q_2(x) = 0_F \), or, equivalently, \( q_1(x) = q_2(x) \). Since the left side is zero, we must have \( r_2(x) - r(x) \), so that \( r_2(x) = r(x) \). Thus the polynomials \( q(x) \) and \( r(x) \) are unique.