# A question about the division algorithm of polynomials.

My Algebra book (Fraleigh) says the following:

Let $f$ and $g$ be two polynomials. If the leading term of $g$ divides the leading term of $f$, then we can execute a division of $f$ by $g$.

Why is division only then possible? What about $f=x^3+xy^2+1$ and $g=y^2+2$? We can surely write $x^3+xy^2+1=x(y^2+2)+(x^3-2x+1)$

Is it that division is possible only when the degree of the remainder is strictly lower than that of the dividend?

• Is an implication not an if and only if (sufficient but not necessary) – rlartiga Apr 24 '14 at 13:39
• Maybe Fraleigh is only talking about polynomials in one variable. Or maybe he is talking about division in which the remainder is smaller, in some well-defined sense, than the divisor. You have left out all the context. – Gerry Myerson Apr 24 '14 at 13:55
• In your example, leading coefficients of $f$ and $g$ were both $1$... – MattAllegro Apr 24 '14 at 15:43

The point is that when that condition holds then one can scale $$g$$ to make its leading term equal to the leading term of $$f$$, so subtracting the two yields $$f'\!$$ with smaller degree, and $$\,f'\equiv f\pmod g.\,$$ In particular, when the leading coefficient of $$g$$ is $$1$$ (or a unit = invertible) then this is always possible so iterating this reduction we eventually obtain a polynomial of degree smaller than $$g$$, i.e. this yields an algorithm to compute the remainder of $$f$$ on division by $$g$$, the Polynomial Division Algorithm.

The key idea of the polynomial division algorithm is this: if the leading coefficient of the divisor $$= 1$$ (or is invertible), 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 canceling 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 leading term of the dividend), viz.

$$(\overbrace{a x^{k+n} + f}^{\rm dividend}) - \color{#c00}{a x^k} (\overbrace{x^n + g}^{\rm divisor})\ =\ f-ax^kg$$

$$\ \Rightarrow\ \dfrac{a x^{k+n}+f}{x^n+g}\, =\ \color{#c00}{a x^k} +\!\!\! \underbrace{\dfrac{f-ax^k g}{x^n + g}}_{\large\rm recurse\ on\ this}$$

where the second equation arises from the first by dividing through by $$\,x^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 having smaller degree than the divisor.

Remark  Polynomial division can be generalizaed to non-monic polynomials as follows

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.