# Proof of the polynomial division algorithm

The theorem which I am referring to states: for any $f, g$ there exist $q, r$ such that $f(x)=g(x)q(x)+r(x)$ with the degree of $r$ less than the degree of $g$ if $g$ is monic.

The book I am using remarks that it can be proven via induction on the degree of $g$, but leaves the proof to the reader. Unfortunately, this reader is not clever enough to get it.

The base case is fairly clear, but I'm completely stuck after that. Any hints?

• Huh. I would induct on the degree of $f$ instead. (By the way, to me "the division algorithm" also includes the statement that $q, r$ are unique.) Jul 1, 2011 at 23:28
• Oh - I assumed induction of degree of $f$ as well. I suppose they aren't really too different, but $f$ seems much more natural. Jul 1, 2011 at 23:40

Hint  If $$\, f- g\,h\,$$ has $$\,\deg \ge g\,$$ then subtracting $$\, c\:x^i\:g\$$ so to kill the leading coefficient yields a smaller degree polynomial of same form $$\, f - g\ h'.\,$$ Note: this inducts on $$\,\deg f,\,$$ not on $$\,\deg g$$.

Remark  This method works $$\rm\color{#0a0}{universally}$$ to kill the lead coef of the dividend because the lead coef of the divisor $$\,g\,$$ is a unit (invertible) so it is a divisor of $$\rm\color{#0a0}{every}$$ coefficient, so it is always possible to scale it to agree with the lead coef of the divisor. Otoh, if the lead coef of the divisor is not a unit then this is not always possible, e.g. consider $$\, x \div 2x\:$$ in $$\rm\,\mathbb Z[x]\!:\:$$ if $$\,x = (2x)q(x) + c\,$$ then evaluating at $$\,x=0\Rightarrow c=0,\,$$ therefore cancelling $$\,x\,$$ yields that $$\,1 = 2q(x)\,$$ thus, again, evaluating at $$\,x = 0\Rightarrow 1 = 2q(0)\Rightarrow 2\mid 1\,$$ in $$\Bbb Z,\,$$ contradiction [cf. this proof that $$\,x\nmid 1\,$$ in $$R[x]$$].

The key idea of polynomial division is this: if the divisor has invertible lead coef $$\,b\,$$ (e.g. $$\,b=1)\,$$ and the dividend has degree $$\ge$$ the divisor, then we can $$\rm\color{#c00}{scale}$$ the divisor so that it has the same degree and leading coef as the dividend, then subtract it from the dividend, thereby killing the leading term of the dividend; then recursively apply this process to the remaining part of the dividend, which has smaller degree (since we killed the lead term of the dividend), viz.

\begin{align} (\overbrace{a x^{\large k+n} + f}^{\large \rm dividend})\ -\ &\color{#c00}{\frac{a}b x^{\large k}} (\overbrace{b x^{\large n} + g}^{\large \rm divisor})\ =\ \overbrace{\color{#0a0}{f-\frac{a}b x^kg}}^{\large {\rm deg}\ <\ k+n}\\[.4em] \Longrightarrow\ \ \ \dfrac{a x^{\large k+n}+f}{bx^{\large n}+g}\, =\ &\color{#c00}{\frac{a}b x^{\large k}}\ \ +\ \underbrace{\dfrac{\color{#0a0}{f-\frac{a}bx^{\large k} g}}{bx^n + g}}_{\large\rm recurse\ on\ this}\end{align}\qquad\qquad

$$\require{enclose} \begin{array}{r} \color{#c00}{\frac{a}b x^k}\phantom{x^{k+n}+f\ } \\[0pt] {\Large \smash[t]{\overset{\rm\color{#90f}{tabularly}}{\leadsto^{\phantom{.}}}}}\quad\ bx^n\!+g\,\ \enclose{longdiv}{\,\ a x^{k+n}\,+\,f\phantom{x^kg}} \\[-3pt] \underline{ax^{k+n}\, +\, \frac{a}b x^k g} \\ \color{#0a0}{f\,-\,\frac{a}b x^k g} \end{array}\qquad\qquad\qquad\qquad\quad$$

where the second equation arises from the first by dividing through by $$\,bx^n + g. \,$$ The final expression displayed above shows how this single division step is represented in the common $$\rm\color{#90f}{table\ form}.\,$$ This single division (descent) step is iterated till we reach a dividend that has smaller degree than the divisor (which must occur since $$\Bbb N$$ is well-ordered; equivalently, we can use a proof by strong induction).

Rephrased in the language of Gaussian elimination: $$\,b\,$$ being invertible in the lead monomial $$\,b\:\!x^n\,$$ of the divisor means we can use it as a pivot to scale-up and eliminate all higher degree monomials. This pivoting viewpoint will become clearer when one studies multivariate division algorithms (standard (Grobner) ideal bases and monomial orderings) which are nonlinear generalizations of Gaussian elimination, and unification algorithms for (equational) term rewriting systems.

Remark  Polynomial division can be generalized to divisors with noninvertible lead coef, viz.

Theorem (nonmonic Polynomial Division Algorithm) $$\$$ Let $$\,0\neq F,G\in A[x]\,$$ be polynomials over a commutative ring $$A,$$ with $$\,a\,$$ = lead coef of $$\,F,\,$$ and $$\, i \ge \max\{0,\,1+\deg G-\deg F\}.\,$$ Then
$$\qquad\qquad \phantom{1^{1^{1^{1^{1^{1}}}}}}a^{i} G\, =\, Q F + R\ \ {\rm for\ some}\ \ Q,R\in A[x],\ \deg R < \deg F$$

Proof $$\$$ See here for a few proofs.

There are also multivariate generalizations of the polynomial division algorithm such as the Gröbner basis algorithm. One gains further insight from this more general perspective on the descent process, e.g. in terms of monomial orderings.

• Could you give me an explanation of this: then recursively apply this process to the remaining part of the dividend, which has smaller degree (since we killed the lead term of the dividend)? Feb 27, 2021 at 3:52
• @John We recurse on the new underbraced "smaller" quotient, i.e. our new dividend is the numerator $\,\color{#0a0}{f-\frac{a}b x^k g}\,$ which has smaller degree than the original dividend. See the edit above where I show the corresponding $\rm\color{#90f}{tabular}$ form. May 7, 2021 at 0:27
• @user161005 A coef $\,b\,$ is invertible means that there is some coef $\,c\,$ such that $\,bc = 1,\,$ i.e. $\,b\,$ is a unit (invertible) in the coefficient ring, e.g. for polynomials over a field like $\Bbb Q,\,\Bbb R,\Bbb C\,$ all nonzero coef's are invertible, but over $\Bbb Z$ only $\pm1$ are invertible since, e.g. $2$ isn't invertible in the coef ring $\Bbb Z$ since there is no $\,n\in\Bbb Z\,$ such that $\,2n = 1.\ \$ Jan 28 at 15:59
• How did you get this?: i.imgur.com/EupiXb6.png Feb 1 at 18:23
• @user161005 As explained, we want to scale the divisor $\,bx^n+g\,$ by some $\,\color{#c00}{cx^j}\,$ to make it have the same $\rm\color{#0a0}{lead\ term}$ as the dividend $\,\color{#0a0}{ax^{k+n}} + f$, i.e. so $\,\color{#0a0}{ax^{k+n}} = (cx^j)(bx^n) = \color{#c00}cb x^{\color{#c00}j+n},\,$ so $\,\color{#c00}j = \color{#0a0}k,\ \color{#c00}c = \color{#0a0}a/b\,$ yields the sought scaling term $\,\color{#c00}{\frac{a}b x^k}\ \$ Feb 1 at 18:43

HINT:

Prove that in an integral domain, if $f$ and $g$ are nonzero polynomials then $\deg(fg) = \deg(f) + \deg(g)$. Then, once you have the base case and are working with the induction hypothesis, write out the polynomials. That is, $f = a_n x^n + a_{n-2} x^{n-1} + \cdots + a_0$, $g = b_m x^m + \cdots + b_0$. Multiply $g$ by an appropriate multiple of a power of $x$ and subtract. Use the induction hypothesis.

Does that make sense?

• The ring needn't be a domain. In any ring one can divide (with remainder) by monic divisors. Jul 2, 2011 at 1:05
• To make Bill's claim more clear, the proof works as long as $b_m$ is invertible in $R$. But even if $R$ is an integral domain, the second part of the proof doesn't work if $b_m$ is not invertible. Oct 8, 2020 at 23:34