Thursday, January 29, 2009

Alternate Form of the Division Algorithm for Polynomials

Theorem: Alternative Form of the Division Algorithm for Polynomials

Let F be a field

Let f(x),g(x) be polynomials of F[x] where 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) be two polynomials such that g(x) ≠ 0

(2) We can assume that deg f(x) ≥ deg g(x) since:

if deg f(x) = 0, then f(x) = g(x)(0) - 0.

if deg f(x) is less than deg g(x), then f(x) = g(x)(0) - [-f(x)]

(3) Let:

f(x) = anxn + ... + a0

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

where an and bm are nonzero.

[We can make this assumption since g(x) ≠ 0 and deg f(x) ≥ deg g(x).]

(4) I will use induction to establish the existence of q(x), r(x).

(5) q(x),r(x) exist if deg f(x) = 0 since:

(a) Assume deg f(x) = 0

(b) Then there exists C such that f(x)=C

(c) Since deg f(x) ≥ deg g(x), it follows that deg g(x)= 0 and there exists D such that g(x)=D

(d) Let q(x) = C/D

(e) Then it follows that f(x) = g(x)*q(x) - 0

(6) Assume that our assumption holds true up to deg f(x) = n-1

(7) Let:

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

(8) So, deg f1(x) is less than deg f(x)

(9) By the induction hypothesis, there exists q1(x) and r1(x) such that:

f1(x) = q1(x)g(x) - r1(x)

where deg r1 is less than deg g(x) or deg r1(x) = 0

(10) So, then:

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

= [anbm-1xn-m + q1(x)]g(x) - r1(x)

where deg r1 is less than deg g(x) or deg r1(x) = 0

(11) This proves the first part of the theorem. To complete it, we need to prove uniqueness.

(12) Assume that:

f(x) = g(x)q(x) - r(x) = g(x)q'(x) - r'(x)

where deg r(x), deg r'(x) = 0 or is less then deg g(x)

(13) So that:

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

(14) Then:

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

(15) Assume that q(x) - q'(x) is nonzero.

(16) Then, deg g(x)[q(x)-q'(x)] = deg g(x) + deg (q(x) - q'(x)) [See Lemma 2, here]

(17) And, deg(r(x) - r'(x)) ≤ max(deg r(x),deg r'(x)) [See Lemma 1, here]

(18) But this is impossible since deg(r(x)) is less than deg g(x)

(19) So, we have a contradiction and we reject our assumption in step #15.

(20) So, if q(x) - q'(x) is 0, then it follows that r(x) - r'(x) is also 0.

(21) Then q(x) = q'(x) and r(x) = r'(x)

QED

Reference

No comments :