17.2: The Division Algorithm

Recall that the division algorithm for integers (Theorem 2.9) 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 2.9 at this point.

Theorem \(17.6\). Division Algorithm

Let \(f(x)\) and \(g(x)\) be polynomials in \(F[x]\text{,}\) where \(F\) is a field and \(g(x)\) is a nonzero polynomial. Then there exist unique polynomials \(q(x), r(x) \in F[x]\) such that

\[ f(x) = g(x) q(x) + r(x)\text{,} \nonumber \]

where either \(\deg r(x) \lt \deg g(x)\) or \(r(x)\) is the zero polynomial.

Proof

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

\[ 0 = 0 \cdot g(x) + 0; \nonumber \]

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

\[ f'(x) = f(x) - \frac{a_n}{b_m} x^{n - m} g(x) \nonumber \]

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

\[ f'(x) = q'(x) g(x) + r(x)\text{,} \nonumber \]

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

\[ q(x) = q'(x) + \frac{a_n}{b_m} x^{n - m}\text{.} \nonumber \]

Then

\[ f(x) = g(x) q(x) + r(x)\text{,} \nonumber \]

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

\[ f(x) = g(x) q(x) + r(x) = g(x) q_1(x) + r_1(x)\text{,} \nonumber \]

and

\[ g(x) [q(x) - q_1(x) ] = r_1(x) - r(x)\text{.} \nonumber \]

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

\[ \deg( g(x) [q(x) - q_1(x) ] )= \deg( r_1(x) - r(x) ) \geq \deg g(x)\text{.} \nonumber \]

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 \(17.7\)

The division algorithm merely formalizes long division of polynomials, a task we have been familiar with since high school.

Solution

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{.}\)

Corollary \(17.8\)

Let \(F\) be a field. An element \(\alpha \in F\) is a zero of \(p(x) \in F[x]\) if and only if \(x - \alpha\) is a factor of \(p(x)\) in \(F[x]\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

\[ p(x) = (x -\alpha) q(x) + r(x) \nonumber \]

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,

\[ p(x) = (x -\alpha) q(x) + a\text{.} \nonumber \]

But

\[ 0 = p(\alpha) = 0 \cdot q(\alpha) + a = a; \nonumber \]

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{.}\)

 

Corollary \(17.9\)

Let \(F\) be a field. A nonzero polynomial \(p(x)\) of degree \(n\) in \(F[x]\) can have at most \(n\) distinct zeros in \(F\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 17.8. The degree of \(q(x)\) is \(n-1\) by Proposition 17.4. 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{.}\)

Proposition \(17.10\)

Let \(F\) be a field and suppose that \(d(x)\) is a greatest common divisor of two polynomials \(p(x)\) and \(q(x)\) in \(F[x]\text{.}\) Then there exist polynomials \(r(x)\) and \(s(x)\) such that

\[ d(x) = r(x) p(x) + s(x) q(x)\text{.} \nonumber \]

Furthermore, the greatest common divisor of two polynomials is unique.

Proof

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

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

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

\[ \deg d(x) = \deg d'(x) + \deg[r(x) u(x) + s(x) v(x)] \nonumber \]

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 \(17.10\) and the proof of Theorem \(2.10\).