Polynomial long division -- How does it work?

[TheSodesa]

Let's say I wanted to do the following calculation: (x^2 + 2x + 1) / (x+1)

I've scrolled through some online guides, and they all show how to do it, but not the principle behind it. I'm specifically having trouble with the fact, that instead of dividing the largest degree term with the entire denominator x+1 = x¹+x⁰, they only take the largest degree term from the denominator, and divide it into the largest degree term in the numerator, as they progress down the steps.

How can they just ignore the number 1 in this case. I know that once the largest degree terms have been divided, the result is then multiplied into the denominator and therefore the 1 is not completely ignored, but it just doesn't make sense to me.

I don't see the connection between dividing 121 by 11, which is the same as dividing 121 = 1*10^2 + 2*10^1 + 1 * 10^0 by (1*10^1+1*10^0) which is equivalent to dividing x^2 + 2x + 1 by x+1.

Could someone clarify the specifics for me? Why can I ignore the lower degree terms when doing the divisions?

 

[rcgldr]

Each quotient term is the result of dividing the most significant dividend term by the most significant divisor term. The lower order terms in the dividend are not needed until they eventually become the most significant terms, and until then, zeroes can be used for the lower order terms in the dividend to calculate intermediate results.

 

[SteamKing]

It's not clear what you mean when you say that the lower degree terms are ignored when doing long division, be it with numbers or polynomials.

The long division algorithm is a stepped process: it generally takes more than one step to complete the process of finding the quotient.

To take the example polynomial division: (x^2 + 2x + 1) / (x+1)

      ____________
x+1 ) x^2 + 2x + 1

for step 1, the first term of the dividend, x^2, is a higher degree than the highest power of the divisor, x.  We find out how many times x^2 can be divided by x:

Step 1:

        x
      ____________
x+1 ) x^2 + 2x + 1

The first part of the quotient is x, since (x+1) * x = x^2 + x
We subtract this result from the original dividend:

Step 2:

        x
      ____________
x+1 ) x^2 + 2x + 1
      x^2 +  x
      ---------------
             x + 1

Now, we wish to find out by what factor multiplied by the divisor, x + 1, gives x + 1.
This factor is 1, so multiplying and subtracting:

Step 3:

        x + 1
      ____________
x+1 ) x^2 + 2x + 1
      x^2 +  x
      ---------------
             x + 1
             x + 1
      ---------------
               0

We have the quotient, x + 1, which, multiplied by the divisor x + 1, gives the original dividend.

The same procedure is followed for long division involving numbers, but let's take a more interesting example:

      ________
45  ) 125486

45 is greater that 1 and 12, but not 125, so this is where we start the algorithm:

Step 1:

        2
      ________
45  ) 125486
       90
     -----------
       354

Step 2:

        27
      ________
45  ) 125486
       90
     -----------
       354
       315
     -----------
        398

Step 3:

        278
      ________
45  ) 125486
       90
     -----------
       354
       315
     -----------
        398
        360
     -----------
         386

Step 4:

        2788
      ________
45  ) 125486
       90
     -----------
       354
       315
     -----------
        398
        360
     -----------
         386
         360
     -----------
          26

And so on, until we reach a zero result in the subtractions or we have sufficient decimals in the quotient. For this example, the quotient is 2788.57, with the 7 repeating.

 

[TheSodesa]

This is going to be awkward, since I don't know how to make a code window like SteamKing above, but if we were to replicate the method of polynomial long division with simple numerical long division, 121/11 = (100 + 20 + 1) / (10 + 1)

1) We would first divide 12 by 10 (from 11 = 10 + 1) and then multiply the result into 10 + 1 (the divisor), which would give us 1*10 + 1*1 = 10 + 1 = 11, the original divisor.

2) We would then subtract 10 + 1 from 12 = 10 + 2, which would give us 1.

3) Then we would take down the remaining less significant 1 from the dividend and add it to the 1 we got from the subtraction, resulting in 11.

4) Then we would divide 11 by 11 and get 1, multiply this one into the divisor again to get 11, subtract, and end up with the remainder 0.

