Scribd
Upload
84 views2 pages

Division Algorithm Polynomials Proof

The Division Algorithm for Polynomials states that for polynomials f(x) and g(x) over a field F, there exist unique polynomials q(x) (quotient) and r(x) (remainder) such that f(x) = q(x)g(x) + r(x), where either r(x) = 0 or deg(r) < deg(g). The proof involves induction on the degree of f(x) to establish existence and demonstrates uniqueness by showing that if two pairs (q(x), r(x)) satisfy the equation, they must be equal. Thus, the theorem confirms the existence and uniqueness of the quotient and remainder in polynomial division.

Uploaded by

Basit Rasool
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
84 views2 pages

Division Algorithm Polynomials Proof

The Division Algorithm for Polynomials states that for polynomials f(x) and g(x) over a field F, there exist unique polynomials q(x) (quotient) and r(x) (remainder) such that f(x) = q(x)g(x) + r(x), where either r(x) = 0 or deg(r) < deg(g). The proof involves induction on the degree of f(x) to establish existence and demonstrates uniqueness by showing that if two pairs (q(x), r(x)) satisfy the equation, they must be equal. Thus, the theorem confirms the existence and uniqueness of the quotient and remainder in polynomial division.

Uploaded by

Basit Rasool
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Proof: Division Algorithm for Polynomials

Theorem (Division Algorithm for Polynomials):

Let f(x) and g(x) be polynomials over a field F, with g(x) 0. Then there exist unique polynomials q(x)

(quotient) and r(x) (remainder) in F[x] such that:

f(x) = q(x)g(x) + r(x)

where either r(x) = 0 or deg(r) < deg(g).

Proof (Existence and Uniqueness):

Part A: Existence

We use induction on the degree of f(x).

Let deg(f(x)) = n and deg(g(x)) = m.

Base Case: If deg(f) < deg(g), then we can take q(x) = 0 and r(x) = f(x). Clearly,

f(x) = 0 g(x) + f(x)

and deg(r) < deg(g), so the condition is satisfied.

Inductive Step: Assume the result is true for all polynomials of degree less than n. Suppose deg(f(x)) = n m =

deg(g(x)).

Let leading term of f(x) be a_n x^n, and leading term of g(x) be b_m x^m.

Since F is a field, b_m 0, so a_n / b_m exists in F.

Let s(x) = (a_n / b_m)x^{n - m}. Define:

f(x) = f(x) - s(x)g(x)

Then deg(f) < deg(f). By induction,

f(x) = q(x)g(x) + r(x), with deg(r) < deg(g)

So,

f(x) = s(x)g(x) + f(x) = (s(x) + q(x))g(x) + r(x)


Proof: Division Algorithm for Polynomials

Let q(x) = s(x) + q(x). Then,

f(x) = q(x)g(x) + r(x), with deg(r) < deg(g)

Hence, existence is proved.

Part B: Uniqueness

Suppose there are two pairs (q(x), r(x)) and (q(x), r(x)) such that:

f(x) = q(x)g(x) + r(x) = q(x)g(x) + r(x)

Subtracting, we get:

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

Let d(x) = q(x) - q(x) and s(x) = r(x) - r(x). Then,

d(x)g(x) = s(x)

But deg(s(x)) < deg(g(x)), and if d(x) 0, then deg(d(x)g(x)) deg(g(x)). So the only possibility is:

d(x) = 0 q(x) = q(x), and hence r(x) = r(x)

Therefore, the quotient and remainder are unique.

Conclusion:

There exist unique polynomials q(x) and r(x) such that:

f(x) = q(x)g(x) + r(x), with deg(r) < deg(g)

You might also like