MATH 415 Lecture 20

« previous | Tuesday, November 5, 2013 | next »

Division Algorithm for Polynomials

Given ring of polynomials $F[x]$ with $f,g\in F[x]$ , there exist $q(x),r(x)\in F[x]$ such that $f(x)=g(x)\,q(x)+r(x)$ and $\deg {r(x)}<\deg {g(x)}$ .

Factor Theorem

Corollary 23.3. $a\in F$ is a zero (or root) of $f(x)\in F[x]$ ^[1] if and only if $x-a$ is a factor of $f(x)$ in $F[x]$ . That is, there is a polynomial $q(x)\in F[x]$ such that $f(x)-(x-a)\,q(x)$ .

Proof. Let $g(x)=x-a$ . Then $\phi _{a}(x-a)=a-a=0$ .

Now there exist $q(x)$ and $r(x)$ . $\deg {r(x)}<\deg(x-a)=1$ , thus $\deg {r(x)}=0$ and $r(x)=C$ . Hence $f(x)=(x-a)\,q(x)+C$ .

Applying the evaluation homomorphism $\phi _{a}$ to both sides yields

${\begin{aligned}\phi _{a}(f(x))&=\phi _{a}((x-a)\,q(x)+C)\\0&=\phi _{a}((x-a)\,q(x))+C\\&=(a-a)\,q(a)+C\\&=0\,q(a)+C\\&=0+C\end{aligned}}$

Therefore $C=0$ , so $f(x)=(x-a)\,q(x)$

quod erat demonstrandum

Example

$p(x)=x^{4}+3x^{3}+2x+4\in \mathbb {Z} _{5}[x]$

$\pm 1$ are zeroes of $p(x)$ , and $p(x)$ factors into $(x-1)^{3}\,(x+1)$ , so

the zero $1$ has multiplicity of $3$ , and
the zero $-1$ has multiplicity of $1$ .

Factoring

Let $p(x)=a_{n}\,x^{n}+\dots +a_{0}$ for $a_{i}\in F$ with $a_{n}\neq 0$ .

Then if $p(x)$ can be factored into $a_{n}\,(x-a_{1})\,(x-a_{2})\,\dots \,(x-a_{n})$ , then there may be some $a_{i}$ 's that are not distinct. Therefore $p(x)=a_{n}\,(x-a_{i_{1}})^{m_{1}}\,(x-a_{i_{2}})^{m_{2}}\,\dots \,(x-a_{i_{k}})^{m_{k}}$ for $a_{i_{j}}\neq a_{i_{k}}$ if $i_{j}\neq i_{k}$ , where $m_{1},\ldots ,m_{k}$ are the multiplicities of the corresponding zero.

Corollary. A nonzero polynomial $f(x)\in F[x]$ of degree $n$ can have at most $n$ zeroes in a field $F$ .

Proof. Let $f(x)=a_{n}\,x^{n}+\dots +a_{1}\,x+a_{0}$ with $a_{n}\neq 0$ . Then $\deg {f(x)}=n$ . Let $a_{1}\in F$ be a zero of $f(x)$ . Then $f(x)=(x-a_{1})\,q_{1}(x)$ , with $\deg {q_{1}(x)}=n-1$ . For the basis, let $f(x)=a_{1}\,x+a_{0}$ be a polynomial of degree $1$ . Then $f(x)=a_{1}\left(x+{\frac {a_{0}}{a_{1}}}\right)$ implies that $f$ has at most one zero: $x=-{\frac {a_{0}}{a_{1}}}$ . The theorem holds by induction on $n$ .

quod erat demonstrandum

Corollary. If $G$ is a finite subgroup of the multiplicative group $\left\langle F^{*},\cdot \right\rangle$ of a field $F$ , then $G$ is cyclic. In particular, the multiplicative group of all non-zero elements of a finite field is cyclic.

