# Synthetic division via the greedy strategy

I was looking at the expanded synthetic division within Wikipedia. I was stumped by how to come up with and perform the 'compactified' version of synthetic division.

Does anyone know how to do it?

-
I must admit I can't make much sense of that section of the Wikipedia article. But there's little mathematical content there -- if you understand the division algorithm for polynomial rings, the different flavors of synthetic division are just notational shortcuts. – user7530 Dec 24 '12 at 22:31
Come up with and perform are two very different verbs. The article shows how to perform it, but doesn't explain how somebody envisioned the algorithm. This one looks like somebody did a lot of synthetic division and thought about how to only write down what was needed. – Ross Millikan Dec 25 '12 at 4:01

I came up with three shorthand methods from noticing certain patterns, but the one I describe below is the simplest:

1. Write the coefficients of the dividend on a bar

$\begin{array}{cc} \begin{array}{|rrrrrrrr} a & b & c & d & e & f & g & h \\ \hline \end{array} \end{array}$

1. Negate the coefficients of the divisor. Write in every coefficient of the divisor but the first (leading coefficient) one on the left.

$\begin{array}{cc} \begin{array}{rrrr} i &j & k & l \\ \end{array} & \begin{array}{|rrrrrrrr} a & b & c & d & e & f & g & h \\ \hline \end{array} \end{array}$

1. From the number of coefficients placed on the left side, count the number of dividend coefficients above the bar and then place a vertical bar on the row below. This vertical bar marks the separation between the quotient and the remainder.

$\begin{array}{cc} \begin{array}{rrrr} i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} a & b & c & d & e & f & g & h \\ \hline & & & & & & & \\ \end{array} \end{array}$

1. Drop the first coefficient of the dividend below the bar.

$\begin{array}{cc} \begin{array}{rrrr} i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} a & b & c & d & e & f & g & h \\ \hline m & & & & & & & \\ \end{array} \end{array}$

1. Multiply the last dropped/summed number to each negated coefficients on the left (starting with the left most); skip this step if the summed number is zero. Place each product on top of the subsequent columns.

$\begin{array}{cc} \begin{array}{rrrr} \\ i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} & mi & mj & mk & ml & & & \\ a & b & c & d & e & f & g & h \\ \hline m & & & & & & & \\ \end{array} \end{array}$

1. Perform an column-wise addition on the next column.

$\begin{array}{cc} \begin{array}{rrrr} \\ i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} & mi & mj & mk & ml & & & \\ a & b & c & d & e & f & g & h \\ \hline m & n & & & & & & \\ \end{array} \end{array}$

1. Repeat the previous two steps. Stop when you performed the previous two steps on the number just before the vertical bar.

$\begin{array}{cc} \begin{array}{rrrr} \\ \\ i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} & & ni & nj & nk & & & \\ & mi & mj & mk & ml & nl & & \\ a & b & c & d & e & f & g & h \\ \hline m & n & o & & & & & \\ \end{array} \end{array}$

$\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} & & & oi & oj & & & \\ & & ni & nj & nk & ok & & \\ & mi & mj & mk & ml & nl & ol & \\ a & b & c & d & e & f & g & h \\ \hline m & n & o & p & & & & \\ \end{array} \end{array}$

$\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ \\ i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} & & & & pi & & & \\ & & & oi & oj & pj & & \\ & & ni & nj & nk & ok & pk & \\ & mi & mj & mk & ml & nl & ol & pl \\ a & b & c & d & e & f & g & h \\ \hline m & n & o & p & q & & & \\ \end{array} \end{array}$

1. Perform the remaining column-wise additions on the subsequent columns (getting the remainder).

$\begin{array}{cc} \begin{array}{rrrr} \\ \\ \\ \\ i &j & k & l \\ \\ \end{array} & \begin{array}{|rrrr|rrrr} & & & & pi & & & \\ & & & oi & oj & pj & & \\ & & ni & nj & nk & ok & pk & \\ & mi & mj & mk & ml & nl & ol & pl \\ a & b & c & d & e & f & g & h \\ \hline m & n & o & p & q & r & s & t \\ \end{array} \end{array}$

