Polynomial Long Division

From ProofWiki
Jump to navigation Jump to search

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$



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.



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$