06 - Polynomials

Factor Theorem corollary

For all $f(x)\in \mathbf{F}[x]$ and $a\in \mathbf{F}$ then

$$f(a)=0⟹(x-a)\mid f(x)$$

Proof

By Division Algorithm for Polynomials then there exists $q(x),r(x)$ such that

$$f(x)=q(x)(x-a)+r(x)$$

As $\mathrm{deg}r(x)<1$ then $r(x)$ is a constant

Evaluating at $a$ then

$$f(a)=0=q(a)(a-a)+r=r$$

Hence $r=0$ so $(x-a)\mid f(x)$

Maximum Roots of a Polynomial

Assume $f\ne 0$

If $\mathrm{deg}f\le n$ then $f$ has at most $n$ roots

Monic Polynomial

Coefficient of highest power of $x$ of non-zero polynomial $f(x)$ is $1$

Bezout's Identity for Polynomials

Let $a,b\in \mathbf{F}[x]$ be two non-zero polynomials

Let $c(x)$ be a monic polynomial of highest degree that divides both $a(x)$ and $b(x)$
So $c(x)=\gcd (a,b)$

Then there exists $s,t\in \mathbf{F}[x]$ such that

$$a(x)s(x)+b(x)t(x)=c(x)$$

Proof

If $c\ne 1$ then divide both $a,b$ by $c$
WLOG assume that $\mathrm{deg}a>\mathrm{deg}b$ and $gcd(a,b)=1$

Doing induction on $\mathrm{deg}(a)+\mathrm{deg}(b)$

By the Division Algorithm for Polynomials then there exist $q,r\in \mathbf{F}[x]$ such that

$$a=qb+r\text{ with }\mathrm{deg}b>\mathrm{deg}r$$

Then $\mathrm{deg}(a)+\mathrm{deg}(b)>\mathrm{deg}(b)+\mathrm{deg}(r)$ and $\gcd (b,r)=1$
If $r=0$ then $b(x)=\lambda$ since $\gcd (a,b)=1$ hence

$$a(x)+b(x)\left(\frac{1}{\lambda }\right)(1-a(x))=1$$

Assume that $r\ne 0$ so by induction hypothesis, there exists $s^{\prime },t^{\prime }\in \mathbf{F}[x]$ such that

$$b{s}^{\prime }+r{t}^{\prime }=1$$

Hence

$$b{s}^{\prime }+(a-qb)t^{\prime }=1\text{ and }a{t}^{\prime }+b(s^{\prime }-q{t}^{\prime })=1$$

So then let $t = t'$ and $s = s' - qt'$