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]$ 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 (unknown function "\lcm"): {\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 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 x^2 - 2} is reducible over 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 \mathbb{R}} .

Theorem 23.10

Let 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 f(x) \in F[x]} and let the degree of 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 f(x)} be 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 2} or 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 3} . Then 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 f(x)} is reducible over 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 F} if and only if it has a zero in $F$.

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

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

Example

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 f(x) = x^3 + 3x + 2 \in \mathbb{Z}_5 [x]} is irreducible because it has no zeroes: 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 f(0) = 2} , 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 f(1) = 1} , 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 f(2) = 1} , 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 f(3) = 3} , and 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 f(4) = 3} .

Theorem 23.11

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

In other words, take a polynomial 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 p(x)} with integer coefficients. At the same time, 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 p(x)} is a polynomial with rational coefficients. If 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 f(x) = g(x) \, h(x)} with 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 \deg{g} = r \ge 1} and 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 \deg{h} = s \ge 1} , then 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 f(x) = g_1(x) \, h_1(x)} for 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 g_1(x), h_1(x) \in \mathbb{Z}(x)} , where 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 \deg{g_1} = r} and 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 \deg{g_2} = s} .

Extra Office Hours

• Thursday, 13:10–14:10
• Monday, 14:00–15:00