Polynomial division ($f=gq+r$)

Polynomial division separates a polynomial into a multiple of a chosen divisor and a smaller polynomial remainder. Given $f,g\in F[X]$ over a field $F$, with $g\ne 0$, there are unique polynomials $q,r$ satisfyingHere $q$ is the polynomial quotient. The bound concerns polynomial degree, rather than the sizes of the coefficients.^[ref]

For an original example over the rational numbers, takePolynomial long division first cancels $2X^3$ by subtracting $2Xg$:Subtracting one more copy of $g$ cancels $X^2$:ThusThe final polynomial remainder has polynomial degree one, below the divisor's polynomial degree two. Multiplying out the last identity checks every coefficient, including the constant term $-2+8=6$.

The polynomial degree bound makes this decomposition useful: it replaces a potentially long polynomial with a short polynomial remainder whenever multiples of $g$ can be discarded. At any root of a polynomial of $g$, those multiples vanish under polynomial evaluation. Repeated polynomial division also drives the Euclidean algorithm for finding a greatest common divisor of polynomials.

The coefficient setting matters. Over a commutative ring, the same existence and uniqueness hold when the divisor's leading coefficient is a unit in a ring. A monic polynomial therefore works over the integers, even though they do not form a field; monic polynomial division over a ring explains why zero divisors cause no difficulty in that case.^[ref]

A nonzero divisor alone is insufficient over the integers. Dividing $X$ by $2X+1$ with an integer polynomial quotient and a constant polynomial remainder would require $1=2c$ for an integer $c$, which is impossible. Over the rational numbers the division instead givesThe obstruction is the nonunit leading coefficient $2$. This example separates existence from uniqueness: over an integral domain, the polynomial degree argument still makes any admissible pair unique, if it exists.

In polynomial division $q=Qs+r$ over a field, the polynomial quotient is the polynomial $s$. The polynomial remainder $r$ has smaller polynomial degree than the nonzero divisor $Q$ unless it is zero.

In the notation $f=gq+r$, the polynomial quotient is instead named $q$. It is a polynomial determined by the divisor and the polynomial degree bound. The pointwise ratio of the associated polynomial functions satisfiesFor the worked example, $f(0)/g(0)=6/(-2)=-3$, while $q(0)=1$; the correction is $r(0)/g(0)=8/(-2)=-4$. Thus a polynomial quotient need not equal the rational function $f/g$. At $x=1$ and $x=-2$, the pointwise ratio is undefined, but the polynomial quotient still has perfectly well-defined values. When $r=0$, the divisor is a polynomial factor of $f$ and the ratio agrees with $q$ wherever $g(x)\ne 0$.

The polynomial remainder is the polynomial $r$ in polynomial division $q=Qs+r$. Division by $X-a$ has a constant polynomial remainder $q(a)$, as expressed by the factor theorem.

For any identity $f=gq+r$, polynomial evaluation at a root of a polynomial $a$ of $g$ givesThis substitution requires no division by $g(a)$. In the worked example, polynomial factorization gives $g=(X-1)(X+2)$, so its two roots of a polynomial are $1$ and $-2$. The cubic polynomial and its linear polynomial remainder agree there:A cubic expression has been compressed into a straight line carrying exactly these two values.

Conversely, those two values determine the linear polynomial remainder by polynomial interpolation. Write $r=AX+B$; then $A+B=6$ and $-2A+B=12$, giving $A=-2$ and $B=8$. The polynomial degree bound is essential: adding any multiple of $g$ preserves the two values, but generally raises the polynomial degree. The plot also shows agreement at $x=-1/2$, where $q=0$ rather than $g=0$. Agreement of $f$ and $r$ at a point therefore does not imply that the point is a root of a polynomial of the divisor.

Dividing a polynomial $f$ by $X-a$ leaves the constant polynomial remainder $f(a)$. Polynomial division makes the polynomial remainder constant because its polynomial degree must be below one; polynomial evaluation at $a$ identifies that constant. In particular, it is zero exactly when $a$ is a root of a polynomial of $f$, which is the factor theorem.^[ref]

In the worked example, division by $X-1$ leaves $6$ and division by $X+2$ leaves $12$. Division by their product leaves $-2X+8$, a polynomial remainder that stores both values at once. The argument also holds over a commutative ring for $a$ in that ring, because $X-a$ is a monic polynomial.

Start with a provisional polynomial quotient $q=0$ and remainder $h=f$. If $h$ has polynomial degree $n$ at least the divisor's polynomial degree $m$, with leading coefficients $a$ and $b$, subtract $tg$, whereThe identity $f=gq+h$ survives each step, while the leading term cancels and the polynomial degree of nonzero $h$ strictly decreases. Stop when $h=0$ or $\mathrm{deg}h<m$.

For uniqueness over a field, subtract two proposed decompositions:If $q_1\ne q_2$, the left side has polynomial degree at least $\mathrm{deg}g$, while the right side is zero or has smaller polynomial degree. Hence $q_1=q_2$ and then $r_1=r_2$.^[ref]