Developing an Algorithm to Divide Polynomials

Let us explore polynomial division through an example, hoping it might lead to a general process/algorithm for dividing any two given polynomials.

In doing so, it will be useful to have some verbiage to quickly identify different terms of the polynomials in question. As these can be distinguished by the exponents with which they are associated, let us define the degree of a term in a polynomial of one variable to be the exponent on the variable in that term. Further, let us call the term of highest degree in such a polynomial the leading term. We also call the degree of the leading term the degree of the polynomial.

Additionally, let us refer to the term of a polynomial with degree zero as the constant term (since its value doesn't change, even when the value of the variable changes). We call the term with degree one the linear term (for reasons that will be forthcoming), the term with degree two the quadratic term (from the Latin quadratus which literally means "made square"), the term with degree three the cubic term (from the greek kubikos whose root kobos means "cube"), and the term with degree four the quartic term (in Latin quartus means "fourth"), and the term with degree five the quintic term (similar to the last one, quintus means "fifth" in Latin).

With those definitions aside, let us now suppose we wish to divide $x^3 - 2x^2 - 4$ (the dividend) by $x-3$ (the divisor).

Presuming that the divisor divides the dividend evenly for the moment (recall this need not be the case), let us assume that $(x-3)(\cdots) = x^3 - 2x^2 - 4$. We hope the as-yet-unknown factor on the left will be a polynomial. If it is, it seems clear the leading term of the unknown factor must be $x^2$ so that the product of the two leading terms on the left can produce the leading term of $x^3$ seen on the right. This $x^2$ was of course the result of a quick division of the $x^3$ of the dividend and the $x$ in the divisor.

Of course if we have an $x^2$ as a term in the unknown factor, we can find a partial product $$(x-3)(x^2 + \cdots) = x^3 - 3x^2 + \cdots$$ As such, some of the dividend has been accounted for. We can subtract this $x^3 - 3x^2$ from the dividend to find what remains. As $(x^3 - 2x^2 - 4) - (x^3 - 3x^2) = x^2 - 4$, we can write $$(x-3)(x^2 + \cdots) = (x-3)x^2 + (x-3)(\cdots) = (x^3 - 3x^2) + (x^2 - 4)$$ Note, this allows us to equate $(x-3)(\cdots) = x^2 - 4$ as seen above.

This gives us a new "smaller" problem of the same form (note the degree of the polynomial on the right has been reduced). As such, we can apply the same strategy again (i.e., determine the leading term of what remains unknown is $x$, find the product of this $x$ and $x-3$ and subtract it off to see what still remains of the quotient) -- and again and again, as necessary.

Seeing that we may have to solve a number of such "smaller problems", we will want to keep our work as organized and efficient as possible.

To this end, let us restart the problem using a notation reminiscent of that used for long division of integers. It will also help if we use zero coefficients for any missing powers in our dividend: $$\require{color}\begin{array}{l} x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ \end{array}$$

Recall we earlier found the first part of the quotient, $x^2$, by dividing the leading terms of the dividend and divisor (i.e., $x^3/x$). We do so again, only this time, we place this $x^2$ above the bar but slightly to the right, to align with the term in the dividend of the same degree. $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}{\color{blue}x^2} \\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ \end{array}$$ Again, we now find what the inclusion of this $x^2$ contributes to the product of $(x-3)$ and the unknown factor/quotient by multiplying it by $(x-3)$. Only this time, we write our previously found product $x^2(x-3) = x^3 - 3x^2$, underneath the dividend -- taking care to vertically align terms of common degree so that we easily subtract things to reveal what remains unaccounted for.. $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 \\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ {\color{white}x-3 \ )\ }\underline{{\color{blue}x^3 - 3x^2}}\\ \end{array}$$ Apart from the visual difference of seeing a couple of $0x$ terms, the subtraction results in the same result: $(x^3-2x^2+0x-4) - (x^3-3x^2) = x^2 + 0x -4$. Note however, how we only write the $x^2$ part of this difference on the next line. This is solely to keep our work from getting too cluttered -- we must remember that all three of these terms (shown in red) are still unaccounted for.. $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 \\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2 \ {\color{red}+ \ 0x-4}}\\ {\color{white}x-3 \ )\ }\underline{x^3 - 3x^2}\\ {\color{white}x-3 \ )\ x^3 - 3} {\color{red}x^2} \\ \end{array}$$ Now, we simply repeat the process by asking what must we multiply the $x$ in $x-3$ (i.e., the highest degree term in the divisor) by to get $x^2$ (the highest degree term in what is still unaccounted for from the dividend). A quick division of these two terms reveals this to be $x^2/x = x$, which we again place above the bar. $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 + {\color{white}0}{\color{blue}x}\\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ {\color{white}x-3 \ )\ }\underline{x^3 - 3x^2}\\ {\color{white}x-3 \ )\ x^3 - 3} x^2\\ \end{array}$$ Again, let us find out what including this new $x$ in the quotient adds to the mix by multiplying it by the divisor (i.e., $x(x-3) = x^2-3x$), writing this again on a new line below our existing work, aligning same powers to make the coming subtraction easy... $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 + {\color{white}0}x\\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ {\color{white}x-3 \ )\ }\underline{x^3 - 3x^2}\\ {\color{white}x-3 \ )\ x^3 - 3} x^2 {\color{white}+ 0x}\\ {\color{white}x-3 \ )\ x^3 - 3} \underline{{\color{blue}x^2 - 3x}}\\ \end{array}$$ We again subtract this from what we previously had left to discover what still remains unaccounted for. This time the subtraction performed is $(x^2 + 0x - 4) - (x^2-3x) = 3x - 4$. We again leave these terms (shown in red) a bit "separated" in the interest of not cluttering up things too badly. $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 + {\color{white}0}x\\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x \ {\color{red}{}-4}}\\ {\color{white}x-3 \ )\ }\underline{x^3 - 3x^2}\\ {\color{white}x-3 \ )\ x^3 - 3} x^2 {\color{white}+ 0x}\\ {\color{white}x-3 \ )\ x^3 - 3} \underline{x^2 - 3x}\\ {\color{white}x-3 \ )\ x^3 - 3x^2 - {}} {\color{red}3x} \\ \end{array}$$ Close to being done, we ask what we must multiply the $x$ in $(x-3)$ (i.e., the leading term of the divisor) by to get $3x$, the leading term in what remains unaccounted for. This is of course simply $3$, which we write above the bar $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 + {\color{white}0}x + {\color{blue}3}\\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ {\color{white}x-3 \ )\ }\underline{x^3 - 3x^2}\\ {\color{white}x-3 \ )\ x^3 - 3} x^2 {\color{white}+ 0x}\\ {\color{white}x-3 \ )\ x^3 - 3} \underline{x^2 - 3x}\\ {\color{white}x-3 \ )\ x^3 - 3x^2 - {}} 3x \\ \end{array}$$ We again find the contribution of this $3$'s addition by multiplying it by the divisor -- subtracting this product $3(x-3) = 3x-9$ from what remains as before. Notice that this time, the entirety of the difference $(3x-4)-(3x-9) = 5$ ends up in the bottom-most line -- it is no longer "split" in two different locations any more. $$\require{color}\begin{array}{l} {\color{white}x-3 \ )\ x^3-2}x^2 + {\color{white}0}x + 3\\ x-3 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3-2x^2+0x-4}\\ {\color{white}x-3 \ )\ }\underline{x^3 - 3x^2}\\ {\color{white}x-3 \ )\ x^3 - 3} x^2 {\color{white}+ 0x}\\ {\color{white}x-3 \ )\ x^3 - 3} \underline{x^2 - 3x}\\ {\color{white}x-3 \ )\ x^3 - 3x^2 - {}} 3x \\ {\color{white}x-3 \ )\ x^3 - 3x^2 - {}} \underline{{\color{blue}3x - 9}}\\ {\color{white}x-3 \ )\ x^3 - 3x^2 - 3x - {}} {\color{red}5}\\ \end{array}$$ As asking the question "What can we multiply the $x$ in $x-3$ by to get the $5$ that remains?" would result in an answer involving a negative exponent, we see that our divisor did not evenly go into the dividend, and we consequently have a remainder of $5$.

