The division algorithm

Let $f(x)$ and $g(x)$ be polynomials in $F[x]$ . We say that $g(x)$ divides $f(x)$ , denoted $g(x)\vert f(x)$ , if there is a polynomial $h(x)$ in $F[x]$ such that $f(x)=g(x)h(x)$ . In this case, we call $g(x),h(x)$ factors of $f(x)$ .

To determine if one polynomial divides another, one use the division algorithm for polynomials. The algorithm below is the analog of the division algorithm for the integers which was discussed in the previous chapter.

Lemma 2.2.5 (Division algorithm, special case)   Let $F$ be $\mathbb{C}$ or $\mathbb{Z}/n\mathbb{Z}$ . If $p(x)$ is a polynomial in $F[x]$ and $c\in F$ then then there is a polynomial $q(x)$ of degree deg$(p)-1$ in $F[x]$ (depending on $p(x)$ and on $c$ ) such that

$$p(x)=(x-c)q(x)+p(c).$$

proof: Suppose $p(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n$ . Note that

$$\begin{array}{c} p(x)-p(c)\\ =(a_0+a_1x+...+a_{n-1}x^{n-1}+... ...(a_1+a_2(x+c)+...+a_n\sum_{j=0}^{n-1}x^{n-1-j}c^j). \end{array}$$

$\Box$

Example 2.2.6   If $F={\mathbb{F}}_p$ then for any non-zero $a\in F$ , we have $a^p=a$ by Fermat's little theorem. Moreover, we have

$$(x+a)^p=x^p+a^p=x^p+a,$$

since $p$ divides all the binomial coefficients in the expansion of $(x+y)^p$ except those at the ``ends'' (see Example 1.5.1).

Theorem 2.2.7   Let $F$ be a field and $p\in F[x]$ be a polynomial of degree $n>0$ . Then there are at most $n$ roots of $p(x)=0$ in $F$ , counted according to multiplicity.

proof: The proof is by mathematical induction.

Induction hypothesis: Any polynomial $f\in F[x]$ is degree $k>0$ has at most $k$ roots.

Case $n=1$ : If $p(x)=a_1x+a_0$ is of degree 1 then (since $F$ is a field) $r=-a_0/a_1$ is a root. This proves the theorem in this case.

Case $n>1$ : Assume the induction hypothesis holds for all $k<n$ . If $p(x)$ is a polynomial of degree $n$ then either $p(x)$ has no root (and we are done) or there is a $c\in F$ such that $p(c)=0$ . By the division algorithm, $p(x)=(x-c)q(x)$ , where $q(x)$ is a polynomial of degree $n-1$ . By the induction hypothesis, $q(x)$ has at most $n-1$ roots, so $p(x)$ has at most $n$ roots. $\Box$

Example 2.2.8   Let $p(x)=x^{p-1}-1$ . By Fermat's little theorem, the numbers $1,2,...,p-1$ are distinct roots of $p(x)$ . By the above theorem, there can be no others. By the division algorithm, we have

$$x^{p-1}-1= (x-1)...(x-p+1).$$ (2.1)

Plugging $x=0$ into (2.1), implies the following result.

Corollary 2.2.9 (Wilson's theorem)   $(p-1)!\equiv -1({\rm mod} p)$ .

Example 2.2.10   If $p=7$ then $(p-1)!=720$ and $(p-1)!+1=721=7\cdot 103$ , so $720\equiv -1({\rm mod} 7)$ .