10
$\begingroup$

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?

$\endgroup$
2
  • 4
    $\begingroup$ 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.) $\endgroup$ – Qiaochu Yuan Jul 1 '11 at 23:28
  • $\begingroup$ Oh - I assumed induction of degree of $f$ as well. I suppose they aren't really too different, but $f$ seems much more natural. $\endgroup$ – davidlowryduda Jul 1 '11 at 23:40
5
$\begingroup$

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?

$\endgroup$
2
  • 8
    $\begingroup$ The ring needn't be a domain. In any ring one can divide (with remainder) by monic divisors. $\endgroup$ – Bill Dubuque Jul 2 '11 at 1:05
  • $\begingroup$ 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. $\endgroup$ – N. S. Oct 8 '20 at 23:34
10
$\begingroup$

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

where the second equation arises from the first by dividing through by $\,bx^n + g.\,$ The long division algorithm for polynomials is simply a convenient tabular arrangement of the process obtained by iterating this descent process till one reaches 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 viewepoint 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.  

$\endgroup$
1
  • $\begingroup$ 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)? $\endgroup$ – John Mars yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.