Saturday, May 20, 2006

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) = anxn + ... + a0

(5) Let g(x) = bmxm + ... + b0

(6) Let f1(x) = f(x) - anbm-1xn-mg(x)

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

f(x) - anbm-1xn-mg(x) =

= anxn + ... + a0 - anbm-1xn-m(bmxm + ... + b0) =

= ann - anxn + an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m =

= an-1xn-1 + ... + a0 - anbm-1bm-1xn-1 - ... - anbm-1b0xn-m

So that f1(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) = anbm-1xn-mg(x) + f1(x)

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

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

(11) Therefore, we have:

anbm-1xn-mg(x) + f1(x) = anbm-1xn-mg(x) + q1(x)g(x) + r1(x) =

= [anbm-1xn-m + q1(x)]g(x) + r1(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

2 comments:

Mollier said...

Hi,

I do not understand why under point (6) we let
f_1(x)=f(x)-a_nb_m^-1x^n-mg(x).
And is there a reason to name it f_1, i mean with 1 as the index?

It looks like the first step in long division..

Thanks for posting this!

Nishanth said...

YA ........... i also dont undestand ............ it would be nice if someone commented the answer :XD