3
$\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$
    – zarathustra
    Sep 17, 2013 at 9:57

2 Answers 2

Reset to default
7
$\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$

You must log in to answer this question.

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