I do know what I'm supposed to do in long division, I'm just not comfortable with the 'why' of it. Why can I divide 12 by 10 and multiply the result into 11 to get the same answer as if I was dividing 12 by 11 and then multiplying the answer into 11? 12/11 and 12/10 do not produce the same remainder(the result of the subtraction procedure that is done during long division).

 

[rcgldr]

It's not clear what you mean when you say that the lower degree terms are ignored when doing long division, be it with numbers or polynomials.

What I meant is that it is possible to implement long division substituting zeros for lower degree terms of the dividend, until a term in the dividend becomse the most significant term. This is how some types of hardware implement finite field polynomial division, such as crc or ecc. The advantage is that only one term of the dividend is needed for each division step. I was thinking that seeing this method to implement long division might help understand how polynomial division works.

     _____________
x+1 ) x^2 + 2x + 1

first quotient term:

            x
     _____________
x+1 ) x^2 + 0x + 0
      x^2 + 1x
      ---------
           -1x

add the next term from the dividend

           -1x
           +2x
        ------
             x

second quotient term:

          1
   ________
x+1)  x + 0
      x + 1
      -----
         -1

add the next term from the dividend

        -1
        +1
     -----
         0  -> this is the remainder

x + 1 -> is the quotient

I don't see the connection between dividing 121 by 11, which is the same as dividing 121 = 1*10^2 + 2*10^1 + 1 * 10^0 by (1*10^1+1*10^0) which is equivalent to dividing x^2 + 2x + 1 by x+1.

The difference is there is no carries or borrows in the case of polynomial division, so the quotient terms are a function of the most significant working dividend terms and the most significant divisor term.

 

[olivermsun]

The difference is there is no carries or borrows in the case of polynomial division, so the quotient terms are a function of the most significant working dividend terms and the most significant divisor term.

Good point.

To go along with no carries or borrows, you can also have negative terms in polynomial division whereas you don't allow that for "number" division.

 

[SteamKing]

This is going to be awkward, since I don't know how to make a code window like SteamKing above, but if we were to replicate the method of polynomial long division with simple numerical long division, 121/11 = (100 + 20 + 1) / (10 + 1)

You can substitute x = 10 in the expanded polynomial long division example above and follow the mechanics of the numerical division of 121 by 11, because 121 = 10^2 + 2*10 + 1.

 

[Nugatory]

This is going to be awkward, since I don't know how to make a code window like SteamKing above

Click the "quote" button under SteamKing's post and you'll see how he did it.
(just remember not to submit your reply if you're just looking at how he constructed his post, instead of replying to it)

 

[rcgldr]

To go along with no carries or borrows, you can also have negative terms in polynomial division whereas you don't allow that for "number" division.

As an example of this, take the case of 121/14. Using polynomial long division, x^2 + 2x + 1 / x + 4 = x - 2, remainder 9. With number division, 121/14 = 8, remainder 9. You normally don't write 8 as (10-2) with number division.

 

[SteamKing]

This is going to be awkward, since I don't know how to make a code window like SteamKing above, but if we were to replicate the method of polynomial long division with simple numerical long division, 121/11 = (100 + 20 + 1) / (10 + 1)

1) We would first divide 12 by 10 (from 11 = 10 + 1) and then multiply the result into 10 + 1 (the divisor), which would give us 1*10 + 1*1 = 10 + 1 = 11, the original divisor.

2) We would then subtract 10 + 1 from 12 = 10 + 2, which would give us 1.

3) Then we would take down the remaining less significant 1 from the dividend and add it to the 1 we got from the subtraction, resulting in 11.

4) Then we would divide 11 by 11 and get 1, multiply this one into the divisor again to get 11, subtract, and end up with the remainder 0.

I do know what I'm supposed to do in long division, I'm just not comfortable with the 'why' of it. Why can I divide 12 by 10 and multiply the result into 11 to get the same answer as if I was dividing 12 by 11 and then multiplying the answer into 11? 12/11 and 12/10 do not produce the same remainder(the result of the subtraction procedure that is done during long division).

To clarify, in the first step of the division algorithm, you are dividing 120 by 11. This is a consequence of using numerals written with positional notation.

