Skip to main content

Section 6.3 The Division Algorithm

Recall that the division algorithm for integers (Theorem 6.1) says that if \(a\) and \(b\) are integers with \(b \gt 0\text{,}\) then there exist unique integers \(q\) and \(r\) such that \(a = bq + r\text{,}\) where \(0 \leq r \lt b\text{.}\) The algorithm by which \(q\) and \(r\) are found is just long division. A similar theorem exists for polynomials. The division algorithm for polynomials has several important consequences. Since its proof is very similar to the corresponding proof for integers, it is worthwhile to review Theorem 6.1 at this point.

Proof.

We will first consider the existence of \(q(x)\) and \(r(x)\text{.}\) If \(f(x)\) is the zero polynomial, then

\begin{equation*} 0 = 0 \cdot g(x) + 0; \end{equation*}

hence, both \(q\) and \(r\) must also be the zero polynomial. Now suppose that \(f(x)\) is not the zero polynomial and that \(\deg f(x) = n\) and \(\deg g(x) = m\text{.}\) If \(m \gt n\text{,}\) then we can let \(q(x) = 0\) and \(r(x) = f(x)\text{.}\) Hence, we may assume that \(m \leq n\) and proceed by induction on \(n\text{.}\) If

\begin{align*} f(x) & = a_n x^n + a_{n-1} x^{n - 1} + \cdots + a_1 x + a_0\\ g(x) & = b_m x^m + b_{m-1} x^{m - 1} + \cdots + b_1 x + b_0 \end{align*}

the polynomial

\begin{equation*} f'(x) = f(x) - \frac{a_n}{b_m} x^{n - m} g(x) \end{equation*}