Our process has thus come to an end, allowing us to say: $$(x^3 - 2x^2 - 4) = (x^2+x+3)(x-3) + 5$$ In this case, we call the $(x^2+x+3)$ the quotient, and $5$ the remainder, and may also write $$(x^3 - 2x^2 - 4) \div (x-3) = (x^2 + x + 3) \textrm{ with a remainder of } 5$$ While above the remainder was a constant value, it need not be. Indeed, when dividing any two polynomials, stopping the process above before any negative exponents appear may leave a polynomial as a remainder -- although its degree will always be less than the divisor polynomial.

When performing the division of polynomials $f(x)$ and $g(x)$, if we find a quotient $q(x)$ and remainder $r(x)$, then we can say $$f(x) = q(x)g(x) + r(x)$$ Dividing both sides by $g(x)$ gives us an alternate way to express this fact. Namely, $$\cfrac{f(x)}{g(x)} = q(x) + \cfrac{r(x)}{g(x)}$$ In our example above, we might then also say:

$$\frac{x^3 - 2x^2 - 4}{x-3} = x^2 + x + 3 + \frac{5}{x-3}$$


This process is easily extended to divisors with higher degree. Consider the work shown below to divide $(x^3 - 8)$ by $(x^2 - 5x + 6)$: $$\begin{array}{l} \hphantom{x^2 - 5x + 6 \ )\ x^3 + 0x^2 + \ 0}x \ + \ 5\\ x^2 - 5x + 6 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^3 + 0x^2 + \ 0x \ - \ 8}\\ \hphantom{x^2 - 5x + 6 \ )\ } \underline{x^3 - 5x^2 + \ 6x}\\ \hphantom{x^2 - 5x + 6 \ )\ x^3 - {}} 5x^2 - \ 6x\\ \hphantom{x^2 - 5x + 6 \ )\ x^3 - {}} \underline{5x^2 - 25x + 30}\\ \hphantom{x^2 - 5x + 6 \ )\ x^3 - 5x^2 - {}} 19x - 38 \end{array}$$

