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 $\mathrm{deg}r(x)<\mathrm{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 ${\varphi }_a(x-a)=a-a=0$.

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

Applying the evaluation homomorphism ${\varphi }_a$ to both sides yields

$\begin{array}{rl}{\varphi }_a(f(x))& ={\varphi }_a((x-a)q(x)+C)\\ 0& ={\varphi }_a((x-a)q(x))+C\\ & =(a-a)q(a)+C\\ & =0q(a)+C\\ & =0+C\end{array}$

Therefore

$C=0$

, so

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

quod erat demonstrandum

Example

$p(x)=x^4+3x^3+2x+4\in {\mathbb{\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\ne 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}\ne a_{i_k}$ if $i_j\ne i_k$, where $m_1,\dots ,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\ne 0$

. Then

$\mathrm{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

$\mathrm{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(x+\frac{a_0}{a_1})$

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 $⟨F^{*},\cdot ⟩$ 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{\mathbb{Z}}}_{d_1}\times {\mathbb{\mathbb{Z}}}_{d_2}\times \dots \times {\mathbb{\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\le \prod _i{d}_i$.

For any $a_i\in {\mathbb{\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{\mathbb{Q}}[x]$ is irreducible in $\mathbb{\mathbb{Q}}[x]$ (over $\mathbb{\mathbb{Q}}$). Note $x^2-2=(x+\sqrt{2}(x-\sqrt{2})$, but $\sqrt{2}\in ̸\mathbb{\mathbb{Q}}$. Hence $x^2-2$ is reducible over $\mathbb{ℝ}$.

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 $\mathrm{deg}f=\mathrm{deg}g+\mathrm{deg}h$. Since $\mathrm{deg}g,\mathrm{deg}h\ge 1$, we have $\mathrm{deg}g=1$ and $\mathrm{deg}h=2$ or $\mathrm{deg}g=2$ and $\mathrm{deg}h=1$. Without loss of generality, assume the latter case. Then $h(x)=ax+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 $\mathrm{deg}g=2$.

Example

$f(x)=x^3+3x+2\in {\mathbb{\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{\mathbb{Z}}[x]$, then $f(x)$ factors into a product of two nonconstant polynomials of degrees $r$ and $s$ in $\mathbb{\mathbb{Q}}[x]$ if and only if it has such a factorization with polynomials of the same degrees $r$ and $s$ in $\mathbb{\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 $\mathrm{deg}g=r\ge 1$ and $\mathrm{deg}h=s\ge 1$, then $f(x)=g_1(x)h_1(x)$ for $g_1(x),h_1(x)\in \mathbb{\mathbb{Z}}(x)$, where $\mathrm{deg}{g}_1=r$ and $\mathrm{deg}{g}_2=s$.

Extra Office Hours

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