synthetic division

Let $a, b, q, r$ be polynomials of the form

p = \sum_{k = 0}^{σ_{p}} p_{k} x^{k}

such that $σ_{p}$ is the degree of $p$ .
We define that if $k < 0$ or $k > σ_{p}$ , then $p_{k} = 0$ .

Specifically, let $σ_{a} = n$ , and $σ_{b} = m$ , and $σ_{q} = (n - m)$ , and $σ_{r} = (m - 1)$ .

Then synthetic division of $a$ by $b$ can be expressed as $a = b q + r$ , and calculated using the following algorithm:

Arrange the $n$ coefficients $a_{i}$ of $a$ by decreasing order in the top row.
Arrange the $m$ coefficients $b_{j}$ of $b$ by increasing order in the leftmost column.
Separate the final coefficient $b_{m}$ with a horizontal line and a "spacer" row.
Fill the empty spaces of the first column (the column corresponding to coefficient $a_{n}$ ) up to the horizontal line with $0$ 's.
Record the sum of the first column (simply $a_{n}$ ) in the first column of the $\sum col$ "spacer" row.
Divide the sum by $b_{m}$ , and record that value as $q_{n - m}$ in the first column of the $\div b_{m}$ "quotient" row.
1. $q_{n - m}$ is notated such because by our definition of $q$ , it is thus the coefficient of the highest degree term in $q$ , since $q$ has order $(n - m)$ .
Place the value of $q_{n - m}$ in a diagonal, from the open bottom left position towards the top right, multiplying in each $j^{t h}$ row the value of the coefficient $- b_{j}$ to the value of $q_{n - m}$ .
Fill above this diagonal with $0$ 's.
Record the sum of the fully populated second column in the $\sum col$ "spacer" row (denoted here $*$ for convenience)
Divide the sum by $b_{m}$ , and record that value as $q_{n - m - 1}$ in the second column of the $\div b_{m}$ "quotient" row.
1. This index indicates the coefficient of the second highest degree term.
Place the value of $q_{n - m - 1}$ in a diagonal, from the open bottom left position towards the top right, multiplying in each $j^{t h}$ row the value of the term $- b_{j}$ to the value of $q_{n - m - 1}$ .
Sum the next column, and repeat until the value $q_{0}$ is calculated and $(- b_{0}) (q_{0})$ is placed below $a_{0}$ . Fill the rest of the table with $0$ 's, and the sum of each remaining column is the remainder after division, as following the table below:

\begin{array}{ccccccccccccccc} a_{n} & a_{n - 1} & a_{n - 2} & a_{n - 3} & \dots & a_{m + 2} & a_{m + 1} & a_{m} & a_{m - 1} & a_{m - 2} & a_{m - 3} & \dots & a_{2} & a_{1} & a_{0} \\ - b_{0} & 0 & 0 & 0 & 0 & \dots & (- b_{0}) (q_{m + 2}) & (- b_{0}) (q_{m + 1}) & (- b_{0}) (q_{m}) & (- b_{0}) (q_{m - 1}) & (- b_{0}) (q_{m - 2}) & (- b_{0}) (q_{m - 3}) & \dots & (- b_{0}) (q_{2}) & (- b_{0}) (q_{1}) & (- b_{0}) (q_{0}) \\ - b_{1} & 0 & 0 & 0 & 0 & \dots & (- b_{1}) (q_{m + 1}) & (- b_{1}) (q_{m}) & (- b_{1}) (q_{m - 1}) & (- b_{1}) (q_{m - 2}) & (- b_{1}) (q_{m - 3}) & (- b_{1}) (q_{m - 4}) & \dots & (- b_{1}) (q_{1}) & (- b_{1}) (q_{0}) & 0 \\ - b_{2} & 0 & 0 & 0 & 0 & \dots & (- b_{2}) (q_{m}) & (- b_{2}) (q_{m - 1}) & (- b_{2}) (q_{m - 2}) & (- b_{2}) (q_{m - 3}) & (- b_{2}) (q_{m - 4}) & (- b_{2}) (q_{m - 5}) & \dots & (- b_{2}) (q_{0}) & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ - b_{m - 3} & 0 & 0 & 0 & (- b_{m - 3}) (q_{n - m}) & \dots & (- b_{m - 3}) (q_{5}) & (- b_{m - 3}) (q_{4}) & (- b_{m - 3}) (q_{3}) & (- b_{m - 3}) (q_{2}) & (- b_{m - 3}) (q_{1}) & (- b_{m - 3}) (q_{0}) & \dots & 0 & 0 & 0 \\ - b_{m - 2} & 0 & 0 & (- b_{m - 2}) (q_{n - m}) & (- b_{m - 2}) (q_{n - m - 1}) & \dots & (- b_{m - 2}) (q_{4}) & (- b_{m - 2}) (q_{3}) & (- b_{m - 2}) (q_{2}) & (- b_{m - 2}) (q_{1}) & (- b_{m - 2}) (q_{0}) & 0 & \dots & 0 & 0 & 0 \\ - b_{m - 1} & 0 & (- b_{m - 1}) (q_{n - m}) & (- b_{m - 1}) (q_{n - m - 1}) & (- b_{m - 1}) (q_{n - m - 2}) & \dots & (- b_{m - 1}) (q_{3}) & (- b_{m - 1}) (q_{2}) & (- b_{m - 1}) (q_{1}) & (- b_{m - 1}) (q_{0}) & 0 & 0 & \dots & 0 & 0 & 0 \\ \sum col & a_{n} & * & * & * & \dots & * & * & * & r_{m - 1} & r_{m - 2} & r_{m - 3} & \dots & r_{2} & r_{1} & r_{0} \\ \div b_{m} & q_{n - m} & q_{n - m - 1} & q_{n - m - 2} & q_{n - m - 3} & \dots & q_{2} & q_{1} & q_{0} \end{array}

The algorithm determines that the polynomial $a$ can be written $a = b q + r$ , where $q = \sum_{k = 0}^{n - m} q_{k} x^{k}$ is the quotient and $r = \sum_{k = 0}^{m - 1} r_{k} x^{k}$ is the remainder after division of $a$ by $b$ .

Note we defined that for polynomial coefficient $p_{k}$ of $p$ : if $k < 0$ or $k > σ_{p}$ , then $p_{k} = 0$ . Depending on the actual values of $n$ and $m$ , some coefficients in $q$ listed in the table may evaluate to $0$ .

Examples (Abstract)

Example 1

Let $σ_{a} = 7, σ_{b} = 3$ .
Then $σ_{q} = (7 - 3) = 4$

\begin{array}{ccccccccc} a_{7} & a_{6} & a_{5} & a_{4} & a_{3} & a_{2} & a_{1} & a_{0} \\ - b_{0} & 0 & 0 & 0 & (- b_{0}) (q_{4}) & (- b_{0}) (q_{3}) & (- b_{0}) (q_{2}) & (- b_{0}) (q_{1}) & (- b_{0}) (q_{0}) \\ - b_{1} & 0 & 0 & (- b_{1}) (q_{4}) & (- b_{1}) (q_{3}) & (- b_{1}) (q_{2}) & (- b_{1}) (q_{1}) & (- b_{1}) (q_{0}) & 0 \\ - b_{2} & 0 & (- b_{2}) (q_{4}) & (- b_{2}) (q_{3}) & (- b_{2}) (q_{2}) & (- b_{2}) (q_{1}) & (- b_{2}) (q_{0}) & 0 & 0 \\ \sum col & a_{7} & * & * & * & * & r_{2} & r_{1} & r_{0} \\ \div b_{3} & q_{4} & q_{3} & q_{2} & q_{1} & q_{0} \end{array}

$k$	$q_{k}$	$a_{k}$
$k = 7$		$a_{7} = b_{3} q_{4}$
$k = 6$		$a_{6} = b_{2} q_{4} + b_{3} q_{3}$
$k = 5$		$a_{5} = b_{1} q_{4} + b_{2} q_{3} + b_{3} q_{2}$
$k = 4$	$q_{4} = \frac{1}{b_{3}} (a_{7})$	$a_{4} = b_{0} q_{4} + b_{1} q_{3} + b_{2} q_{2} + b_{3} q_{1}$
$k = 3$	$q_{3} = \frac{1}{b_{3}} (a_{6} + (- b_{2}) (q_{4}))$	$a_{3} = b_{0} q_{3} + b_{1} q_{2} + b_{2} q_{1} + b_{3} q_{0}$
$k = 2$	$q_{2} = \frac{1}{b_{3}} (a_{5} + (- b_{2}) (q_{3}) + (- b_{1}) (q_{4}))$	$a_{2} = r_{2} + b_{0} q_{2} + b_{1} q_{1} + b_{2} q_{0}$
$k = 1$	$q_{1} = \frac{1}{b_{3}} (a_{4} + (- b_{2}) (q_{2}) + (- b_{1}) (q_{3}) + (- b_{0}) (q_{4}))$	$a_{1} = r_{1} + b_{0} q_{1} + b_{1} q_{0}$
$k = 0$	$q_{0} = \frac{1}{b_{3}} (a_{3} + (- b_{2}) (q_{1}) + (- b_{1}) (q_{2}) + (- b_{0}) (q_{3}))$	$a_{0} = r_{0} + b_{0} q_{0}$

Example 2

Let $σ_{a} = 8, σ_{b} = 4$ .
Then $σ_{q} = (8 - 4) = 4$

\begin{array}{cccccccccc} a_{8} & a_{7} & a_{6} & a_{5} & a_{4} & a_{3} & a_{2} & a_{1} & a_{0} \\ - b_{0} & 0 & 0 & 0 & 0 & (- b_{0}) (q_{4}) & (- b_{0}) (q_{3}) & (- b_{0}) (q_{2}) & (- b_{0}) (q_{1}) & (- b_{0}) (q_{0}) \\ - b_{1} & 0 & 0 & 0 & (- b_{1}) (q_{4}) & (- b_{1}) (q_{3}) & (- b_{1}) (q_{2}) & (- b_{1}) (q_{1}) & (- b_{1}) (q_{0}) & 0 \\ - b_{2} & 0 & 0 & (- b_{2}) (q_{4}) & (- b_{2}) (q_{3}) & (- b_{2}) (q_{2}) & (- b_{2}) (q_{1}) & (- b_{2}) (q_{0}) & 0 & 0 \\ - b_{3} & 0 & (- b_{3}) (q_{4}) & (- b_{3}) (q_{3}) & (- b_{3}) (q_{2}) & (- b_{3}) (q_{1}) & (- b_{3}) (q_{0}) & 0 & 0 & 0 \\ \sum col & a_{8} & * & * & * & * & r_{3} & r_{2} & r_{1} & r_{0} \\ \div b_{4} & q_{4} & q_{3} & q_{2} & q_{1} & q_{0} \end{array}

$k$	$a_{k}$
$k = 8$	$a_{8} = b_{4} q_{4}$
$k = 7$	$a_{7} = b_{3} q_{4} + b_{4} q_{3}$
$k = 6$	$a_{6} = b_{2} q_{4} + b_{3} q_{3} + b_{4} q_{2}$
$k = 5$	$a_{5} = b_{1} q_{4} + b_{2} q_{3} + b_{3} q_{2} + b_{4} q_{1}$
$k = 4$	$a_{4} = b_{0} q_{4} + b_{1} q_{3} + b_{2} q_{2} + b_{3} q_{1} + b_{4} q_{0}$
$k = 3$	$a_{3} = r_{3} + b_{0} q_{3} + b_{1} q_{2} + b_{2} q_{1} + b_{3} q_{0}$
$k = 2$	$a_{2} = r_{2} + b_{0} q_{2} + b_{1} q_{1} + b_{2} q_{0}$
$k = 1$	$a_{1} = r_{1} + b_{0} q_{1} + b_{1} q_{0}$
$k = 0$	$a_{0} = r_{0} + q_{0} b_{0}$

Examples (Concrete)

#WIP

Proof

By definition, $p_{k}$ is the coefficient of $x^{k}$ in $p$ .
Subject to the constraint "if $k < 0$ or $k > σ_{p}$ , then $p_{k} = 0$ ",
if $a = b q + r$ , then

a_{k} = r_{k} + \sum_{i = 0}^{m} b_{i} q_{k - i}

since $b_{i}$ is the coefficient for $x^{i}$ , $q_{k - i}$ is the coefficient for $x^{k - i}$ , and their product $b_{i} q_{k - i}$ is the coefficient for $x^{i} x^{k - i} = x^{k - i + i} = x^{k}$ . It thus can be linearly combined with the coefficient $r_{k}$ of $x^{k}$ in $r$ to construct a single monomial of order $k$ .

Since $σ_{r} = (m - 1)$ ,
since we defined that for polynomial coefficient $p_{k}$ of $p$ : if $k < 0$ or $k > σ_{p}$ , then $p_{k} = 0$ ,
an equivalent expression for $a_{k}$ is

a_{k} = {\begin{cases} \sum_{i = 0}^{m} b_{i} q_{k - i}, & k \geq m \\ r_{k} + \sum_{i = 0}^{m} b_{i} q_{k - i}, & k < m \end{cases}

with the understanding that some coefficients of $q$ will evaluate to $0$ .

It suffices to show that the synthetic division algorithm produces coefficients which satisfy this relation, with respect to a chosen $a$ and $b$ .

The synthetic division algorithm produces quotient coefficients

q_{k} = \frac{1}{b_{m}} (a_{m + k} + \sum_{i = 0}^{m - 1} (- b_{i}) (q_{m + k - i}))

when $0 \leq k \leq (n - m)$ , allowing that indices corresponding to non-existent coefficients will evaluate to $0$ .

Rewriting for $a$ ,

\begin{aligned} a_{m + k} & = b_{m} q_{k} + \sum_{i = 0}^{m - 1} b_{i} q_{m + k - i} \\ a_{k} & = \sum_{i = 0}^{m} b_{i} q_{k - i} \end{aligned}

for $m \leq k \leq n$ .

Additionally, the synthetic division algorithm produces remainder coefficients

r_{k} = a_{k} + \sum_{i = 0}^{k} (- b_{i}) (q_{k - i})

for $0 \leq k \leq (m - 1)$ .

Rewriting for $a$ ,

a_{k} = r_{k} + \sum_{i = 0}^{k} b_{i} q_{k - i}

for $0 \leq k \leq (m - 1)$ .

Therefore, we have

a_{k} = {\begin{cases} \sum_{i = 0}^{m} b_{i} q_{k - i}, & k \geq m \\ r_{k} + \sum_{i = 0}^{m} b_{i} q_{k - i}, & k < m \end{cases}

and the algorithm is verified.