Note, here we again stop when the degree of what remains (i.e., $19x-38$) is less than the degree of the divisor (i.e., $x^2 - 5x + 6$).

We again can state the result in two ways: $$(x^3-8) \div (x^2 - 5x + 6) = (x+5) \textrm{ with a remainder of } (19x - 38)$$ or equivalently, $$\cfrac{x^3 - 8}{x^2 - 5x + 6} = x + 5 + \cfrac{19x-38}{x^2 - 5x + 6}$$

As a matter of verbiage, we call a rational expression where the degree of the numerator equals or exceeds that of the denominator an improper rational expression, and rational expressions where the degree of the numerator is less than that of the denominator a proper rational expression. As such, expressing the quotient as we have immediately above suggest we can always write an improper rational expression as the sum of a polynomial and a proper rational expression -- much in the same way that an improper fraction can be written as the sum of an integer and a proper fraction (i.e., "mixed numeral" form).


Importantly, and perhaps unexpectedly -- the long division algorithm described above forces us to generalize what we mean by a "polynomial".

Heretofore, we had only considered polynomials with integer coefficients, but the many divisions of leading terms that appear in the process described above can produce expressions of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0$ where the coefficients $a_k$ are rational.

Consider the case below, where we divide $(x^2-5x+6)$ by $(19x-38)$. Certainly, the leading term $x^2$ of the dividend must be the product of the leading term of the divisor, $19x$, and the leading term of what we seek. This tells us that we need $\frac{1}{19}x$ as the first term of our answer. An additional rational coefficient, $-\frac{3}{19}$, shows up in a later term as well: $$\begin{array}{l} \hphantom{19x - 38 \ )\ x^2 + {}} \frac{1}{19}x - \frac{3}{19}\\ 19x - 38 \ \overline{\smash{\raise{.6ex}{)}}{\vphantom{)}} \ x^2 \ - 5x \ + \ 6}\\ \hphantom{19x - 38 \ )\ } \underline{x^2 \ -2x}\\ \hphantom{19x - 38 \ )\ x^2 } \ -3x\\ \hphantom{19x - 38 \ )\ x^2 } \ \underline{{}- 3x \ + \ 6}\\ \hphantom{19x - 38 \ )\ x^2 \ -3x \ + {}}\ 0 \end{array}$$ Here, the divisor went into the dividend evenly -- allowing us to say $$(x^2 - 5x + 6) \div (19x - 38) = \textstyle{\frac{1}{19}x - \frac{3}{19}}$$ or equivalently, $$\frac{x^2 - 5x + 6}{19x - 38} = \textstyle{\frac{1}{19}x - \frac{3}{19}}$$ We naturally call expressions like the result of the division above a polynomial with rational coefficients.


The Remainder Theorem and Factor Theorem

We will often find ourselves dividing a polynomial $f(x)$ by something of the form $(x-c)$ where $c$ is some constant. Suppose this results in a quotient $q(x)$ and remainder $r$ (note $r$ is a constant, as it must be of degree less than our divisor $(x-c)$.

Recall, we can then say $$f(x) = q(x) \cdot (x-c) + r$$ Consider what this means for the value of $f(c)$: $$f(c) = q(c) \cdot (c-c) + r = q(c) \cdot 0 + r = r$$ This result turns out to be quite important later, and so we give it a name:

The Remainder Theorem

The remainder of a polynomial $f(x)$ divided by $(x-c)$ equals $f(c)$.

This has an immediate and equally important corollary upon realizing when the remainder resulting from the division of two polynomials is $0$, the divisor is a factor of the dividend:

The Factor Theorem

$(x-c)$ is a factor of a polynomial $f(x)$ when $f(c) = 0$.