4
$\begingroup$

There is one small matter that has always stumped me with polynomial long division. In the example from the Wikipedia on Polynomial long division, why is the equation only divided by the first/highest divisor term? This is the correct way, and it obviously works, but I don't understand why. What about the other terms? I realise that they get involved with the multiplying and subtraction, but can't quite see how it all fits together.

Many thanks!

$\endgroup$
1
  • $\begingroup$ You need the degree of the polynomial being divised to decrease, in order to prove that long division terminates. Hence you have to find a polynomial Q (when dividing A by B) such that $deg(A - BQ) < deg(A)$, and the easiest way to do it is to simply set $Q = \frac{a_m}{b_n}x^{m-n}$, and not to take care of the other terms of $B$. $\endgroup$ Commented Sep 17, 2013 at 9:57

4 Answers 4

13
$\begingroup$

Polynomial long division is an algorithm. By that I roughly mean that it is an entirely mechanical procedure that is guaranteed to finish in finitely many steps.

In order to ensure this, we want a notion of progress. In polynomial long division, this progress is measured by the degree of the polynomial in the numerator.

So how to attain progress? All we need to do for that, is eliminate the highest power of $x$ ("the variable") by subtracting a suitable multiple of the denominator, without introducing new, higher powers.

As it turns out, by the nature of polynomial multiplication, we can use only a multiple of the highest power of the denominator to eliminate this highest power of the numerator.

And that is all. In doing so, we have reduced the degree of the remaining numerator by at least one, and so have progressed.

Therefore, the algorithm works, even if we disregard the terms of lower degree in the denominator.


The fundamental difference between polynomials and ordinary integers, i.e. why this so-called greedy procedure works for the former, but not the latter, is because polynomials don't have carries: the degree of $n p(x)$ (for $n \ne 0$) is precisely the degree of $p(x)$. Similarly, in computing:

$$x^2 \cdot (x^2 + 100 x) = x^4 + 100 x^3$$

no part of the $100$ can ever be transferred to the $x^4$ term.

This, fundamentally, is why the same algorithm does not work for computing $\dfrac {100}{37}$: in $3 \cdot 37 = 111$, there will be a carry from the "ones" to the "tens", and a subsequent one from "tens" to "hundreds"; hence, greedily selecting $3$ on the basis of $3 \cdot 30 = 90 < 100$ does not work.

$\endgroup$
1
$\begingroup$

I think when you divide by the highest degree it is guaranteed that when subtracting you will terminate the highest degree term thus only the second term of the divisor is used to ensure that we utilise all terms

$\endgroup$
1
+50
$\begingroup$

Euclid's Division Lemma for polynomials suggests that for any two polynomials $f(x),g(x)$ ϵ R$[x]$ with

$deg(f) ≥ deg(g)$, ∃ unique polynomials $q(x)$ and $r(x)$ with either $deg(r) < deg(g)$ or $r(x)=0$ that satisfy:

$f(x)$ $=$ $g(x)$$q(x)$+$r(x)$

We call $q(x)$ the quotient polynomial and $r(x)$ the division polynomial of this division of $f(x)$ by $g(x)$. A division algorithm for polynomials concerns an algorithmic procedure for the computation of these quotients and remainders, given the starting polynomials $f(x)$ and $g(x)$.

Prerequisite result: For the division of a polynomial $f(x)$ = $\sum_{i=0}^n$ $a_i$$x^i$ by another polynomial $g(x)$ = $\sum_{i=0}^n$ $b_i$$x^i$ of the same degree,

$q(x)$ = $\frac{a_n}{b_n}$ and $r(x)$= $\sum_{i=0}^n$ ($a_i$ $-$ ($\frac{a_n}{b_n}$)$b_i$) $x^i$

This is easy to see intuitively. I encourage you to attempt to prove it yourself

Proof: The quotient and remainder polynomials must satisfy $f(x)$ $=$ $g(x)$$q(x)$+$r(x)$ with either $deg(r) < deg(g) = n$, or $r(x)=0$. Thus, $f(x) - g(x)q(x)$ $=$ $\sum_{i=0}^n$ ($a_i$-$q(x)$$b_i$)$x^i$ $=$ $r(x)$. Assume that $q(x)$ $≠$ $\frac{a_n}{b_n}$. Thus, the coefficient of the $x^n$th term of $r(x)$ $=$ $f(x) - g(x)q(x)$ is nonzero, implying that $deg(r)=n=deg(g)$ which is contradictory. Hence our assumption must be incorrect and therefore we must have $q(x)$ = $\frac{a_n}{b_n}$ and $r(x)$= $\sum_{i=0}^n$ ($a_i$ $-$ ($\frac{a_n}{b_n}$)$b_i$) $x^i$

Concerning ourselves with the most general case, let us consider the division of:

$f(x)$ = $\sum_{i=0}^n$ $a_i$$x^i$ by $g(x)$ = $\sum_{i=0}^m$ $b_i$$x^i$ with $n≥m$

Let us lay down a basic strategy to approach this division. We start by dividing $f(x)$ by a "scaled version" of $g(x)$, i.e by a polynomial of degree $n$ given by multiplying $g(x)$ by a suitable index of $x$ ($n-m$ in this case). This gives a remainder polynomial $r_1(x)$ of degree $m ≤$ $d_1$ < $n$. The process is then carried out again with $r_1(x)$ and $g(x)$ to give a remainder polynomial $r_2(x)$ of degree $m ≤$ $d_2$ < $d_1$. This process is continued until we get a remainder polynomial $r_k(x)$ such that its degree $d_k<m$ or $r_k(x)=0$. Once at this stage, further division is no longer possible and thus the remainder of the division of $f(x)$ by $g(x)$ comes out to be $r_k(x)$ after the completion of our algorithm.

This can be formulated mathematically through extensive use of the Prerequisite result as follows:

1: $f(x)$ = $\frac{a_n}{b_m}$ $x^{n-m}$ $g(x)$ + $r_1(x)$, $deg(r_1)≥deg(g)$- Algorithm incomplete

2: $r_1(x)$ = $\frac{l_1}{b_m}$ $x^{d_1-m}$ $g(x)$ + $r_2(x)$, $deg(r_2)≥deg(g)$- Algorithm incomplete

.

.

.

k: $r_{k-1}(x)$ = $\frac{l_{k-1}}{b_m}$ $x^{d_{k-1}-m}$ $g(x)$ + $r_k(x)$, $deg(r_k)<deg(g)$ or $r_k(x)=0$ - Algorithm complete

$l_t$ denoting the leading coefficient of $r_t(x)$. These k equations when summed together, give-

$f(x)$ + $\sum_{j=1}^{k-1}$ $r_j(x)$ $=$ ($\frac{a_n}{b_m}$ $x^{n-m}$ $+$ $\sum_{j=1}^{k-1}$$\frac{l_{x}}{b_m}$ $x^{{d_j}-m})$ $g(x)$ + $\sum_{j=1}^{k}$ $r_j(x)$

Which simplifies to

$f(x)$ $=$ ($\frac{a_n}{b_m}$ $x^{n-m}$ $+$ $\sum_{x=1}^{k-1}$$\frac{l_{x}}{b_m}$ $x^{{d_j}-m})$ $g(x)$ + $r_k(x)$

Thus, $q(x)$ $=$ ($\frac{a_n}{b_m}$ $x^{n-m}$ $+$ $\sum_{x=1}^{k-1}$$\frac{l_{x}}{b_m}$ $x^{{d_j}-m})$ and $r(x)$ = $r_k(x)$.

If you'd notice carefully, this is exactly what we do in polynomial long division. This also holds the key to understanding why the long division must be done from left to right.

The argument that the successive remainders have strictly decreasing degrees is crucial to conclude the existence of an $r_k(x)$ such that $deg(r_k)<deg(g)$ (or $r_k(x)=0$). This strictly decreasing sequence of the degrees of the remainder polynomial is guaranteed only when the division is carried out in the fashion described above, i.e from left to right in the long division process.

Hope this helps!

$\endgroup$
0
$\begingroup$

Polynomial long division can be done by taking any term at first and dividing. This will also yield the correct result. I cannot assure you that the degree of the remainder will be lesser than that of the divisor, but the equality, Dividend=Quotient*Divisor+Remainder will hold. However, taking the highest term guarantees that the degree of the polynomial will reduce, and we will reach a remainder of degree less than that of the divisor in finitely many steps. If you are to take it in some other order, you may be successful, but it is also possible that you will be stuck in a cycle of trying to cancel out the remainders. You may cancel out one term first, and then when you come to a term higher than that, the term may get back in place with a non-zero coefficient.

If we are to consider how efficient an algorithm is, long division is definitely most efficient when the highest term is taken first. To see why, note that first term you get by this method needs to be added to the quotient at some point in time to cancel that particular term. Knowing this, it makes logical sense to remove that term beforehand so that you can clearly understand the new problem and cancel out other terms accordingly.

Here I said that the highest term must be canceled out at some point, but that is only if you want the remainder to have degree lesser than the divisor. I can also suggest a similar algorithm for divisors with a non-zero constant term, if you decide that you want only terms with degree $n$ to $n+k$ in your remainder, then you can begin by canceling out terms with degree higher than $n+k$ first. This is done in the usual long division way. You can repeat from the other side, first consider the constant terms of both the dividend and divisor and cancel the constant term of the dividend. Repeat for the coefficient of $x$ and so on. However, this works only when the constant term is non-zero. When the constant term in $0$, simply subtract the constant term and add it to the remainder. Now both will have no constant term. Divide both divisor and dividend by $x$ and continue.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .