Polynomial long division

For a shorthand version of this method, see synthetic division.

In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalized version of the familiar arithmetic technique called long division. It can be done easily by hand, because it separates an otherwise complex division problem into smaller ones. Polynomial long division is an algorithm that implements the Euclidean division of polynomials: starting from two polynomials A (the dividend) and B (the divisor) produces, if B is not zero, a quotient Q and a remainder R such that

A = BQ + R,

and either R = 0 or the degree of R is lower than the degree of B. These conditions uniquely define Q and R; the result R = 0 occurs if and only if the polynomial A has B as a factor. Thus long division is a means for testing whether one polynomial has another as a factor, and, if it does, for factoring it out.

Sometimes using a shorthand version called synthetic division is faster, with less writing and fewer calculations, especially when the divisor is a linear polynomial.

Polynomial long division is possible provided that the coefficients of the polynomials belong to the same field, meaning that division by nonzero elements in always possible; examples of fields include the rational numbers, real numbers, and complex numbers.

Example

Find the quotient and the remainder of the division of ${\displaystyle (x^{3}-2x^{2}-4)}$, the dividend, by ${\displaystyle (x-3)}$, the divisor.

The dividend is first rewritten like this:

${\displaystyle x^{3}-2x^{2}+0x-4.}$

The quotient and remainder can then be determined as follows:

1. Divide the first term of the dividend by the highest term of the divisor (meaning the one with the highest power of x, which in this case is x). Place the result above the bar (x³ ÷ x = x²).

   ${\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\end{array}}}$

2. Multiply the divisor by the result just obtained (the first term of the eventual quotient). Write the result under the first two terms of the dividend (x² · (x − 3) = x³ − 3x²).

   ${\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3\ )\ }x^{3}-3x^{2}\end{array}}}$

3. Subtract the product just obtained from the appropriate terms of the original dividend (being careful that subtracting something having a minus sign is equivalent to adding something having a plus sign), and write the result underneath (x³ − 2x²) − (x³ − 3x²) = −2x² + 3x² = x² Then, "bring down" the next term from the dividend.

   ${\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\color {White}x-3\ )\ }{\underline {x^{3}-3x^{2}}}\\{\color {White}x-3\ )\ 0x^{3}}+{\color {White}}x^{2}+0x\end{array}}}$

4. Repeat the previous three steps, except this time use the two terms that have just been written as the dividend.

   ${\displaystyle {\begin{array}{r}x^{2}+{\color {White}1}x{\color {White}{}+3}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\\end{array}}}$

5. Repeat step 4. This time, there is nothing to "bring down".

   ${\displaystyle {\begin{array}{r}x^{2}+{\color {White}1}x+3\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\\{\underline {x^{3}-3x^{2}{\color {White}{}+0x-4}}}\\+x^{2}+0x{\color {White}{}-4}\\{\underline {+x^{2}-3x{\color {White}{}-4}}}\\+3x-4\\{\underline {+3x-9}}\\+5\end{array}}}$

The polynomial above the bar is the quotient q(x), and the number left over (5) is the remainder r(x).

${\displaystyle {x^{3}-2x^{2}-4}=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}}$

The long division algorithm for arithmetic is very similar to the above algorithm, in which the variable x is replaced (in base 10) by the specific number 10.

Pseudocode

The algorithm can be represented in pseudocode as follows, where +, −, and × represent polynomial arithmetic, lead is a function returning the leading term (the term of the highest degree) of a given polynomial as a function input argument, and lead(remainder) / lead(denominator) gives the polynomial obtained by dividing the two leading terms:

function numerator / denominator is
    require denominator ≠ 0
    quotient ← 0
    remainder ← numerator  // At each step numerator = denominator × quotient + remainder

    while remainder ≠ 0 and degree(remainder) ≥ degree(denominator) do
        tmp ← lead(remainder) / lead(denominator)       // Divide the leading terms
        quotient ← quotient + tmp
        remainder ← remainder − tmp × denominator

    return (quotient, remainder)

This works equally well when degree(numerator) < degree(denominator); in that case the result is just the trivial (0, numerator), the while loop is never entered.

This algorithm describes exactly the above paper and pencil method: denominator is written on the left of the ")"; quotient is written, term after term, above the horizontal line, tmp stores the last term of the quotient in each loop repetition; the region under the horizontal line is used to compute and write down the successive values of remainder.

Euclidean division

Main article: Euclidean division of polynomials

For every pair of polynomials (A, B) such that B ≠ 0, polynomial division provides a quotient Q and a remainder R such that

${\displaystyle A=BQ+R,}$

and either R = 0 or degree(R) < degree(B). Moreover (Q, R) is the unique pair of polynomials having this property.

The process of getting the uniquely defined polynomials Q and R from A and B is called Euclidean division (sometimes division transformation). Polynomial long division is thus an algorithm for Euclidean division.^[1]

Applications

Factoring polynomials

Sometimes one or more roots of a polynomial are known, perhaps having been found using the rational root theorem. If one root r of a polynomial P(x) of degree n is known then polynomial long division can be used to factor P(x) into the form (x − r)Q(x) where Q(x) is a polynomial of degree n − 1. Q(x) is simply the quotient obtained from the division process; since r is known to be a root of P(x), it is known that the remainder must be zero.

Likewise, if several roots r, s, . . . of P(x) are known, a linear factor (x − r) can be divided out to obtain Q(x), and then (x − s) can be divided out of Q(x), etc.^[a] Alternatively, the quadratic factor ${\displaystyle (x-r)(x-s)=x^{2}-(r{+}s)x+rs}$ can be divided out of P(x) to obtain a quotient of degree n − 2.

This method is especially useful for cubic polynomials, and sometimes all the roots of a higher-degree polynomial can be obtained. For example, if the rational root theorem produces a single (rational) root of a quintic polynomial (degree five), it can be factored out to obtain a quartic (fourth degree) quotient; the explicit formula for the roots of a quartic polynomial can then be used to find the other four roots of the quintic. There is, however, no general way to solve a quintic by purely algebraic methods, see Abel–Ruffini theorem.

Finding tangents to polynomial functions

Polynomial long division can be used to find the equation of the line that is tangent to the graph of the function defined by the polynomial P(x) at a particular point x = r.^[2] If R(x) is the remainder of the division of P(x) by (x − r)², then the equation of the tangent line at x = r to the graph of the function y = P(x) is y = R(x), regardless of whether or not r is a root of the polynomial.

Example

Find the equation of the line that is tangent to the following curve ${\displaystyle y=(x^{3}-12x^{2}-42)}$

at: ${\displaystyle x=1}$

Begin by dividing the polynomial by: ${\displaystyle (x-1)^{2}=(x^{2}-2x+1)}$

${\displaystyle {\begin{array}{r}x-10\\x^{2}-2x+1\ {\overline {)\ x^{3}-12x^{2}+0x-42}}\\{\underline {x^{3}-{\color {White}0}2x^{2}+{\color {White}1}x}}{\color {White}{}-42}\\-10x^{2}-{\color {White}01}x-42\\{\underline {-10x^{2}+20x-10}}\\-21x-32\end{array}}}$

The tangent line is ${\displaystyle y=(-21x-32)}$

Cyclic redundancy check

A cyclic redundancy check uses the remainder of polynomial division to detect errors in transmitted messages.

See also

• Polynomial remainder theorem
• Synthetic division, a more concise method of performing Euclidean polynomial division
• Ruffini's rule
• Euclidean domain
• Gröbner basis
• Greatest common divisor of two polynomials