# Polynomial Long Division

## Technique

Let $\map {P_n} x$ be a polynomial in $x$ of degree $n$.

Let $\map {Q_m} x$ be a polynomial in $x$ of degree $m$ where $m \le n$.

Then $\map {P_n} x$ can be expressed in the form:

- $\map {P_n} x \equiv \map {Q_m} x \map {D_{n - m} } x + \map {R_k} x$

This article, or a section of it, needs explaining.what is $\equiv$ being used for here?You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

where:

- $\map {D_{n - m} } x$ is a polynomial in $x$ of degree $n - m$

- $\map {R_k} x$ is a polynomial in $x$ of degree $k$, where $k < m$, or may be null.

Hence we can define $\dfrac {\map {P_n} x} {\map {Q_m} x}$:

- $\dfrac {\map {P_n} x} {\map {Q_m} x} = \map {D_{n - m} } x + \dfrac {\map {R_k} x} {\map {Q_m} x}$

The polynomial $\map {R_k} x$ is called the **remainder**.

The procedure for working out what $\map {D_{n - m} } x$ and $\map {R_k} x$ are is called **(polynomial) long division**.

This article, or a section of it, needs explaining.Establish the precise versions of polynomial that are invoked via the links on this page.You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Explain}}` from the code. |

## Proof

Let $\ds \map {P_n} x = \sum_{j \mathop = 0}^n p_j x^j$.

Let $\ds \map {Q_m} x = \sum_{j \mathop = 0}^m q_j x^j$.

First calculate $\map {Q'_m} x = \map {Q_m} x \times \dfrac {p_n} {q_m} x^{n - m}$.

This gives:

\(\ds \map {Q'_m} x\) | \(=\) | \(\ds \sum_{j \mathop = 0}^m \frac {p_n q_j} {q_m} x^{n - m + j}\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds \sum_{j \mathop = n - m}^n \frac {p_n q_{j - n + m} } {q_m} x^j\) | ||||||||||||

\(\ds \) | \(=\) | \(\ds p_n x^n + \sum_{j \mathop = n - m}^{n - 1} \frac {p_n q_{j - n + m} } {q_m} x^j\) |

Then evaluate:

- $\map {P'_{n - 1} } x = \map {P_n} x - \map {Q'_m} x$

which (after some algebra) works out as:

- $\ds \map {P_n} x - \map {Q'_m} x = \sum_{j \mathop = n - m}^{n - 1} \frac {p_n q_{j - n + m} } {q_m} x^j + \sum_{j \mathop = 0}^{n - m - 1} p_j x^j$

So we see that $\map {P_n} x - \map {Q'_m} x$ is a polynomial in $x$ of degree $n - 1$.

Let $\dfrac {p_n} {q_m} = d_{n - m}$.

Hence we have:

- $\map {P_n} x = d_{n - m} x^{n - m} \map {Q_m} x + \map {P'_{n - 1} } x$

We can express $\map {P'_{n - 1} } x$ as:

- $\ds \map {P'_{n - 1} } x = \sum_{j \mathop = 0}^{n - 1} p'_j x^j$

Repeat the above by subtracting $\ds \frac {p'_{n - 1} } {q_m} x^{n - m - 1} \map {Q_m} x$ from $\map {P'_{n - 1} } x$, and letting $\dfrac {p'_{n - 1} } {q_m} = d_{n - m - 1}$.

Hence:

- $\map {P'_{n - 1} } x = d_{n - m - 1} x^{n - m - 1} \map {Q_m} x + \map {P''_{n - 2} } x$

The process can be repeated $n - m$ times.

It can be seen that after the last stage, we have:

- $\map {P_n} x = \map {D_{n - m} } x \map {Q_m} x + \map {R_k} x$

where:

- $\ds \map {D_{n - m} } x = \sum_{j \mathop = 0}^{n - m} d_j x^j$

- $\map {R_k} x$ is a polynomial of degree at most $m - 1$.

$\blacksquare$