Abstract Algebra: Theory and Applications

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

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

the polynomial

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

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

Then

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

and

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

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

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

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,

But

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

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 \(d(x)\) be the monic polynomial of smallest degree in the set

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,

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,

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

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