How To Prove The Division Algorithm For Polynomials

How to Prove the Division Algorithm for Polynomials

This article provides a comprehensive guide on proving the division algorithm for polynomials. Understanding this algorithm is crucial for various algebraic manipulations and forms the basis for many advanced concepts in abstract algebra. We'll explore the theorem, its implications, and a step-by-step proof using polynomial long division.

What is the Division Algorithm for Polynomials?

The division algorithm for polynomials states that for any polynomials f(x) and g(x) (where g(x) is not the zero polynomial), there exist unique polynomials q(x) (the quotient) and r(x) (the remainder) such that:

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

where the degree of r(x) is strictly less than the degree of g(x). This is analogous to the division algorithm for integers, where we divide a number by another and obtain a quotient and a remainder.

Understanding the Components:

• f(x): This is the dividend, the polynomial being divided.
• g(x): This is the divisor, the polynomial we're dividing by. It must be a non-zero polynomial.
• q(x): This is the quotient, the result of the division.
• r(x): This is the remainder, the part left over after the division. Its degree is always less than the degree of the divisor, g(x).

Proving the Division Algorithm:

We'll prove the existence and uniqueness of q(x) and r(x) separately.

1. Existence:

The proof relies on the principle of mathematical induction on the degree of the dividend, f(x).

• Base Case: If deg(f(x)) < deg(g(x)), then we can simply set q(x) = 0 and r(x) = f(x). The condition that deg(r(x)) < deg(g(x)) is satisfied.

• Inductive Hypothesis: Assume that the division algorithm holds for all polynomials of degree less than n.

• Inductive Step: Let deg(f(x)) = n. Let the leading term of f(x) be a_nxⁿ and the leading term of g(x) be b_mx^m, where n ≥ m. Construct a polynomial h(x) = a_n/b_m * x^n-m. Then consider the polynomial f(x) - g(x)h(x).

The leading term of f(x) is cancelled by the leading term of g(x)h(x), meaning that the degree of f(x) - g(x)h(x) is strictly less than n. By the inductive hypothesis, there exist polynomials q'(x) and r(x) such that:

f(x) - g(x)h(x) = g(x)q'(x) + r(x), where deg(r(x)) < deg(g(x)).

Rearranging, we get:

f(x) = g(x)[h(x) + q'(x)] + r(x)

Let q(x) = h(x) + q'(x). Then we have f(x) = g(x)q(x) + r(x), with deg(r(x)) < deg(g(x)). This completes the inductive step.

2. Uniqueness:

Suppose there exist two sets of polynomials, q₁(x), r₁(x) and q₂(x), r₂(x), satisfying the division algorithm. Then:

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

Subtracting these equations, we get:

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

If q₁(x) ≠ q₂(x), then the degree of the left-hand side is at least the degree of g(x), while the degree of the right-hand side is less than the degree of g(x), which is a contradiction. Therefore, q₁(x) = q₂(x), and consequently, r₁(x) = r₂(x). This proves the uniqueness of q(x) and r(x).

This completes the proof of the division algorithm for polynomials. This fundamental theorem provides a solid base for further explorations in polynomial algebra and its applications. Remember to practice polynomial long division to solidify your understanding.