Division Algorithm for Polynomials

In today's blog, I will go over a result that I use in the proof for the Fundamental Theorem of Algebra.

Today's proof is taken from Joseph A. Gallian's Contemporary Abstract Algebra.

Theorem: Division Algorithm for Polynomials

Let F be a field, f(x), g(x) ∈ F[x] with g(x) ≠ 0.

Then there exists unique polynomials q(x), r(x) in F[x] such that f(x) = g(x)q(x) + r(x) and r(x)=0 or deg r(x) is less than deg g(x).

Proof:

(1) Let f(x) = g(x)q(x) + r(x) with g(x) ≠ 0

(2) If f(x) = 0 or deg f(x) is less than g(x), then q(x)=0, r(x)=f(x)

(3) So, we can assume that f(x) ≠ 0 and deg f(x) ≥ deg g(x)

(4) Let f(x) = a_nxⁿ + ... + a₀

(5) Let g(x) = b_mx^m + ... + b₀

(6) Let f₁(x) = f(x) - a_nb_m^-1x^n-mg(x)

(7) We note that deg f₁(x) is less than deg f(x) since:

f(x) - a_nb_m^-1x^n-mg(x) =

= a_nxⁿ + ... + a₀ - a_nb_m^-1x^n-m(b_mx^m + ... + b₀) =

= a_nⁿ - a_nxⁿ + a_n-1x^n-1 + ... + a₀ - a_nb_m^-1b_m-1x^n-1 - ... - a_nb_m^-1b₀x^n-m =

= a_n-1x^n-1 + ... + a₀ - a_nb_m^-1b_m-1x^n-1 - ... - a_nb_m^-1b₀x^n-m

So that f₁(x) has a degree of n-1 while f(x) has a degree of n.

(8) Now, we are ready to prove this theorem by induction.

(9) The assumption is true for deg f(x) = 0

deg f(x) is 0 → f(x)=C where C is a constant.

If deg g(x) is 0, then g(x) = D where D is a nonzero constant and q(x) = C/D and r(x)=0.

If deg g(x) is greater than 0, then q(x)=0 and r(x)=C.

(10) We can now assume that the assumption holds for all polynomials up to degree n-1.

(9) We see that:

f(x) = a_nb_m^-1x^n-mg(x) + f₁(x)

where the degree of f₁(x) is n-1 [See step #7]

(10) But by the induction hypothesis (step #10), we can assume that there exists q₁(x) and r₁(x) where r₁(x) has a degree lower than g(x).

(11) Therefore, we have:

a_nb_m^-1x^n-mg(x) + f₁(x) = a_nb_m^-1x^n-mg(x) + q₁(x)g(x) + r₁(x) =

= [a_nb_m^-1x^n-m + q₁(x)]g(x) + r₁(x)

(12) Which proves that degree r(x) is less than degree g(x) by principle of induction.

(13) Now, we still need to prove uniqueness of q(x),r(x)

(14) Suppose that:

f(x) = g(x)q(x) + r(x) = g(x)q'(x) + r'(x) where r(x),r'(x)=0 or deg r(x),r'(x) is less than deg g(x)

(15) Now, if we substract both equations, we get:

0 = g(x)[q(x) - q'(x)] + [r(x) - r'(x)]

which is the same as:

r'(x) - r(x) = g(x)[q(x) - q'(x)]

(16) Now since r'(x) and r(x) have degree less than g(x), the only way that this can be true is if r'(x) - r(x) = 0

(17) But then r'(x) = r(x) and q(x) = q'(x)

QED

References

• Joseph A. Gallian, Contemporary Abstract Algebra.