03 - Division Algorithm for Polynomials

Division Algorithm for Polynomials

Let $f(x),g(x)$ be two polynomials with $g(x)\ne 0$ then
There exists $q(x),r(x)\in \mathbf{F}[x]$ such that

$$f(x)=q(x)g(x)+r(x)\text{ and }\mathrm{deg}r(x)<\mathrm{deg}g(x)$$

Proof

If $\mathrm{deg}f(x)<\mathrm{deg}g(x)$ then $q(x)=0$ and $r(x)=f(x)$

Assume that $\mathrm{deg}f(x)\ge \mathrm{deg}g(x)$
Let

$$\begin{array}{rl}f(x)& =a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\\ g(x)& =b_k{x}^k+b_{k-1}{x}^{k-1}+\cdots +b_0(b_k\ne 0)\end{array}$$

Then

$$\mathrm{deg}\left(f(x)-\frac{a_n}{b_k}{x}^{n-k}g(x)\right)<n$$

By induction on $\mathrm{deg}f-\mathrm{deg}g$, then there exists $s(x)$ and $t(x)$ such that

$$f(x)-\frac{a_n}{b_k}{x}^{n-k}g(x)=s(x)g(x)+t(x)\text{ and }\mathrm{deg}g(x)>\mathrm{deg}t(x)$$

Hence put $q(x)=\frac{a_n}{b_k}{x}^{n-k}+s(x)$ and $r(x)=t(x)$