Olivine logo
My main page / Fully Homomorphic encryption basics / Polynomial Long Division

Polynomial Long Division

#algebra #polynomials

Dividing polynomials works exactly like long division with numbers: divide the leading terms, multiply back, subtract, and repeat until what's left is too small to divide further.

The division algorithm

Theorem. Let $f(x)$ and $g(x)$ be polynomials with $g(x) \neq 0$. Then there are unique polynomials $q(x)$ and $r(x)$ such that

$$ f(x) = q(x)\,g(x) + r(x), \qquad r(x) = 0 \ \text{ or } \ \deg r \lt \deg g. $$

We call $q(x)$ the quotient and $r(x)$ the remainder. Compare this with integers: $17 = 3 \cdot 5 + 2$, where the remainder $2$ is smaller than the divisor $5$. For polynomials, "smaller" means "lower degree".

Example 1: dividing by a linear polynomial

Let's divide $f(x) = 2x^3 - 3x^2 + 4x - 5$ by $g(x) = x - 2$.

Step 1. Divide the leading terms: $2x^3 / x = 2x^2$. Multiply $2x^2(x - 2) = 2x^3 - 4x^2$ and subtract.

Step 2. The new leading term is $x^2$, and $x^2 / x = x$. Multiply $x(x - 2) = x^2 - 2x$ and subtract.

Step 3. The new leading term is $6x$, and $6x / x = 6$. Multiply $6(x - 2) = 6x - 12$ and subtract.

Written out in columns:

$$ \begin{array}{rrrrl} 2x^3 & -\,3x^2 & +\,4x & -\,5 & \\ -(2x^3 & -\,4x^2) & & & \leftarrow 2x^2 \cdot (x-2) \\ \hline & x^2 & +\,4x & -\,5 & \\ & -(x^2 & -\,2x) & & \leftarrow x \cdot (x-2) \\ \hline & & 6x & -\,5 & \\ & & -(6x & -\,12) & \leftarrow 6 \cdot (x-2) \\ \hline & & & 7 & \end{array} $$

The remainder $7$ has degree $0 \lt 1 = \deg g$, so we stop. Therefore

$$ 2x^3 - 3x^2 + 4x - 5 = (x - 2)(2x^2 + x + 6) + 7. $$

A quick check: the remainder theorem

When dividing by $x - a$, the remainder is always $f(a)$. Plug $x = a$ into the division algorithm and the $q(x),g(x)$ term vanishes. Here:

$$ f(2) = 2 \cdot 8 - 3 \cdot 4 + 4 \cdot 2 - 5 = 16 - 12 + 8 - 5 = 7. \checkmark $$

A useful consequence: $x - a$ divides $f(x)$ exactly when $f(a) = 0$, that is, when $a$ is a root.

Example 2: dividing by a quadratic

Now divide $f(x) = x^4 + 2x^3 - x + 3$ by $g(x) = x^2 + 1$. Notice that $f$ has no $x^2$ term, so we write it as $0x^2$ to keep the columns aligned.

$$ \begin{array}{rrrrrl} x^4 & +\,2x^3 & +\,0x^2 & -\,x & +\,3 & \\ -(x^4 & & +\,x^2) & & & \leftarrow x^2 \cdot (x^2+1) \\ \hline & 2x^3 & -\,x^2 & -\,x & +\,3 & \\ & -(2x^3 & & +\,2x) & & \leftarrow 2x \cdot (x^2+1) \\ \hline & & -x^2 & -\,3x & +\,3 & \\ & & -(-x^2 & & -\,1) & \leftarrow (-1) \cdot (x^2+1) \\ \hline & & & -3x & +\,4 & \end{array} $$

The remainder $-3x + 4$ has degree $1 \lt 2$, so we're done:

$$ x^4 + 2x^3 - x + 3 = (x^2 + 1)(x^2 + 2x - 1) + (-3x + 4). $$

Check. Expanding the product:

$$ \begin{aligned} (x^2 + 1)(x^2 + 2x - 1) &= x^4 + 2x^3 - x^2 + x^2 + 2x - 1 \\ &= x^4 + 2x^3 + 2x - 1, \end{aligned} $$

and adding the remainder $-3x + 4$ gives back $x^4 + 2x^3 - x + 3$. ✓

Shortcut: synthetic division

When the divisor is $x - a$, you can skip the variables and work with coefficients only. For Example 1, write the coefficients $2, -3, 4, -5$ and use $a = 2$:

$$ \begin{array}{c|rrrr} 2 & 2 & -3 & 4 & -5 \\ & & 4 & 2 & 12 \\ \hline & 2 & 1 & 6 & \boxed{7} \end{array} $$

Bring down the first coefficient. Then repeatedly multiply by $a$, write the result under the next coefficient, and add. The bottom row gives the quotient's coefficients $2, 1, 6$, meaning $2x^2 + x + 6$, and the last entry is the remainder $7$. Same answer, a fraction of the writing.

Exercises

  1. Divide $x^3 - 6x^2 + 11x - 6$ by $x - 1$. What does the remainder tell you?
  2. Use synthetic division to find the remainder of $3x^4 - 2x^2 + x - 7$ divided by $x + 1$. (Hint: $x + 1 = x - (-1)$.)
  3. Divide $x^5 - 1$ by $x - 1$. Can you spot the pattern in the quotient?

Answers. (1) Quotient $x^2 - 5x + 6$, remainder $0$, so $x = 1$ is a root. (2) Remainder $-7$. (3) Quotient $x^4 + x^3 + x^2 + x + 1$, remainder $0$.