has degree less than \(n\) or is the zero polynomial. By induction, there exist polynomials \(q'(x)\) and \(r(x)\) such that

\begin{equation*} f'(x) = q'(x) g(x) + r(x)\text{,} \end{equation*}

where \(r(x) = 0\) or the degree of \(r(x)\) is less than the degree of \(g(x)\text{.}\) Now let

\begin{equation*} q(x) = q'(x) + \frac{a_n}{b_m} x^{n - m}\text{.} \end{equation*}

Then

\begin{equation*} f(x) = g(x) q(x) + r(x)\text{,} \end{equation*}

with \(r(x)\) the zero polynomial or \(\deg r(x) \lt \deg g(x)\text{.}\)

To show that \(q(x)\) and \(r(x)\) are unique, suppose that there exist two other polynomials \(q_1(x)\) and \(r_1(x)\) such that \(f(x) = g(x) q_1(x) + r_1(x)\) with \(\deg r_1(x) \lt \deg g(x)\) or \(r_1(x) = 0\text{,}\) so that

\begin{equation*} f(x) = g(x) q(x) + r(x) = g(x) q_1(x) + r_1(x)\text{,} \end{equation*}

and

\begin{equation*} g(x) [q(x) - q_1(x) ] = r_1(x) - r(x)\text{.} \end{equation*}

If \(q(x) - q_1(x)\) is not the zero polynomial, then

\begin{equation*} \deg( g(x) [q(x) - q_1(x) ] )= \deg( r_1(x) - r(x) ) \geq \deg g(x)\text{.} \end{equation*}

However, the degrees of both \(r(x)\) and \(r_1(x)\) are strictly less than the degree of \(g(x)\text{;}\) therefore, \(r(x) = r_1(x)\) and \(q(x) = q_1(x)\text{.}\)

Example 6.14.

The division algorithm merely formalizes long division of polynomials, a task we have been familiar with since high school. For example, suppose that we divide \(x^3 - x^2 + 2 x - 3\) by \(x - 2\text{.}\)

\(x^2\) \(+\) \(x\) \(+\) \(4\)
\(x\) \(-\) \(2\) \(x^3\) \(-\) \(x^2\) \(+\) \(2x\) \(-\) \(3\)
\(x^3\) \(-\) \(2x^2\)
\(x^2\) \(+\) \(2x\) \(-\) \(3\)
\(x^2\) \(-\) \(2x\)
\(4x\) \(-\) \(3\)
\(4x\) \(-\) \(8\)
\(5\)

Hence, \(x^3 - x^2 + 2 x - 3 = (x - 2) (x^2 + x + 4 ) + 5\text{.}\)

Let \(p(x)\) be a polynomial in \(F[x]\) and \(\alpha \in F\text{.}\) We say that \(\alpha\) is a zero or root of \(p(x)\) if \(p(x)\) is in the kernel of the evaluation homomorphism \(\phi_{\alpha}\text{.}\) All we are really saying here is that \(\alpha\) is a zero of \(p(x)\) if \(p(\alpha) = 0\text{.}\)

Proof.

Suppose that \(\alpha \in F\) and \(p( \alpha ) = 0\text{.}\) By the division algorithm, there exist polynomials \(q(x)\) and \(r(x)\) such that

\begin{equation*} p(x) = (x -\alpha) q(x) + r(x) \end{equation*}

and the degree of \(r(x)\) must be less than the degree of \(x -\alpha\text{.}\) Since the degree of \(r(x)\) is less than 1, \(r(x) = a\) for \(a \in F\text{;}\) therefore,

\begin{equation*} p(x) = (x -\alpha) q(x) + a\text{.} \end{equation*}

But

\begin{equation*} 0 = p(\alpha) = 0 \cdot q(\alpha) + a = a; \end{equation*}

consequently, \(p(x) = (x - \alpha) q(x)\text{,}\) and \(x - \alpha\) is a factor of \(p(x)\text{.}\)

Conversely, suppose that \(x - \alpha\) is a factor of \(p(x)\text{;}\) say \(p(x) = (x - \alpha) q(x)\text{.}\) Then \(p( \alpha ) = 0 \cdot q(\alpha) = 0\text{.}\)

Proof.

We will use induction on the degree of \(p(x)\text{.}\) If \(\deg p(x) = 0\text{,}\) then \(p(x)\) is a constant polynomial and has no zeros. Let \(\deg p(x) = 1\text{.}\) Then \(p(x) = ax + b\) for some \(a\) and \(b\) in \(F\text{.}\) If \(\alpha_1\) and \(\alpha_2\) are zeros of \(p(x)\text{,}\) then \(a\alpha_1 + b = a\alpha_2 +b\) or \(\alpha_1 = \alpha_2\text{.}\)

Now assume that \(\deg p(x) \gt 1\text{.}\) If \(p(x)\) does not have a zero in \(F\text{,}\) then we are done. On the other hand, if \(\alpha\) is a zero of \(p(x)\text{,}\) then \(p(x) = (x - \alpha ) q(x)\) for some \(q(x) \in F[x]\) by Corollary 6.15. The degree of \(q(x)\) is \(n-1\) by Proposition 6.11. Let \(\beta\) be some other zero of \(p(x)\) that is distinct from \(\alpha\text{.}\) Then \(p(\beta) = (\beta - \alpha) q(\beta) = 0\text{.}\) Since \(\alpha \neq \beta\) and \(F\) is a field, \(q(\beta ) = 0\text{.}\) By our induction hypothesis, \(q(x)\) can have at most \(n - 1\) zeros in \(F\) that are distinct from \(\alpha\text{.}\) Therefore, \(p(x)\) has at most \(n\) distinct zeros in \(F\text{.}\)

Let \(F\) be a field. A monic polynomial \(d(x)\) is a greatest common divisor of polynomials \(p(x), q(x) \in F[x]\) if \(d(x)\) evenly divides both \(p(x)\) and \(q(x)\text{;}\) and, if for any other polynomial \(d'(x)\) dividing both \(p(x)\) and \(q(x)\text{,}\) \(d'(x) \mid d(x)\text{.}\) We write \(d(x) = \gcd( p(x), q( x))\text{.}\) Two polynomials \(p(x)\) and \(q(x)\) are relatively prime if \(\gcd(p(x), q(x) ) = 1\text{.}\)

Proof.

Let \(d(x)\) be the monic polynomial of smallest degree in the set

\begin{equation*} S = \{ f(x) p(x) + g(x) q(x) : f(x), g(x) \in F[x] \}\text{.} \end{equation*}

We can write \(d(x) = r(x) p(x) + s(x) q(x)\) for two polynomials \(r(x)\) and \(s(x)\) in \(F[x]\text{.}\) We need to show that \(d(x)\) divides both \(p(x)\) and \(q(x)\text{.}\) We shall first show that \(d(x)\) divides \(p(x)\text{.}\) By the division algorithm, there exist polynomials \(a(x)\) and \(b(x)\) such that \(p(x) = a(x) d(x) + b(x)\text{,}\) where \(b(x)\) is either the zero polynomial or \(\deg b(x) \lt \deg d(x)\text{.}\) Therefore,

\begin{align*} b(x) & = p(x) - a(x) d(x)\\ & = p(x) - a(x)( r(x) p(x) + s(x) q(x))\\ & = p(x) - a(x) r(x) p(x) - a(x) s(x) q(x)\\ & = p(x)( 1 - a(x) r(x) ) + q(x) ( - a(x) s(x) ) \end{align*}

is a linear combination of \(p(x)\) and \(q(x)\) and therefore must be in \(S\text{.}\) However, \(b(x)\) must be the zero polynomial since \(d(x)\) was chosen to be of smallest degree; consequently, \(d(x)\) divides \(p(x)\text{.}\) A symmetric argument shows that \(d(x)\) must also divide \(q(x)\text{;}\) hence, \(d(x)\) is a common divisor of \(p(x)\) and \(q(x)\text{.}\)

To show that \(d(x)\) is a greatest common divisor of \(p(x)\) and \(q(x)\text{,}\) suppose that \(d'(x)\) is another common divisor of \(p(x)\) and \(q(x)\text{.}\) We will show that \(d'(x) \mid d(x)\text{.}\) Since \(d'(x)\) is a common divisor of \(p(x)\) and \(q(x)\text{,}\) there exist polynomials \(u(x)\) and \(v(x)\) such that \(p(x) = u(x) d'(x)\) and \(q(x) = v(x) d'(x)\text{.}\) Therefore,

\begin{align*} d(x) & = r(x) p(x) + s(x) q(x)\\ & = r(x) u(x) d'(x) + s(x) v(x) d'(x)\\ & = d'(x) [r(x) u(x) + s(x) v(x)]\text{.} \end{align*}

Since \(d'(x) \mid d(x)\text{,}\) \(d(x)\) is a greatest common divisor of \(p(x)\) and \(q(x)\text{.}\)

Finally, we must show that the greatest common divisor of \(p(x)\) and \(q(x)\) is unique. Suppose that \(d'(x)\) is another greatest common divisor of \(p(x)\) and \(q(x)\text{.}\) We have just shown that there exist polynomials \(u(x)\) and \(v(x)\) in \(F[x]\) such that \(d(x) = d'(x)[r(x) u(x) + s(x) v(x)]\text{.}\) Since

\begin{equation*} \deg d(x) = \deg d'(x) + \deg[r(x) u(x) + s(x) v(x)] \end{equation*}

and \(d(x)\) and \(d'(x)\) are both greatest common divisors, \(\deg d(x) = \deg d'(x)\text{.}\) Since \(d(x)\) and \(d'(x)\) are both monic polynomials of the same degree, it must be the case that \(d(x) = d'(x)\text{.}\)

Notice the similarity between the proof of Proposition 6.17 and the proof of Theorem 6.2.

Reading Questions Reading Questions

1.

What must be true of \(r(x)\) in the division algorithm for polynomials? How does this relate to \(r\) in the division algorithm for the integers?

2.

What can you say about the number \(\alpha\) and the polynomial \(p(x)\) if \(p(x)\) is in the kernel of the evaluation homomorphism \(\phi_\alpha\text{?}\)

3.

What do we mean by the greatest common divisor of a pair of polynomials \(p(x)\) and \(q(x)\text{?}\)

4.

After reading the section, what questions do you still have? Write at least one well formulated question (even if you think you understand everything).

Exercises Practice Problems

1.

In \(\Z_7[x]\text{,}\) find the quotient and remainder as in the division algorithm for \(a(x) = 5x^3 + 6x^2 - 3x + 4\) and \(b(x) = x-2\text{.}\) Then verify that \(r(x)\) is \(a(2)\text{.}\)

2.

In \(\Z_5[x]\text{,}\) find the quotient and remainder as in the division algorithm for \(a(x) = 4x^5 - x^3 +x^2 + 4\) and \(b(x) = x^3-2\text{.}\)

3.

Suppose the ideal \(J\) of \(\Z\) is the smallest ideal that contains both 231 and 429. Find a single element \(p \in \Z\) such that \(J = \langle p \rangle\text{.}\)

4.

Suppose the ideal \(J\) of \(\Q[x]\) is the smallest ideal that contains both \(x^2 - 2x - 3\) and \(x^3 - 5x^2 + 6x\text{.}\) Find a single element \(p \in \Q[x]\) such that \(J = \langle p \rangle\text{.}\)

Hint

Factor the polynomials

5.

Suppose the ideal \(J\) of \(\Z_5[x]\) is the smallest ideal that contains both \(2x^7 + 4\) and \(x^7 + 1\text{.}\) Find a single element \(p \in \Z_5[x]\) such that \(J = \langle p \rangle\text{.}\)

6.

Let \(J\) be an ideal that contains polynomials \(a(x)\) and \(b(x)\) in \(F[x]\) for some field \(F\text{.}\) If \(r(x)\) is the remainder when \(a(x)\) is divided by \(b(x)\text{,}\) prove that \(r(x)\) is also in the ideal \(J\text{.}\)

7.

In the previous problem you proved that if \(a(x), b(x) \in J\) and \(a(x) = q(x)b(x) + r(x)\text{,}\) then \(r(x) \in J\text{.}\) If you then apply the division algorithm again, to \(b(x)\) and \(r(x)\text{,}\) to find \(b(x) = q'(x)r(x) + r'(x)\text{,}\) you would have that \(r'(x) \in J\) as well.

What would happen if you kept doing this? Would it go on forever? If it stops, how would it? And what does this have to do with the GCD?

8.

Does \(3x^3 - 4x^2 - x + 4\text{,}\) as a polynomial in \(\Z_5[x]\) have any roots? What does this tell you about whether the polynomial can factor in \(\Z_5[x]\text{?}\)

9.

Find two different factorizations of \(x^2 + x + 8\) in \(\Z_{10}[x]\)

Hint

One factorization is \((x+2)(x+9)\text{.}\) Are there other ways to multiply to \(8\) in \(\Z_{10}\text{?}\)

Exercises Collected Homework

1.

Let \(F\) be a field and \(p(x)\) be a polynomial in \(F[x]\text{.}\) Let \(a \in F\) be some element in \(F\text{.}\) What will the remainder be when you divide \(p(x)\) by \(x-a\text{?}\) We saw in class that if \(a\) is a root of \(p(x)\text{,}\) then the remainder will be zero. But what if \(a\) is not a root?

  1. Try a few examples and conjecture a formula for the remainder. Then use the division algorithm to prove your conjecture.

  2. Restate the result you proved in the language of ideals. In other words, which coset of the ideal \(\langle x-a\rangle\) will the remainder belong to?

2.

Let \(F\) be a field, \(a \in F\) and \(p(x) \in F[x]\text{.}\)

  1. Prove that when \(p(x)\) is divided by \(x-a\text{,}\) the remainder is the constant \(p(a)\text{.}\)

  2. Prove that for any polynomial \(b(x) \in F[x]\text{,}\) the polynomial \(p(x)\) and the remainder when \(p(x)\) is divided by \(b(x)\) are in the same coset of \(F[x]/\langle b(x)\rangle\text{.}\)