I think it is a sign.

In the question How does Synthetic Division Work? by the user Riddler on math.stackexchange, Riddler says that he’s never seen a proof of Synthetic Division. This gave me a great case of Mom’s Corollary (the generalization of the fact that when mothers tell you something, you are often reminded of specific cases of it within three days – at least with my mom), as it came up with a student whom I’m tutoring. It turns out many of my students haven’t liked synthetic division. I chatted with some of the other Brown grads, and in general, they didn’t like synthetic division either.

It was one of those things that was taught to us before we thought about why different things worked. Somehow, it wasn’t interesting or useful enough to be revisited. But let’s take a look at synthetic division after the fold:

Synthetic division is a specialized method for dividing a monic polynomial (leading coefficient $latex 1$) by a monomial of the form $latex x – a$. The reason why some people like synthetic division is because it can be done very quickly, although as we’ll see below, we are really just optimizing some of the steps from doing regular polynomial long division. The rule for synthetic division is best seen through example:

Synthetic Division Algorithm:

Say we have the polynomial $latex x^2 – 12x^2 – 42$ and we want to divide it by $latex x – 3$. Then we first write out the coefficients of the polynomial to be divided like this:$latex \begin{array}{c|cccc} & 1& -12 & 0 & -42 \\ \phantom{x} \\ \hline \end{array}$

Since we are dividing by $latex x – 3$, we will write out a $latex 3$ to the left on the second line. Note that from $latex x – 3$ we got a $latex 3$ and not a $latex -3$. This is important, and could mess up a whole lot of computation.

$latex \begin{array}{c|cccc} & 1& -12 & 0 & -42 \\ 3 \\ \hline \end{array}$

Now we have set up the polynomial division, and we just carry out the following steps: Copy down the first coefficient below the bar. Here, we drop down a $latex 1$ like so:

$latex \begin{array}{c|cccc} & 1& -12& 0 & -42 \\ 3 \\ \hline & 1 \end{array}$

We then multiply the dropped number by the $latex 3$ and place it in the next column. So beneath the $latex -12$, we now have a $latex 3$. We then add in that column, so that we get a $latex -9$. Our diagram now looks like:

$latex \begin{array}{c|cccc} & 1& -12& 0 & -42 \\ 3 & & 3& \\ \hline & 1 &-9& \end{array}$

We now repeat to the end of the diagram. The completed diagram for this example will look like

$latex \begin{array}{c|cccc} & 1& -12& 0 & -42 \\ 3 & & 3& -27 & -81\\ \hline & 1 &-9& -27 & -123 \end{array}$

Ok, so now what? It turns out that this last line contains our answer. The last term gives the remainder, the next to last gives the constant term, then the linear term, then the quadratic (and so on, if there were more terms). So here, our remainder coefficient is $latex -123$, so it’s $latex \frac{-123}{x-3}$, our constant term is $latex -27$, our linear coefficient is $latex -9$, and our quadratic coefficient is $latex 1$. So we think that answer is $latex x^2 – 9x – 27 – \frac{123}{x-3}$. Multiplying it out, we even see that’s it’s correct.

The general method is very similar. You drop down the first coefficient, bring multiply it by the left term to bring it to the next column, add that column, multiply it by the left term and bring it to the next column, and so on until you’re out of columns. Let’s look at another, but let’s cheat to see what it will look like. We know that if we divide $latex (x-1)(x+1)(x-2) = x^3 – 2x^2 – x + 1$ by $latex (x-2)$ we should get $latex x^2 – 1$. The synthetic division diagram looks like

$latex \begin{array}{c|cccc} & 1 &-2 &-1 &2 \\ 2 & & 2 & 0 &-2 \\ \hline & 1 & 0 & -1 & 0 \end{array}$

And this is exactly correct, as our answer has no remainder and gives $latex x^2 – 1$. What if we were to divide it by $latex (x + 1)$ instead? This is a bit different, as you should note that we don’t just put a $latex 1$ out to the left. Synthetic division only works on divisors of the form $latex (x – a)$, so we write $latex (x + 1) = (x – (-1))$. Then the synthetic division diagram looks like:

$latex \begin{array}{c|cccc} & 1 &-2 &-1 &2 \\

-1 & & -1 & 3 &-2 \\

\hline & 1 & -3 & 2 & 0 \end{array}$

And this is again correct. That’s handy. There is a way to do a synthetic-like division for dividing by quadratics, etc, but it’s much longer. The greatest strength of synthetic division is that it’s very compact, and if you know how it’s done, it can be done very, very quickly. Combined with bits like the Rational Root Theorem and Factor Theorem, if can speed up the process of factoring and finding roots too.

All that’s is well-said, but this might leave a gap in the pit of your stomach, or perhaps a pit in the gap of your stomach. Why does it work? Let’s see why:

Let’s go back to the original problem of dividing $latex x^3 – 12x^2 – 42$ by $latex x – 3$, and write it out using long division.

$latex \begin{array}{cccc|ccc}

x^3& -12x^2 & 0x & -42 & & x & -3 \\

\hline

-x^2(x & -3)&&& x^2 \\

0&-9x^2&0x &&\\

& -9x(x& -3) && & -9x\\

&0&-27x&-42&& \\

&&-27(x & -3) &&&-27 \\

&&&-123&&

\end{array}$

And so we again get $latex x^2 – 9x – 27 – \frac{123}{x-3}$. But why did this give the same answer. Let’s look at the algorithm again,

It’s clear that the first coefficient will be a $latex 1$, because it’s a monic polynomial. So this is no shock. To see what the next line is, we multiply $latex (x-3)$ by $latex x^2$ to get $x^3 – 3x^2$. Of course, we knew the cubic terms would cancel (that’s why we chose to multiply $latex 1$), so we only need to pay attention to the $latex -3x^2$. But since we’re dividing by $latex (x-3)$, in particular that there is a $latex -3$ instead of a $latex +3$, carrying out the arithmetic leads to us *adding* $latex 3x^2$ on the next line. This is why, after we switch the sign on $latex a$ in the $latex (x-a)$ term, we just multiply and add.

And this directly gives us the next coefficient, because we again are dealing with division by a monic polynomial $latex x-3$ (so no leading coefficient problem). Put another way, synthetic division is a clever way of combining two lines of the polynomial long division into one step, which is to ‘multiply the number at the bottom of the column by $latex -a$ (corresponding to finding the result of the last multiplication and ignoring the leading term because it will cancel out in the long division) and adding (corresponding to carrying out the addition in the long division).

If you write out a couple side-by-side, a rigourous proof becomes very clear, though perhaps not fun to write.

Pingback: Polynomial division code | DL-UAT