By the Fundamental Theorem of Fininitely Generated Abelian Groups, $G$ is isomorphic to $\mathbb {Z} _{d_{1}}\times \mathbb {Z} _{d_{2}}\times \dots \times \mathbb {Z} _{d_{r}}$ , where $d_{i}={p_{i}}^{k_{i}}$ for prime $p$ . Let Failed to parse (unknown function "\lcm"): {\displaystyle m = \lcm{\left\{ d_i \right\}}} . Observe that $m\leq \prod _{i}d_{i}$ .

For any $a_{i}\in \mathbb {Z} _{d_{i}}$ , we have ${a_{i}}^{d_{i}}=1$ . Moreover, for $a\in G$ , we have $a^{m}=1$ . Hence every $a\in G$ is a zero of the polynomial $x^{m}-1\in F[x]$ , which has at most $m$ zeroes in $F$ .

However, all $a\in (F^{*}=G)$ are zeroes, and there are $\left|G\right|=\prod _{i}d_{i}$ zeroes. By the above observation, $m=\prod _{i}d_{i}$ .

"Forget about algebra and go to number theory for a moment."

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lcm{\left\{ {p_i}^{k_i} \right\}}} is of form $\prod _{i=1}^{r}{p_{i}}^{k_{i}}$ , where if $p_{i}=p_{j}$ , we just include $p_{i}^{\max {(k_{i},k_{j})}}$ .

Irreducible Polynomials

A nonconstant polynomial $f(x)\in F[x]$ is irreducible over $F$ (or is an irreducible polynomial in $F[x]$ ) if $f(x)$ cannot be expressed as a product $g(x)\,h(x)$ of two nonconstant polynomials.

Example

$x^{2}-2\in \mathbb {Q} [x]$ is irreducible in $\mathbb {Q} [x]$ (over $\mathbb {Q}$ ). Note $x^{2}-2=(x+{\sqrt {2}}(x-{\sqrt {2}})$ , but ${\sqrt {2}}\not \in \mathbb {Q}$ . Hence $x^{2}-2$ is reducible over $\mathbb {R}$ .

Theorem 23.10

Let $f(x)\in F[x]$ and let the degree of $f(x)$ be $2$ or $3$ . Then $f(x)$ is reducible over $F$ if and only if it has a zero in $F$ .

Proof. Assume $f(x)=g(x)\cdot h(x)$ , then $\deg {f}=\deg {g}+\deg {h}$ . Since $\deg {g},\deg {h}\geq 1$ , we have $\deg {g}=1$ and $\deg {h}=2$ or $\deg {g}=2$ and $\deg {h}=1$ . Without loss of generality, assume the latter case. Then $h(x)=a\,x+b$ implies $x=-{\frac {b}{a}}$ is a zero of $h$ and thus a zero of $f$ .

Conversely, assume that $a\in F$ is a zero of $f(x)$ . Then $f(x)$ is reducible into $f(x)=(x-a)\,g(x)$ , where $g(x)\in F[x]$ and $\deg {g}=2$ .

Example

$f(x)=x^{3}+3x+2\in \mathbb {Z} _{5}[x]$ is irreducible because it has no zeroes: $f(0)=2$ , $f(1)=1$ , $f(2)=1$ , $f(3)=3$ , and $f(4)=3$ .

Theorem 23.11

If $f(x)\in \mathbb {Z} [x]$ , then $f(x)$ factors into a product of two nonconstant polynomials of degrees $r$ and $s$ in $\mathbb {Q} [x]$ if and only if it has such a factorization with polynomials of the same degrees $r$ and $s$ in $\mathbb {Z} [x]$ .

In other words, take a polynomial $p(x)$ with integer coefficients. At the same time, $p(x)$ is a polynomial with rational coefficients. If $f(x)=g(x)\,h(x)$ with $\deg {g}=r\geq 1$ and $\deg {h}=s\geq 1$ , then $f(x)=g_{1}(x)\,h_{1}(x)$ for $g_{1}(x),h_{1}(x)\in \mathbb {Z} (x)$ , where $\deg {g_{1}}=r$ and $\deg {g_{2}}=s$ .