Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted


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?

share|cite|improve this answer
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]\:.$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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