Division Algorithm for Polynomials: Explained with Examples

The division algorithm for polynomials says that for polynomials f and g ≠ 0 over a field, there exist unique polynomials q (quotient) and r (remainder) with f = qg + r, where either r = 0 or deg r < deg g. It is long division, generalized: at each step, cancel the leading term of what remains.

It matters because it is the engine of polynomial arithmetic: it proves the remainder theorem (f(c) is the remainder on dividing by x − c), the factor theorem (x − c divides f iff f(c) = 0), and the fact that F[x] is a principal ideal domain — every ideal is generated by one polynomial. Computer algebra systems use it constantly for GCDs and simplification.

Key Concepts

• Dividend, divisor, quotient, remainder: f = qg + r mirrors integer division a = qb + r.
• Degree condition: deg r < deg g (or r = 0) — this is what makes the process terminate.
• Uniqueness: q and r are unique when they exist.
• Field coefficients needed: the algorithm requires dividing by the leading coefficient of g, so coefficients must come from a field (ℚ, ℝ, ℂ, ℤ/pℤ).
• Remainder theorem: dividing f by (x − c) leaves remainder f(c).
• Factor theorem: (x − c) divides f iff f(c) = 0.

Formulas

• The algorithm: f = qg + r with r = 0 or deg r < deg g. (Degrees are nonnegative integers; no physical units.)
• Leading-term step: if the leading term of f is a·x^m and of g is b·x^n with m ≥ n, the next quotient term is (a/b)·x^{m−n}; subtract it times g and repeat.
• Remainder theorem: f = q(x)(x − c) + f(c).
• Degree bounds: deg q = deg f − deg g (when f ≠ 0); deg r ≤ deg g − 1.
• Limit: over ℤ (not a field), division can fail: x² divided by 2x has no quotient in ℤ[x] since 1/2 ∉ ℤ. The divisor must be monic, or coefficients must lie in a field.

Worked Example

Divide f(x) = x³ + 2x² + 1 by g(x) = x + 1 over ℚ. Step 1: leading terms x³ ÷ x = x²; multiply x²(x + 1) = x³ + x²; subtract: (x³ + 2x²) − (x³ + x²) = x². Bring down the rest: x² + 0x + 1. Step 2: x² ÷ x = x; multiply x(x + 1) = x² + x; subtract: (x² + 0x) − (x² + x) = −x. Now −x + 1. Step 3: −x ÷ x = −1; multiply −1(x + 1) = −x − 1; subtract: (−x + 1) − (−x − 1) = 2. The remainder 2 has degree 0 < deg g = 1, so stop. Result: q(x) = x² + x − 1, r = 2. Verify: (x² + x − 1)(x + 1) + 2 = x³ + 2x² + 0x − 1 + 2 = x³ + 2x² + 1 = f(x). Cross-check with the remainder theorem: f(−1) = −1 + 2 + 1 = 2. Both agree.

Common Misconceptions

• "Polynomial division always works over ℤ." It fails when the divisor's leading coefficient does not divide: dividing by 2x + 1 in ℤ[x] gets stuck at the first step.
• "The remainder's degree can equal the divisor's." The algorithm stops only when deg r < deg g — one more step would still be possible otherwise.
• "f(c) = 0 means (x − c) is the only factor." It means (x − c) divides f; the quotient q(x) may factor further (a degree-n polynomial can have up to n linear factors).

Real-World Applications

• Root finding: the factor theorem plus division powers every polynomial root-finder — divide out each found root and continue.
• Error-correcting codes: Reed–Solomon encoding and decoding are polynomial division over finite fields.
• Computer algebra: polynomial GCD (Euclidean algorithm) and fraction simplification run on repeated division.
• Signal processing: deconvolution and filter design use polynomial division in the z-domain.

Polynomial long division repeatedly cancels leading terms until the remainder's degree drops below the divisor's — giving a unique quotient and remainder, and with them the remainder and factor theorems.