120 / 11 = 10, check 10 * 11 = 110

The next step subtracts 110 from 121, leaving 11. The quotient of 11/11 = 1. Adding the two partial results together produces Q = 10 + 1 = 11, which is 121/11.

 

[HakimPhilo]

Polynomial long division can be viewed as a more general case of the Euclidean algorithm. The basic procedure is similar to integers. At each step $k$, a quotient polynomial $q_k(x)$ and a remainder polynomial $r_k(x)$ are identified to satisfy the recursive equation
$$r_{k−2}(x) = q_k(x) r_{k−1}(x) + r_k(x),$$ where $r_{−2}(x) = a(x)$ and $r_{−1}(x) = b(x)$. The quotient polynomial is chosen so that the leading term of $q_k(x) r_{k−1}(x)$ equals the leading term of $r_{k−2}(x)$; this ensures that the degree of each remainder is smaller than the degree of its predecessor $\deg[r_k(x)] \lt \deg[r_{k−1}(x)]$. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The final nonzero remainder is the greatest common divisor of the original two polynomials, $a(x)$ and $b(x)$.

You can gain a deeper understanding by viewing this as a special case of multivariate polynomial division algorithms, such as the Gröbner basis algorithm. One gains further insight from this more general perspective of monomial orderings.

 

[TheSodesa]

Polynomial long division can be viewed as a more general case of the Euclidean algorithm. The basic procedure is similar to integers. At each step $k$, a quotient polynomial $q_k(x)$ and a remainder polynomial $r_k(x)$ are identified to satisfy the recursive equation
$$r_{k−2}(x) = q_k(x) r_{k−1}(x) + r_k(x),$$ where $r_{−2}(x) = a(x)$ and $r_{−1}(x) = b(x)$. The quotient polynomial is chosen so that the leading term of $q_k(x) r_{k−1}(x)$ equals the leading term of $r_{k−2}(x)$; this ensures that the degree of each remainder is smaller than the degree of its predecessor $\deg[r_k(x)] \lt \deg[r_{k−1}(x)]$. Since the degree is a nonnegative integer, and since it decreases with every step, the Euclidean algorithm concludes in a finite number of steps. The final nonzero remainder is the greatest common divisor of the original two polynomials, $a(x)$ and $b(x)$.

You can gain a deeper understanding by viewing this as a special case of multivariate polynomial division algorithms, such as the Gröbner basis algorithm. One gains further insight from this more general perspective of monomial orderings.

This is sort of the general answer I was looking for, except I would have to learn what words like "recursive equation" and "monomial orderings" mean, before I can actually start looking at this properly. :tongue:

 

[Alicelewis11]

My companion have said right that each remainder term is the result of dividing the most significant divided term by the most significant divisor term. The lower terms in the divided are not required until they inevitably turned into the most significant terms, and until then, zeroes could be utilized for the lower request terms in the profit to compute transitional results.

 

[SteamKing]

This is sort of the general answer I was looking for, except I would have to learn what words like "recursive equation" and "monomial orderings" mean, before I can actually start looking at this properly. :tongue:

It's better to learn the long division algorithm in grade school. If you wait too long to master it, then you need a PhD. in Mathematics to understand the algorithm.

 

[symbolipoint]

This is sort of the general answer I was looking for, except I would have to learn what words like "recursive equation" and "monomial orderings" mean, before I can actually start looking at this properly. :tongue:

My companion have said right that each remainder term is the result of dividing the most significant divided term by the most significant divisor term. The lower terms in the divided are not required until they inevitably turned into the most significant terms, and until then, zeroes could be utilized for the lower request terms in the profit to compute transitional results.

It's better to learn the long division algorithm in grade school. If you wait too long to master it, then you need a PhD. in Mathematics to understand the algorithm.

Some students do not really understand long division algorithm in grade school --- instead, they really understand well enough a few years AFTER grade school, and only at this time the algorithm really makes sense. Polynomial long division as taught in ninth-grade Algebra 1 is one of those things that pushes a student into real progress for ordinary long division. Suddenly, long division seems to make sense.