Euclidean Polynomial Division

Theorem: Given two polynomials $f(x)$ and $g(x)$, with $g(x) \neq 0$, there exists unique polynomials $q(x)$ and $r(x)$ such that $f(x)=q(x)g(x)+r(x)$ with $deg\big(r

(x)\big) < deg\big(g(x)\big)$.

Proof:

Existence:
Let $\quad f(x) = a_{n}x^n + a_{n-1}x^{n-1} + \cdots + a_{0}x^0$
and $\quad g(x) = b_{m}x^m + b_{m-1}x^{m-1} + \cdots + b_{0}x^0$

If $\quad n<m$
Then take $q(x) = 0$ and $r(x) = f(x)$
Hence $f(x)=q(x)g(x)+r(x)$ with $deg\big(r(x)\big) = n < deg\big(g(x)\big)$.

If $\quad n\geq m$
Let $\;\;q_{1}(x) = \dfrac{a_{n}}{b_{m}}x^{n-m}$

Then $r_{1}(x) = f(x) - q_{1}(x)g(x)$

Now, if $deg\big(r_{1}(x)\big)< deg\big(g(x)\big)$, then $r(x) = r_{1}(x)$ and $q(x) = q_{1}(x)$. Otherwise:

$\qquad\quad r_{1}(x) = f(x) - q_{1}(x)g(x) = c_{n-1}x^{n-1} + c_{n-2}x^{n-2} + \cdots + c_{0}x^0$

Take $\quad q_{2}(x) = q_{1}(x) + \dfrac{c_{n-1}}{b_{m}}x^{n-m-1}$

This procedure can be continued till degree of $f(x) - q_{k}(x)g(x) < m$. This value of $q_{k}(x) = q(x)$ and corresponding $r_{k}(x) = f(x) - q_{1}(x)g(x) = r(x)$ with $deg\big(r(x)\big) < n = deg\big(g(x)\big)$.

Uniqueness:
If possible, let there exist two sets of polynomials $q_{1}(x)$, $r_{1}(x)$ and $q_{2}(x)$, $r_{2}(x)$ $\left(q_{1}(x)\neq q_{2}(x)\text{ and } r_{1}(x)\neq r_{2}(x)\right)$ such that $f(x)=q_{1}(x)g(x)+r_{1}(x)$ and $f(x)=q_{2}(x)g(x)+r_{2}(x)$ with $deg\big(r_{1}(x)\big)< deg\big(g(x)\big)$ and $deg\big(r_{2}(x)\big)< deg\big(g(x)\big)$.

$\therefore\quad\;\; f(x)=q_{1}(x)g(x)+r_{1}(x) = q_{2}(x)g(x)+r_{2}(x)$

$\Rightarrow\quad\;\; \left(q_{1}(x) - q_{2}(x)\right)g(x) + \left(r_{1}(x)-r_{2}(x)\right) = 0$

$\Rightarrow\quad\;\; \left(q_{1}(x) - q_{2}(x)\right)g(x) = \left(r_{1}(x)-r_{2}(x)\right)$

Since, $deg\big(g(x)\big) = n$, therefore, degree of LHS $>n$. But the degree of RHS$<n$. Hence there is a contradiction. Therefore $q(x)$ and $r(x)$ are unique.


Recommended:
Polynomial Remainder Theorem
Factor Theorem
Factor representation of polynomials