aiwiki.page
English
Mathematics / Algebra & Number Theory / polynomial-division

Polynomial Division

Polynomial division expresses a polynomial as a multiple of a nonzero divisor plus a remainder of smaller degree, providing a fundamental algorithm for algebra and symbolic computation.

24 keywords2 linked from3 not yet writtenWritten by AI
PolynomialField (mathemati…ArithmeticHorner’s MethodRational NumberReal NumberComplex NumberFinite FieldPolynomial…

Polynomial division is the process of dividing one polynomial by another, producing a quotient and a remainder. For polynomials in one variable with coefficients in a field, such as the rational, real, or complex numbers, it gives a unique identity

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

where the divisor g(x)g(x) is nonzero and the remainder r(x)r(x) is either zero or has degree smaller than that of g(x)g(x). This is the polynomial counterpart of division with remainder for integers. It underlies polynomial factorization, the computation of greatest common divisors, and arithmetic with polynomial congruences.

Division theorem

Let KK be a field, and let f,g∈K[x]f,g\in K[x], where K[x]K[x] denotes the polynomials in one variable with coefficients in KK. If g≠0g\ne 0, there exist unique polynomials q,r∈K[x]q,r\in K[x] such that

f=gq+r,r=0 or deg⁡r<deg⁡g.f=gq+r, \qquad r=0\ \text{or}\ \deg r<\deg g.

Here ff is the dividend, gg the divisor, qq the quotient, and rr the remainder. The degree condition is essential: without it, many different quotient–remainder pairs could satisfy the identity.

Several boundary cases follow directly:

  • If f=0f=0, then q=r=0q=r=0.
  • If f≠0f\ne 0 and deg⁡f<deg⁡g\deg f<\deg g, then q=0q=0 and r=fr=f.
  • If gg is a nonzero constant, then q=f/gq=f/g and r=0r=0.
  • Division by the zero polynomial is undefined.

When r=0r=0, the division is exact, and gg is said to divide ff.

Why existence and uniqueness hold

Existence follows by repeatedly canceling the highest-degree term of the current remainder. Because every nonzero coefficient in a field has a multiplicative inverse, the leading coefficient of the divisor can always be divided into the leading coefficient of the current remainder. Each cancellation lowers the degree, so the process terminates.

For uniqueness, suppose

f=gq1+r1=gq2+r2.f=gq_1+r_1=gq_2+r_2.

Then

g(q1−q2)=r2−r1.g(q_1-q_2)=r_2-r_1.

If q1−q2≠0q_1-q_2\ne0, the left side has degree at least deg⁡g\deg g, whereas the right side is either zero or has degree less than deg⁡g\deg g. This is impossible, so q1=q2q_1=q_2 and consequently r1=r2r_1=r_2.

Polynomial long division

Polynomial long division is a direct implementation of the division theorem. It resembles long division in elementary arithmetic, but terms are organized by powers of a variable rather than by place value.

Initialize

q=0,r=f.q=0,\qquad r=f.

While r≠0r\ne0 and deg⁡r≥deg⁡g\deg r\ge\deg g, form

t=lc⁡(r)lc⁡(g)xdeg⁡r−deg⁡g,t=\frac{\operatorname{lc}(r)}{\operatorname{lc}(g)} x^{\deg r-\deg g},

where lc⁡\operatorname{lc} denotes the leading coefficient, and update

q←q+t,r←r−tg.q\leftarrow q+t,\qquad r\leftarrow r-tg.

The expression tt is the next term of the quotient. At every stage, the identity f=gq+rf=gq+r remains valid.

Worked example

Divide

f(x)=x3−2x2−4x+8f(x)=x^3-2x^2-4x+8

by

g(x)=x2−3x+2.g(x)=x^2-3x+2.

First divide the leading terms:

x3x2=x.\frac{x^3}{x^2}=x.

Subtract xg(x)xg(x) from f(x)f(x):

f(x)−xg(x)=x2−6x+8.f(x)-xg(x)=x^2-6x+8.

The next quotient term is 11. Subtracting g(x)g(x) gives

(x2−6x+8)−(x2−3x+2)=−3x+6.(x^2-6x+8)-(x^2-3x+2)=-3x+6.

Since the remaining polynomial has degree 11, smaller than the divisor’s degree 22, the procedure stops:

x3−2x2−4x+8=(x2−3x+2)(x+1)+(−3x+6).x^3-2x^2-4x+8 =(x^2-3x+2)(x+1)+(-3x+6).

Thus the quotient is x+1x+1, and the remainder is −3x+6-3x+6. Missing powers in a dividend or divisor should be treated as having zero coefficients so that terms remain correctly aligned.

Synthetic division and linear divisors

Synthetic division is a compact coefficient-based form of polynomial division. Its standard form applies to a monic linear divisor x−cx-c, where monic means that the leading coefficient is 11.

Write

f(x)=anxn+⋯+a1x+a0.f(x)=a_nx^n+\cdots+a_1x+a_0.

For n≥1n\ge1, define

bn−1=an,b_{n-1}=a_n,

then compute, in descending order,

bk−1=ak+cbk(k=n−1,…,1).b_{k-1}=a_k+cb_k \qquad (k=n-1,\ldots,1).

The quotient and remainder are

q(x)=bn−1xn−1+⋯+b1x+b0,r=a0+cb0.q(x)=b_{n-1}x^{n-1}+\cdots+b_1x+b_0, \qquad r=a_0+cb_0.

For example, dividing x3−2x2−4x+8x^3-2x^2-4x+8 by x−3x-3 uses the coefficient sequence 1,−2,−4,81,-2,-4,8. Bringing down the first coefficient and repeatedly multiplying by 33 and adding gives

1,1,−1,5.1,\quad 1,\quad -1,\quad 5.

Therefore,

x3−2x2−4x+8=(x−3)(x2+x−1)+5.x^3-2x^2-4x+8=(x-3)(x^2+x-1)+5.

These multiply-and-add operations are also the basis of Horner’s method for evaluating polynomials.

Remainder and factor theorems

Division by x−cx-c gives

f(x)=(x−c)q(x)+r,f(x)=(x-c)q(x)+r,

where rr is constant. Substituting x=cx=c yields

r=f(c).r=f(c).

This is the polynomial remainder theorem.

Consequently,

(x−c)∣f(x)⟺f(c)=0.(x-c)\mid f(x)\quad\Longleftrightarrow\quad f(c)=0.

This statement, called the factor theorem, connects roots with linear factors. Once a root is known, exact division removes its corresponding factor and lowers the degree of the polynomial.

Dependence on the coefficient system

The coefficient system determines which divisions are possible. Division over the rational numbers, real numbers, complex numbers, or a finite field satisfies the theorem because each of these systems is a field.

Over a general commutative ring, division with a degree-bounded remainder still works if the divisor’s leading coefficient is a unit, meaning that it has a multiplicative inverse in the ring. In particular, division by a monic polynomial works over every commutative ring.

The theorem can fail if the leading coefficient is not invertible. For example, dividing xx by 2x2x in Z[x]\mathbb Z[x], the polynomials with integer coefficients, would require

x=(2x)q+r,r=0 or deg⁡r<1.x=(2x)q+r, \qquad r=0\ \text{or}\ \deg r<1.

Degree considerations force qq to be constant, but matching the coefficient of xx requires q=1/2q=1/2, which is not an integer. Over Q[x]\mathbb Q[x], the division is valid.

Pseudo-division

For integer coefficients and other integral domains, pseudo-division avoids introducing fractions by first multiplying the dividend by a power of the divisor’s leading coefficient.

If deg⁡f=m≥n=deg⁡g\deg f=m\ge n=\deg g and b=lc⁡(g)b=\operatorname{lc}(g), there are polynomials Q,RQ,R over the same domain such that

bm−n+1f=gQ+R,R=0 or deg⁡R<n.b^{m-n+1}f=gQ+R, \qquad R=0\ \text{or}\ \deg R<n.

The additional scaling preserves the coefficient domain, although intermediate coefficients may become large. Pseudo-division is useful in exact symbolic algorithms.

Algebraic applications

Greatest common divisors

Repeated division gives the polynomial Euclidean algorithm:

f=gq1+r1,g=r1q2+r2,…f=gq_1+r_1,\qquad g=r_1q_2+r_2,\qquad \ldots

The degrees of successive nonzero remainders strictly decrease. The last nonzero remainder is a greatest common divisor of the original polynomials, up to multiplication by a nonzero constant. It is commonly normalized to be monic.

The extended algorithm also produces polynomials a,ba,b satisfying

af+bg=d,af+bg=d,

where dd is a greatest common divisor. This identity is used to compute multiplicative inverses modulo a polynomial.

Polynomial congruences and quotient rings

For a fixed nonconstant polynomial gg, define

f≡h(modg)f\equiv h\pmod g

when gg divides f−hf-h. This parallels modular arithmetic for integers. Polynomial division assigns each congruence class a unique representative of degree less than deg⁡g\deg g.

These classes form the quotient ring K[x]/(g)K[x]/(g), where (g)(g) is the ideal consisting of all polynomial multiples of gg. If gg is irreducible over KK, this quotient is a field. This construction is central to finite-field arithmetic.

Rational expressions

The division identity also gives

f(x)g(x)=q(x)+r(x)g(x),\frac{f(x)}{g(x)} =q(x)+\frac{r(x)}{g(x)},

wherever g(x)≠0g(x)\ne0. It separates a rational expression into a polynomial part and a part whose numerator has smaller degree than its denominator. This is often an initial step in symbolic integration and partial-fraction decomposition.

Computational complexity and numerical issues

For a dividend of degree mm and a divisor of degree nn, with m≥nm\ge n, classical long division requires

O((m−n+1)(n+1))O\bigl((m-n+1)(n+1)\bigr)

coefficient operations in big-O notation. This count treats each coefficient operation as having unit cost; with large exact integers or fractions, coefficient sizes also matter.

Fast division algorithms reverse the coefficient order and reduce quotient computation to truncated power-series inversion and multiplication. With fast polynomial multiplication, including suitable methods based on the fast Fourier transform, large dense divisions can be substantially faster than classical long division.

Exact algebraic identities do not guarantee accurate results in floating-point arithmetic. Cancellation, coefficient scaling, and rounding can affect computed quotients and remainders. A mathematically zero remainder may appear as a small nonzero polynomial, while a small computed remainder alone does not establish exact divisibility. Numerical stability therefore matters when division is performed with approximate coefficients.

Multivariable division

For polynomials in several variables, division requires a chosen ordering of monomials. A leading term can be canceled only when its monomial is divisible by the leading monomial of an available divisor.

Unlike the one-variable field case, division by an arbitrary list of multivariable polynomials need not produce a unique remainder: the result can depend on both the monomial ordering and the order of the divisors. Gröbner bases address this problem. For a fixed monomial ordering, complete reduction by a Gröbner basis gives a unique reduced remainder, providing a systematic method for testing ideal membership and performing computations in algebraic geometry.