Division Theorem for Polynomial Forms over Field

From ProofWiki
Jump to: navigation, search

Theorem

Let $\struct {F, +, \circ}$ be a field whose zero is $0_F$ and whose unity is $1_F$.

Let $X$ be transcendental over $F$.

Let $F \sqbrk X$ be the ring of polynomials in $X$ over $F$.

Let $d$ be an element of $F \sqbrk X$ of degree $n \ge 1$.


Then $\forall f \in F \sqbrk X: \exists q, r \in F \sqbrk X: f = q \circ d + r$ such that either:

$(1): \quad r = 0_F$

or:

$(2): \quad r \ne 0_F$ and $r$ has degree that is less than $n$.


Proof 1

From the equation $0_F = 0_F \circ d + 0_F$, the theorem is true for the trivial case $f = 0_F$.

So, if there is a counterexample to be found, it will have a degree.


Aiming for a contradiction, suppose there exists at least one counterexample.

By a version of the Well-Ordering Principle, we can assign a number $m$ to the lowest degree possessed by any counterexample.

So, let $f$ denote a counterexample which has that minimum degree $m$.


If $m < n$, the equation $f = 0_F \circ d + f$ would show that $f$ was not a counterexample.

Therefore $m \ge n$.


Suppose $d \divides f$ in $F \sqbrk X$.

Then:

$\exists q \in F \sqbrk X: f = q \circ d + 0_F$

and $f$ would not be a counterexample.

So $d \nmid f$ in $F \sqbrk X$.


So, suppose that:

\(\displaystyle f\) \(=\) \(\displaystyle \sum_{k \mathop = 0}^m {a_k \circ X^k}\)
\(\displaystyle d\) \(=\) \(\displaystyle \sum_{k \mathop = 0}^n {b_k \circ X^k}\)
\(\displaystyle m\) \(\ge\) \(\displaystyle n\)


We can create the polynomial $\paren {a_m \circ b_n^{-1} \circ X^{m - n} } \circ d$ which has the same degree and leading coefficient as $f$.

Thus $f_1 = f - \paren {a_m \circ b_n^{-1} \circ X^{m - n} } \circ d$ is a polynomial of degree less than $m$.

Since $d \nmid f$, $f_1$ is a non-zero polynomial.


There is no counterexample of degree less than $m$.

Therefore:

$f_1 = q_1 \circ d + r$

for some $q_1, r \in F \sqbrk X$, where either:

$r = 0_F$

or:

$r$ is non-zero with degree strictly less than $n$.

Hence:

\(\displaystyle f\) \(=\) \(\displaystyle f_1 + \paren {a_m \circ b_n^{-1} \circ X^{m - n} } \circ d\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {q_1 + a_m \circ b_n^{-1} \circ X^{m - n} } \circ d + r\)

Thus $f$ is not a counterexample.

From this contradiction follows the result.

$\blacksquare$


Proof 2

Suppose $\map \deg f < \map \deg d$.

Then we take $\map q X = 0$ and $\map r X = \map a X$ and the result holds.


Otherwise, $\map \deg f \ge \map \deg d$.

Let:

$\map f X = a_0 + a_1 X + a_2 x^2 + \cdots + a_m X^m$
$\map d X = b_0 + b_1 X + b_2 x^2 + \cdots + b_n X^n$

We can subtract from $f$ a suitable multiple of $d$ so as to eliminate the highest term in $f$:

$\map f X - \map d X \cdot \dfrac {a_m} {b_n} x^{m - n} = \map p X$

where $\map p X$ is some polynomial whose degree is less than that of $f$.

If $\map p X$ still has degree higher than that of $d$, we do the same thing again.

Eventually we reach:

$\map f X - \map d X \cdot \paren {\dfrac {a_m} {b_n} x^{m - n} + \dotsb} = \map r X$

where either $r = 0_F$ or $r$ has degree that is less than $n$.


This approach can be formalised using the Principle of Complete Induction.

$\blacksquare$


Proof 3

Proof by induction:

For all $n \in \N_{> 0}$, let $P \left({n}\right)$ be the proposition:

$\forall f \in F \left[{X}\right]: \exists q, r \in F \left[{X}\right]: f = q \circ d + r$ provided that $\deg \left({f}\right) < n$


$P \left({0}\right)$ is the statement that $q$ and $r$ exist when $f = 0$.

This is shown trivially to be true by taking $q = r = 0$.


Basis for the Induction

$P \left({0}\right)$ is the statement that $q$ and $r$ exist when $f = 0$.

This is shown trivially to be true by taking $q = r = 0$.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 0$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

$\forall f \in F \left[{X}\right]: \exists q, r \in F \left[{X}\right]: f = q \circ d + r$ provided that $\deg \left({f}\right) < k$


Then we need to show:

$\forall f \in F \left[{X}\right]: \exists q, r \in F \left[{X}\right]: f = q \circ d + r$ provided that $\deg \left({f}\right) < k + 1$


Induction Step

This is our induction step:

Let $f$ be such that $\deg \left({f}\right) = n$.

Let:

$\displaystyle f = a_0 + a_1 \circ x + a_2 \circ x^2 + \cdots + a_n \circ x^n$ where $a_n \ne 0$

Let:

$\displaystyle d = b_0 + b_1 \circ x + b_2 \circ x^2 + \cdots + b_j \circ x^j$ where $b_j \ne 0$

If $n < l$ then take $q = 0, r = f$.

If $n \ge l$, consider:

$c := f - a_n b_j^{-1} x^{n-j} d$

This has been carefully arranged so that the coefficient of $x^n$ in $c$ is zero.

Thus $\deg \left({c}\right) < n$.

Therefore, by the induction hypothesis:

$c = d q_0 + r$

where $\deg \left({r}\right) < \deg \left({d}\right)$.

Therefore:

$f = d \left({q_0 + a_n b_j^{-1} x^{n-j}}\right) + r$
\(\displaystyle f\) \(=\) \(\displaystyle d \left({q_0 + a_n b_j^{-1} x^{n-j} }\right) + r\)
\(\displaystyle \) \(=\) \(\displaystyle d q + r\) where $\deg \left({r}\right) < \deg \left({d}\right)$ and $q = q_0 + a_n b_j^{-1} x^{n-j}$

Thus the existence of $q$ and $r$ have been established.


As for uniqueness, assume:

$d q + r = d q' + r'$

with $\deg \left({r}\right) < \deg \left({d}\right), \deg \left({r'}\right) < \deg \left({d}\right)$

Then:

$d \left({q - q'}\right) = r' - r$

By Degree of Sum of Polynomials:

$\deg \left({r' - r}\right) \le \max \left\{{\deg \left({r'}\right), \deg \left({r}\right)}\right\} < \deg \left({d}\right)$

and by Degree of Product of Polynomials over Integral Domain:

$\deg \left({d \left({q - q'}\right)}\right) = \deg \left({d}\right) \deg \left({d}\right) + \deg \left({q - q'}\right)$

That is:

$\deg \left({d}\right) < \deg \left({d}\right) + \deg \left({q - q'}\right)$

and the only way for that to happen is for:

$\deg \left({q - q'}\right) = - \infty$

that is, for $q - q'$ to be the null polynomial.

That is, $q - q' = 0_F$ and by a similar argument $r' - r = 0_F$, demonstrating the uniqueness of $q$ and $r$.

So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall f \in F \left[{X}\right]: \exists q, r \in F \left[{X}\right]: f = q \circ d + r$ such that either:
$(1): \quad r = 0_F$
or:
$(2): \quad r \ne 0_F$ and $r$ has degree that is less than $n$.

$\blacksquare$