1. The results below the horizontal bar would be interpreted with increasing degree from right to left beginning with degree zero for both the remainder and the result.

EDIT: I went ahead and edited the wiki.

-

This is showing a compact (notional shortcut) for doing synthetic division as the non-compactified variant is just a lot of writing.

So, I have worked an example using a seventh-order equation so we can follow along with the Wiki site you reference for expanded synthetic division.

One VERY important note in this approach is that you are jumping between filling in a row value and filling in a column value. Just as soon as you can fill in a value, you do so. I am going to provide you all of the values, but do it in order and see how to fill in the triangle (if you will) of values on your own.

To actually understand why it works, you will have to use the SAME example with the previous method on the site, so you can see that this is just a very compactified variant of the previous method. Please do this or you won't understand the compactified method!

Using compactified synthetic division, find the quotient and remainder of the following

$$\frac{x^{7} + 2x^{6} + 3x^{5} + 4x^{4} +5x^{3} + 6x^{2} + 7x +8}{x^{4} -2x^{3} -3x^{2}-4x -5}$$

Note, when the items below says calculate, recall that you are bouncing between row and column calculations and doing each one just as soon as having the necessary values permit.

I am going to write these in the order as shown on the web page (you are effectively starting at Row 1 and working up to Row 5) - so,

Row 5: Calculate: $p i = 96$

Row 4: Calculate: $o i = 28$ $o j = 42$ $p j = 144$

Row 3: Calculate: $n i = 8$ $n j = 12$ $n k = 16$ $o k = 56$ $p k = 192$

Row 2: Calculate: $m i = 2$ $m j = 3$ $m k = 4$ $m l = 5$ $n l = 20$ $o l = 70$ $p l = 240$

Row 1: Write out the entire bottom row, that is:

$i = 2$, $j = 3$, $k = 4$, $l = 5$ $\vert$ $a=1$ $b=2$ $c=3$ $d=4$ $e=5$ $f=6$ $g=7$ $h=8$

Row 0: this is the resultant quotient and remainder, and it is being filled out just as soon as we have all the necessary column values by just summing all of the values in the respective column.

$m=1$ $n=4$ $o=14$ $p=48$ $\vert$ $q=164$ $r=226$ $s=269$ $t=248$

Therefore, using the compactified variant of synthetic division yields the following quotient and remainder

$x^{3} + 4 x^{2} + 14 x + 48$ + $\frac{164 x^{3} + 226 x^{2} + 269 x +248}{x^{4} -2x^{3} -3x^{2}-4x -5}$

Lets verify the result using WolframAlpha.

So, now try this approach with the previous example they show on the web site and you'll see how it works. I also recommend you do several more examples of varying sizes to make sure you get it! You can check your work using your favorite CAS or WolframAlpha.

Update

The compactified - synthetic division variant is just re-writing synthetic division is a sort of shorthand. Synthetic division is just writing long polynomial division in shorthand.

Regards

-
Thanks for your input. But I'm asking how you would come up with the compactified variant of synthetic division. – Dashed Dec 25 '12 at 1:43
Well, your question did not ask for that. It asked how to perform the 'compactified' version of synthetic division. As this new question, this is just writing a compact version of the synthetic algorithm, there is no magic here - it is just compacting the method shown on the web site to a smaller form. – Amzoti Dec 25 '12 at 1:48
In fact, even synthetic division is just a variant of long polynomial division that has itself been written in a sort of shorthand. Regards – Amzoti Dec 25 '12 at 1:57
Sorry, I edited for clarification. – Dashed Dec 25 '12 at 3:34
+1nice work, answering an ambiguous (unstated) question! – amWhy May 11 '13 at 0:19