# 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.) – Qiaochu Yuan Jul 1 '11 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. – mixedmath Jul 1 '11 at 23:40

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. – Bill Dubuque Jul 2 '11 at 1:05

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

REMARK $\$ Note that this method works universally to cancel the leading coefficient only because the leading coefficient of $\rm\:g\:,$ being a unit, is a divisor of every coefficient, so it is always possible to scale it to agree with the leading coefficient of the polynomial being reduced. For non-monic $\rm\:g\:$ this is not always possible, e.g. consider $\rm\ x \div 2\:x\:$ in $\rm\:\mathbb Z[x]\:.$

-