= Polynomial division
{title2=$f=gq+r$}
= Polynomial division algorithm
{synonym}
<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\ne0$, there are unique <polynomials> $q,r$ satisfying
$$
f=gq+r,\qquad r=0\ \text{or}\ \deg r<\deg g.
$$
Here $q$ is the <polynomial quotient>. The bound concerns <polynomial degree>, rather than the sizes of the <coefficients>.<Fields and Galois Theory by James S. Milne>[Fields and Galois Theory, version 5.10, Chapter 1, p. 10, §1.6: division algorithm, zero remainder alternative and uniqueness]{ref}
For an original example over the <rational numbers>, take
$$
f=2X^3+3X^2-5X+6,\qquad g=X^2+X-2.
$$
<Polynomial long division> first cancels $2X^3$ by subtracting $2Xg$:
$$
f-2Xg=X^2-X+6.
$$
Subtracting one more copy of $g$ cancels $X^2$:
$$
(X^2-X+6)-g=-2X+8.
$$
Thus
$$
q=2X+1,\qquad r=-2X+8,\qquad f=(X^2+X-2)(2X+1)+(-2X+8).
$$
The 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$.
\Image[/polynomial-division-cancellation-ledger.png]
{title=<Polynomial long division> cancels the cubic and quadratic terms in two steps, recording $q=2X+1$ and $r=-2X+8$}
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.<Abstract Algebra by Romyar Sharifi/Chapter 3 Ring theory>[Abstract Algebra, Chapter 3 Ring theory, §3.9, Theorem 3.9.1: division with a unit leading coefficient]{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 gives
$$
X=(2X+1)\frac12-\frac12.
$$
The 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.
Back to article page
