Polynomial rings and the division algorithm
Long division of polynomials works the way long division of integers does. What must the coefficients allow for it to work, and what does it then say about roots and ideals?
Where you are 4 in Rings
Why this exists
Polynomials were first met as real functions, divided by Polynomial long division and factored through their zeros (The remainder and factor theorems). Algebra needs them with coefficients in \mathbb{Z}_p, \mathbb{Q}, \mathbb{Z} or any commutative ring, and there a polynomial is no longer a function: over \mathbb{Z}_5 the different polynomials x^5 and x agree at every element (Example 4). This lesson builds the ring R[x] from coefficients and proves that over a field F the ring F[x] has a division algorithm, as \mathbb{Z} does (The division algorithm), with consequences for roots and ideals.
Definition
Let R be a commutative ring. A polynomial over R in the indeterminate x is an expression
in which only the coefficients matter. Formally f is the sequence (a_0, a_1, a_2, \dots) of elements of R with a_k = 0 for all but finitely many k, and x^k is the sequence with 1 in place k and 0 elsewhere. Two polynomials are equal when all their coefficients agree. With g(x) = \sum_k b_k x^k, the sum and product are
The set of all polynomials over R is R[x]. An element a \in R is identified with the constant polynomial (a, 0, 0, \dots). If f \ne 0, its degree \deg f is the largest n with a_n \ne 0; a_n is the leading coefficient, and f is monic if a_n = 1. The zero polynomial has no degree here, so a remainder is described as “r = 0 or \deg r < \deg g”.
If R is a subring of a commutative ring S and s \in S, the value of f at s is f(s) = a_n s^n + \dots + a_1 s + a_0 \in S, and s is a root of f if f(s) = 0. The map \psi_s : R[x] \to S, \psi_s(f) = f(s), is evaluation at s.
Intuition
A polynomial is its list of coefficients; x only marks the places, and the rule for c_k is the distributive law with x^i x^j = x^{i + j}. Long division works whenever one can divide by the divisor’s leading coefficient: each step cancels the top term of what is left, so the degree falls below the divisor’s. Over a field that is every nonzero divisor, and as every ideal of \mathbb{Z} is the multiples of its least positive element (Ideals and quotient rings, Theorem 5), every ideal of F[x] is the multiples of its monic element of least degree.
Results
Throughout, R is a commutative ring, D an integral domain and F a field.
Theorem 1 (the polynomial ring). R[x] is a commutative ring whose identity is the constant 1, and the constants form a subring that is a copy of R.
Theorem 2 (degrees). Let f, g \in R[x] be nonzero. (a) If f + g \ne 0, then \deg(f + g) \le \max(\deg f, \deg g). (b) If fg \ne 0, then \deg(fg) \le \deg f + \deg g. If the leading coefficient of g is a unit, or if R is an integral domain, then fg \ne 0 and \deg(fg) = \deg f + \deg g. (c) D[x] is an integral domain, and D[x]^\times = D^\times: its units are the constants that are units of D.
Theorem 3 (division algorithm). Let g \in R[x] be nonzero with leading coefficient a unit of R. For every f \in R[x] there are unique q, r \in R[x] with f = qg + r and r = 0 or \deg r < \deg g. In particular this holds in F[x] for every nonzero g.
Theorem 4 (evaluation). If R is a subring of a commutative ring S and s \in S, then \psi_s : R[x] \to S is a ring homomorphism: (f + g)(s) = f(s) + g(s), (fg)(s) = f(s)g(s), and the constant 1 has value 1.
Corollary 5 (remainder and factor theorems). For f \in R[x] and a \in R, f = (x - a)q + f(a) for a unique q \in R[x]. So a is a root of f if and only if x - a divides f in R[x].
Theorem 6 (roots in a domain). Let f \in D[x] be nonzero of degree n. If a_1, \dots, a_k \in D are distinct roots of f, then (x - a_1)\cdots(x - a_k) divides f. Hence f has at most n roots in D.
Corollary 7 (polynomials and functions). If D is infinite, f, g \in D[x] and f(a) = g(a) for every a \in D, then f = g.
Theorem 8 (ideals of F[x]). Every ideal I of F[x] is principal. If I \ne \{0\}, then I = \langle g \rangle for exactly one monic g, the monic polynomial of least degree in I, and f \in I if and only if g divides f.
Corollary 9 (the quotient by \langle g \rangle). Let g \in F[x] have degree n \ge 1 and I = \langle g \rangle. Each coset f + I contains exactly one r with r = 0 or \deg r < n, namely the remainder of f on division by g. If F is finite, then |F[x]/I| = |F|^n.
Why it is true
Proof of Theorem 1. Addition is coefficientwise, so (R[x], +) is an abelian group with 0 the zero sequence and -f = \sum_k (-a_k)x^k; c_k = 0 once k > \deg f + \deg g, so fg is a polynomial. For h = \sum_l d_l x^l, the laws of R make the coefficient of x^m in both (fg)h and f(gh) equal to \sum_{i + j + l = m} a_i b_j d_l, so multiplication is associative. The sum \sum_{i + j = k} a_i b_j is symmetric in f and g as R is commutative, and \sum_{i + j = k} a_i (b_j + d_j) splits into two sums, which is the distributive law; and 1 \cdot f = f. Constants add and multiply as in R and include 1, so they form a subring (Rings and integral domains, Theorem 3), a copy of R. \square
Proof of Theorem 2. Let \deg f = m with leading coefficient a_m, and \deg g = n with leading coefficient b_n. (a) Beyond \max(m, n) every coefficient of f + g is 0 + 0. (b) In c_k with k > m + n, each term a_i b_j has i > m or j > n, so is 0; and c_{m + n} = a_m b_n. If b_n is a unit, then a_m b_n = 0 would give a_m = a_m b_n b_n^{-1} = 0; in a domain a_m b_n \ne 0 as both factors are nonzero. Either way c_{m + n} \ne 0, so fg \ne 0 and \deg(fg) = m + n. (c) D[x] is commutative with 1 \ne 0 (Theorem 1) and has no zero divisors by (b). If fg = 1, then \deg f + \deg g = 0, so f, g are constants a, b with ab = 1 in D; and a unit of D stays a unit in D[x]. \square
Proof of Theorem 3. Let \deg g = m, with leading coefficient u \in R^\times. Existence, by Strong induction and well-ordering on \deg f. If f = 0 or \deg f < m, take q = 0, r = f. If \deg f = n \ge m with leading coefficient a_n, put
The subtracted polynomial has degree n and leading coefficient a_n u^{-1} u = a_n (Theorem 2(b)), so the x^n terms cancel: f_1 = 0 or \deg f_1 < n. By the case already settled or the induction hypothesis, f_1 = q_1 g + r with r = 0 or \deg r < m, and then f = (q_1 + a_n u^{-1} x^{n - m})g + r.
Uniqueness. If qg + r = q'g + r' with both remainders of the stated kind, then (q - q')g = r' - r. If q \ne q', Theorem 2(b) gives \deg\bigl((q - q')g\bigr) = \deg(q - q') + m \ge m, while r' - r is 0 or of degree below m by Theorem 2(a). So q = q', and then r = r'. In a field every nonzero element is a unit. \square
Proof of Theorem 4. Let f = \sum_i a_i x^i and g = \sum_j b_j x^j. Sums are clear. For products, expand in S, move s^i past b_j (S is commutative), and collect powers:
The constant 1 has value 1. \square
Proof of Corollary 5. x - a is monic, so Theorem 3 gives unique q, r with f = (x - a)q + r and r = 0 or \deg r < 1: r is a constant c. Apply \psi_a (Theorem 4): f(a) = (a - a)q(a) + c = c. If f(a) = 0, then f = (x - a)q; conversely f = (x - a)q gives f(a) = 0 \cdot q(a) = 0. \square
Proof of Theorem 6. Induction on k; for k = 0 the empty product is 1. Suppose f = (x - a_1)\cdots(x - a_{k - 1})h. Applying \psi_{a_k} (Theorem 4),
Each a_k - a_i is nonzero and D has no zero divisors, so h(a_k) = 0, and h = (x - a_k)h_1 by Corollary 5. This proves the divisibility. Now write f = Ph with P the product of the k factors, monic of degree k. As f \ne 0, h \ne 0, and Theorem 2(b) gives n = k + \deg h \ge k. \square
Proof of Corollary 7. Every element of D is a root of f - g. If f - g \ne 0, Theorem 6 bounds its roots by \deg(f - g), but D is infinite. \square
Proof of Theorem 8. If I = \{0\}, then I = \langle 0 \rangle. Otherwise degrees are nonnegative integers, so I has a nonzero element g_0 of least degree. With u its leading coefficient, g = u^{-1}g_0 lies in I, which absorbs multiplication, and is monic of the same degree. So \langle g \rangle \subseteq I (Ideals and quotient rings, Theorem 4). For f \in I, Theorem 3 gives f = qg + r; then r = f - qg \in I, and \deg r < \deg g is ruled out by the choice of g, so r = 0. Hence I = \langle g \rangle, and f \in I exactly when g \mid f. A monic generator g' of I divides g, so has least degree too (Theorem 2(b)); then g - g' \in I has its leading terms cancel, so it is 0 or of smaller degree, and it is 0. \square
Proof of Corollary 9. Theorem 3 gives f = qg + r, and f - r = qg \in I, so f + I = r + I. If r + I = r' + I with r, r' each 0 or of degree below n, then g \mid r - r'; a nonzero multiple hg has degree \deg h + n \ge n (Theorem 2(b)), so r = r'. So cosets match the choices of n coefficients c_0, \dots, c_{n - 1} \in F. \square
Worked examples
Arithmetic in \mathbb{Z}_4[x]
In \mathbb{Z}_4[x], writing k for [k], let f = 2x^2 + x + 3 and g = 2x + 1. Compute f + g, fg and g^2, and compare with Theorem 2.
SolutionCoefficients add in \mathbb{Z}_4, so f + g = 2x^2 + 3x + 4 = 2x^2 + 3x. For the product, collect c_k by the rule of the Definition:
since 4 = 0 and 7 = 3 in \mathbb{Z}_4. So \deg(fg) = 1, not 3, as the leading coefficients multiply to 2 \cdot 2 = 0. Also g^2 = 4x^2 + 4x + 1 = 1: g is a unit of degree 1. Over an integral domain neither can happen (Theorem 2).
Division in \mathbb{Q}[x]
Divide f = x^4 + 3x^3 - x + 2 by g = 2x^2 + 1 in \mathbb{Q}[x].
SolutionEach step of Theorem 3 cancels the top term with a multiple of g, using \displaystyle 2^{-1} = \frac12. Subtracting \displaystyle \frac12 x^2 g = x^4 + \frac12 x^2 leaves \displaystyle 3x^3 - \frac12 x^2 - x + 2. Subtracting \displaystyle \frac32 x g = 3x^3 + \frac32 x leaves \displaystyle -\frac12 x^2 - \frac52 x + 2. Subtracting \displaystyle -\frac14 g = -\frac12 x^2 - \frac14 leaves \displaystyle -\frac52 x + \frac94, of degree 1 < 2. So
Check: \displaystyle gq = x^4 + 3x^3 + \frac32 x - \frac14, and adding r gives f. The fractions come from dividing by 2 (see Boundaries).
Division in \mathbb{Z}_5[x]
Divide f = 3x^4 + x^3 + 2x + 4 by g = 2x^2 + 3x + 1 in \mathbb{Z}_5[x].
SolutionThe leading coefficient of g is 2, whose inverse in \mathbb{Z}_5 is 3 (Modular inverses and linear congruences). To cancel 3x^4 use 3 \cdot 3 x^2 = 4x^2: 4x^2 g = 8x^4 + 12x^3 + 4x^2 = 3x^4 + 2x^3 + 4x^2, and
To cancel 4x^3 use 4 \cdot 3x = 2x: 2xg = 4x^3 + 6x^2 + 2x = 4x^3 + x^2 + 2x, and subtracting leaves 4. So q = 4x^2 + 2x and r = 4. Check at 1 (Theorem 4): f(1) = 0 and g(1)q(1) + 4 = 1 + 4 = 0.
A polynomial that vanishes everywhere
Show that in \mathbb{Z}_5[x]
and conclude that x^5 and x are different polynomials with the same values on \mathbb{Z}_5.
SolutionBy Fermat's little theorem, a^5 = a for every a \in \mathbb{Z}_5, so 0, 1, 2, 3, 4 are five distinct roots of x^5 - x. \mathbb{Z}_5 is a field, hence an integral domain, so by Theorem 6 x^5 - x = Ph with P the product on the right. P is monic of degree 5, so Theorem 2(b) makes h a constant, and comparing leading coefficients gives h = 1. So x^5 \ne x as polynomials, yet a^5 = a for all a; Corollary 7 needs D infinite.
Too many roots
Find the roots of x^2 - 1 in \mathbb{Z}_7 and in \mathbb{Z}_8, and explain the difference.
SolutionThe squares of 0, 1, \dots, 6 in \mathbb{Z}_7 are 0, 1, 4, 2, 2, 4, 1, so the roots are 1 and 6: two, as Theorem 6 allows. In \mathbb{Z}_8 the squares of 0, 1, \dots, 7 are 0, 1, 4, 1, 0, 1, 4, 1, so 1, 3, 5, 7 are four roots of a polynomial of degree 2.
The proof of Theorem 6 fails at the step that uses “no zero divisors”. Here x^2 - 1 = (x - 1)(x - 7), and at the root 3 the factors give (3 - 1)(3 - 7) = 2 \cdot 4 = 0 with neither factor 0. Also (x - 3)(x - 5) = x^2 - 8x + 15 = x^2 - 1: the factorization is not unique.
One generator for two
Let I = \langle x^4 - 1, x^6 - 1 \rangle in \mathbb{Q}[x]. Prove that I = \langle x^2 - 1 \rangle.
SolutionProof. Division plays the part it plays in the The Euclidean algorithm and coprime numbers: x^6 - 1 = x^2(x^4 - 1) + (x^2 - 1). So x^2 - 1 = (x^6 - 1) - x^2(x^4 - 1) lies in I, which is closed under subtraction and absorbs multiplication, and \langle x^2 - 1 \rangle \subseteq I. Conversely x^4 - 1 = (x^2 + 1)(x^2 - 1) and x^6 - 1 = (x^4 + x^2 + 1)(x^2 - 1), so both generators lie in the ideal \langle x^2 - 1 \rangle, and I \subseteq \langle x^2 - 1 \rangle. \square By Theorem 6 and Corollary 5, f \in I exactly when 1 and -1 are both roots of f.
A check on a submersible’s cable
Mei’s submersible sends 4-bit readings up its cable, and Samir, on the ship, wants to detect errors. A reading b_3b_2b_1b_0 is read as m = b_3x^3 + b_2x^2 + b_1x + b_0 \in \mathbb{Z}_2[x], and they fix g = x^3 + x + 1. Mei sends the 7 coefficients of c = x^3m + r, where r is the remainder of x^3m on division by g; Samir divides what arrives by g. Encode the reading 1101, and show that every error in one or two bits is detected.
Solutiong is monic, so Theorem 3 applies, and in \mathbb{Z}_2, -1 = 1. Work with cosets of I = \langle g \rangle (Corollary 9): x^3 + I = x + 1 + I. Multiplying by x repeatedly and replacing x^3 each time, the remainders of x^0, x^1, \dots, x^7 are
For 1101, m = x^3 + x^2 + 1 and x^3 m = x^6 + x^5 + x^3, with remainder (x^2 + 1) + (x^2 + x + 1) + (x + 1) = 1. So c = x^6 + x^5 + x^3 + 1, and Mei sends 1101001. In general, if x^3 m = qg + r, then c = qg + 2r = qg: every word sent is a multiple of g.
If bit k flips, Samir receives c + x^k, whose remainder is that of x^k, never 0. If bits j \ne k flip, the remainder is the sum of those of x^j and x^k, not 0 since the first seven entries of the list are distinct. Three flips can go unseen: 0001011 is g itself.
Boundaries
- Division needs a unit leading coefficient. In \mathbb{Z}[x] no q and constant r give x = q(2x + 1) + r: if \deg q \ge 1 the right side has degree at least 2, and if q = c, then 2c = 1. The ideal \langle 2, x \rangle of \mathbb{Z}[x] is not principal (Ideals and quotient rings, Boundaries), so Theorem 8 fails too. Uniqueness can also fail (Exercise 16).
- Roots need a commutative domain. Theorem 6 fails in \mathbb{Z}_8 (Example 5), and in Hamilton’s quaternions, where x^2 + 1 has infinitely many roots, \pm i, \pm j, \pm k among them.
- Polynomials are not functions over a finite ring (Example 4); Corollary 7 needs D infinite.
Where this goes next
Theorem 3 makes F[x] a Euclidean domain (Euclidean domains and principal ideal domains), where the monic generator of \langle f, g \rangle is the greatest common divisor. Prime and maximal ideals shows F[x]/\langle g \rangle is a field exactly when g is not a product of polynomials of lower degree, which Irreducible polynomials and Eisenstein's criterion decide; over \mathbb{Z}_p the count p^n gives the Finite fields, and evaluation outside F begins Field extensions and degree.
Exercises
Arithmetic and units
- In \mathbb{Z}_6[x] compute (3x^2 + 2x + 1)(2x + 3). What is its degree, and why is it not 3?
- Show that 2 + 3x is a unit of \mathbb{Z}_9[x] and find its inverse.
- List the units of \mathbb{Z}[x], of \mathbb{Q}[x] and of \mathbb{Z}_7[x].
Division
- Divide 4x^3 - x + 2 by 3x^2 + 2 in \mathbb{Q}[x].
- Divide x^4 + 5x^2 + 3x + 1 by 3x^2 + x + 6 in \mathbb{Z}_7[x].
- Divide x^5 + 2x^2 + 1 by x^2 + 1 in \mathbb{Z}_3[x].
- Without dividing, find the remainders of x^{100} + x^3 + 1 on division by x - 2 and by x - 3 in \mathbb{Z}_5[x].
Roots
- Write x^4 + 4 as a product of monic linear factors in \mathbb{Z}_5[x].
- Find every root of x^2 + x in \mathbb{Z}_6, and two different factorizations of it into monic linear factors.
- Find a polynomial f \in \mathbb{Z}_5[x] of degree at most 2 with f(0) = 1, f(1) = 3 and f(2) = 2, and show there is only one.
Ideals, quotients and checks
- Find the monic generator g of \langle x^3 + 1, x^2 - x - 2 \rangle in \mathbb{Q}[x], and write g = a(x)(x^3 + 1) + b(x)(x^2 - x - 2).
- Let I = \langle x^2 + 1 \rangle in \mathbb{Z}_3[x]. How many elements does \mathbb{Z}_3[x]/I have? Compute (1 + x + I)^2 and (1 + x + I)^4.
- With Mei and Samir’s scheme, Samir receives 1001101. Can it be a word Mei sent?
Proofs
- Prove that D[x] is not a field for any integral domain D.
- Let R be commutative and a \in R with a^n = 0 for some n \ge 1. Prove that 1 + ax is a unit of R[x].
- Using Exercise 2, show that in \mathbb{Z}_9[x] the equation x = q(3x + 2) + r has a solution with r constant for each of the nine choices of r. Why does this not contradict Theorem 3?
- Prove that the kernel of \displaystyle \psi_{\sqrt{2}} : \mathbb{Q}[x] \to \mathbb{R} is \langle x^2 - 2 \rangle and that its image is \displaystyle \{a + b\sqrt{2} : a, b \in \mathbb{Q}\}.
- Let p be prime. Prove that x^{p - 1} - 1 = (x - 1)(x - 2)\cdots(x - (p - 1)) in \mathbb{Z}_p[x], and deduce Wilson’s theorem, (p - 1)! \equiv -1 \pmod{p}.
Answers
- x^2 + 2x + 3, of degree 2: the coefficients of x^3, x^2, x are 6 = 0, 13 = 1 and 8 = 2. \mathbb{Z}_6 is not a domain and 2 is not a unit, so Theorem 2(b) does not apply.
- (2 + 3x)(5 + 6x) = 10 + 27x + 18x^2 = 1 in \mathbb{Z}_9[x], so the inverse is 5 + 6x.
- By Theorem 2(c): \pm 1 in \mathbb{Z}[x]; the nonzero rational constants in \mathbb{Q}[x]; the six nonzero constants 1, \dots, 6 in \mathbb{Z}_7[x].
- \displaystyle q = \frac43 x, \displaystyle r = -\frac{11}{3}x + 2: subtracting \displaystyle \frac43 x(3x^2 + 2) = 4x^3 + \frac83 x leaves \displaystyle -\frac{11}{3}x + 2.
- q = 5x^2 + 3x, r = 6x + 1. With 3^{-1} = 5, subtracting 5x^2 g leaves 2x^3 + 3x^2 + 3x + 1, and subtracting 3xg leaves 6x + 1.
- q = x^3 + 2x + 2, r = x + 2. Subtracting x^3(x^2 + 1), 2x(x^2 + 1) and 2(x^2 + 1) in turn leaves 2x^3 + 2x^2 + 1, then 2x^2 + x + 1, then x + 2.
- By Corollary 5 the remainders are the values. 2^4 = 1, so 2^{100} = 1 and 1 + 8 + 1 = 10 = 0: remainder 0. 3^4 = 1, so 1 + 27 + 1 = 29 = 4: remainder 4.
- (x - 1)(x - 2)(x - 3)(x - 4). For a \ne 0, a^4 = 1 by Fermat, so a^4 + 4 = 0; the four roots give the factor by Theorem 6, and both sides are monic of degree 4.
- The values of a^2 + a for a = 0, \dots, 5 are 0, 2, 0, 0, 2, 0: roots 0, 2, 3, 5. Then x^2 + x = x(x - 5) = (x - 2)(x - 3), as (x - 2)(x - 3) = x^2 - 5x + 6.
- f = x^2 + x + 1. With f = ax^2 + bx + 1: a + b = 2 and 4a + 2b = 1, so 2a + b = 3 (multiply by 2^{-1} = 3), giving a = 1, b = 1. If g is another, f - g has degree at most 2 and three roots 0, 1, 2, so f - g = 0 by Theorem 6.
- g = x + 1, with \displaystyle a = \frac13 and \displaystyle b = -\frac13(x + 1), from x^3 + 1 = (x + 1)(x^2 - x - 2) + (3x + 3); and x + 1 divides both generators.
- 3^2 = 9 elements (Corollary 9). (1 + x)^2 = x^2 + 2x + 1 \equiv 2x, as x^2 \equiv -1; then (2x)^2 = 4x^2 \equiv -4 = 2. So (1 + x + I)^2 = 2x + I and (1 + x + I)^4 = 2 + I.
- No. x^6 + x^3 + x^2 + 1 has remainder (x^2 + 1) + (x + 1) + x^2 + 1 = x + 1, which is not 0, and every word sent is a multiple of g.
- Proof. By Theorem 2(c) the units of D[x] are constants, and x is a nonzero nonconstant, so it has no inverse. \square
- Proof. Let v = \sum_{k = 0}^{n - 1} (-a)^k x^k. Multiplying out, the sum telescopes: (1 + ax)v = 1 - (-ax)^n = 1 - (-1)^n a^n x^n = 1, and R[x] is commutative. \square
- By Exercise 2, (3x + 2)(6x + 5) = 1. For any constant r, put q = (x - r)(6x + 5); then q(3x + 2) + r = (x - r) + r = x. So all nine r occur, and q, r are not unique. Theorem 3 assumes a unit leading coefficient, and 3 is not a unit of \mathbb{Z}_9.
- Proof. \displaystyle \psi_{\sqrt{2}} is a ring homomorphism (Theorem 4), so its kernel I is an ideal, and x^2 - 2 \in I. By Theorem 8, I = \langle g \rangle with g monic of least degree. No nonzero constant lies in I, and no x - c with c \in \mathbb{Q}, since \displaystyle \sqrt{2} is irrational; so \deg g = 2, and g = x^2 - 2 by uniqueness. By Corollary 9 every f has the value of its remainder a + bx, which is \displaystyle a + b\sqrt{2}; and every \displaystyle a + b\sqrt{2} is the value of a + bx. \square
- Proof. By Fermat's little theorem, a^{p - 1} = 1 for a = 1, \dots, p - 1, so these are p - 1 distinct roots of x^{p - 1} - 1 in the field \mathbb{Z}_p. Theorem 6 gives x^{p - 1} - 1 = Ph with P the product, and both are monic of degree p - 1, so h = 1. Constant terms give -1 = (-1)^{p - 1}(p - 1)!, and (-1)^{p - 1} = 1 in \mathbb{Z}_p (for p = 2 since -1 = 1). \square