Proof of the polynomial division algorithm

Solution 1:

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].$

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$$

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.  

Solution 2:

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?