Division Algorithm (Polynomials)

theorempolynomials

Intuition

The division algorithm for polynomials has analogues in other rings.

Formal Statement

Suppose $p,s\in P(\mathbb{F})$ with $s\ne 0$, then $\exists !q,r\in P(\mathbb{F})$ such that,

$$p=sq+r\text{ and }\mathrm{deg}r<\mathrm{deg}s.$$

Proof

Assume $\mathrm{deg}p=n+\mathrm{deg}s=m$. If $n<m$, then $p=s\cdot 0+p$ works. Assume $n\ge m$. Then the list,

$$1,z,\dots ,z^{m-1},s,sz,\dots ,s{z}^{n-m}$$

is linearly independent in $P_n(\mathbb{F})$ and has length $n+1=\dim P_n(\mathbb{F})$. Thus the list is a basis. Since $p\in P_n(\mathbb{F})$, $\exists !a_0,\dots ,a_{m-1},b_0,\dots ,b_{n-m}$ such that $p=a_0+a_{1}z+\cdots +a_{m-1}{z}^{m-1}+b_{0}s+b_{1}sz+\cdots +b_{n-m}s{z}^{n-m}$. Therefore,

$$p=(a_0+\cdots +a_{m-1}{z}^{m-1})+s(b_0+\cdots +b_{n-m}{z}^{n-m}).\square$$

Corollaries