Finite Fields

Lemma 1   Let $k\subset\mathbb{K}$ be fields, and let $f(x),g(x)\in k[x]\subset \mathbb{K}[x]$. Then the $gcd\big(f(x),g(x)\big)$ computed in $\mathbb{K}[x]$ is the same as the $gcd\big(f(x),g(x)\big)$ computed in $k[x]$.

The proof of the lemma follows directly from the division algorithm.

Proof. In $\mathbb{K}[x]$ we can write

$$f(x)=Q(x)g(x)+R(x)$$

where $Q(x), R(x)\in\mathbb{K}[x]$ and deg$(R)<$deg$(g)$. Since both $f(x), g(x)\in k[x]$ we can also write

$$f(x)=q(x)g(x)+r(x)$$

where $q(x), r(x)\in k[x]$ and deg$(r)<$deg$(g)$. But the equation $f(x)=q(x)g(x)+r(x)$ also holds in $\mathbb{K}[x]$ because $k\subset\mathbb{K}$. Then the uniqueness of $Q(x)$ and $R(x)$ in $\mathbb{K}[x]$ ensures that $Q(x)=q(x)$ and $R(x)=r(x)$. So the lists occuring in the Euclidean algorithm will be indentical in both fields and thus $(f,g)\in\mathbb{K}[x]=(f,g)\in k[x]$.
$\qedsymbol$

So when working with the gcd of two polynomial functions in a polynomial ring over a field $\mathbb{F}$, we can work in either the base field $\mathbb{F}$ or a polynomial ring over a field extension $\ensuremath{\mathbb{F}}'$. In particular, we may wish to extend $\mathbb{F}$ to a splitting field for some polnomial in $\ensuremath{\mathbb{F}}[x]$.

Lemma 2   Let $f(x)=\prod(x-a_i)\in\ensuremath{\mathbb{F}}[x]$, where $\mathbb{F}$is a field and $a_i\in\ensuremath{\mathbb{F}}$ for all $i$. Then $f(x)$ has no repeated roots iff the $gcd\big(f(x),f'(x)\big)=1$, where $f'(x)$ is the derivative of $f(x)$.

Proof. $\big(\Longrightarrow\big)$

Assume that $f(x)$ has a repeated root and show that $f(x)$ and $f'(x)$ are not relatively prime. If $f(x)$ has a repeated root then

$$f(x)=(x-a)^2g(x)\;$$for some$$\;a\in\ensuremath{\mathbb{F}}\;$$and$$\;g(x)\in\ensuremath{\mathbb{F}}[x]$$

Then using the product rule for derivatives we get

$$f'(x)=2(x-a)g(x)+(x-a)^2g'(x)=(x-a)\bigg(2g(x)+(x-a)g'(x)\bigg)$$

But then $(x-a)$ divides both $f(x)$ and $f'(x)$ and the $gcd\big(f(x),f'(x)\big)\ne 1$.

$\big(\Longleftarrow\big)$

Assume that $gcd\big(f(x),f'(x)\big)=1$ and show that $f(x)$ is not equal to the product $(x-a)^2h(x)$, where $a\in\ensuremath{\mathbb{F}}$ and $h(x)\in\ensuremath{\mathbb{F}}[x]$.

By assumption, if $f(a)=0$ then $f'(a)\ne 0$. We can write $f(x)=(x-a)g(x)$ for $a\in\ensuremath{\mathbb{F}}$ and $g(x)\in\ensuremath{\mathbb{F}}[x]$ and it follows that $f'(x)=(x-a)g'(x)+g(x)$. But then $f'(a)\ne 0$ implies that $g(a)\ne 0$ and thus $g(x)\ne(x-a)h(x)$ for some $h(x)\in\ensuremath{\mathbb{F}}[x]$. Therefore,

$$f(x)\ne(x-a)^2h(x)$$

and the proof is complete.
$\qedsymbol$

Given the previous two lemmas we get the following theorem.

Theorem 4   Let $f(x)$ be a polynomial in $\ensuremath{\mathbb{F}}[x]$. Then $f(x)$ has no repeated roots iff the $gcd\big(f(x),f'(x)\big)=1$.

The next corrolarry follows.

Corollary 1   Let $n$ be a positive integer and let $\mathbb{F}$ be a field. If the characterisitic of $\mathbb{F}$ is either 0 or is a prime not dividing $n$, then $x^n-1$ has exactly $n$ distinct roots in a splitting field.

Proof. If $f(x)=x^n-1$ then $f'(x)=nx^{n-1}$ which is not equal to zero since $p$ does not divide n. Thus $gcd\big(f(x),f'(x)\big)=1$ and $f(x)$ has no repeated roots. Since every polynomial has a splitting field, there must be some extension $\ensuremath{\mathbb{F}}'$ such that $\ensuremath{\mathbb{F}}\subset\ensuremath{\mathbb{F}}'$ and $f(x)$ has $n$ distinct roots in $\ensuremath{\mathbb{F}}'$.
$\qedsymbol$

For example, consider the field $\ensuremath{\mathbb{F}}=GF(2)$ which has characteristic 2. Then for any odd integer $n>2$ we can find a field extension $\ensuremath{\mathbb{F}}'$ such that $\alpha^n=1$ for some $\alpha\in\ensuremath{\mathbb{F}}'$. Recall that a field $\ensuremath{\mathbb{F}}'$ with $q$ elements has an $nth$ root of unity iff $n\mid q-1$. So let $n=5$ and let $m$ be the smallest integer such that $2^m>5$ and $5\mid 2^m-1$. Then $m=4$.

To create the extension, find an irreducible polynomial $f(x)$ of degree $m=4$ over $\ensuremath{\mathbb{Z}}_2$ and then form the field $\ensuremath{\mathbb{Z}}_2/<f(x)>\;\cong GF(16)$. Because 2 does not divide 5, then $gcd(5,16)=1$. Also, since $m$ was chosen correctly we have $5\mid 15$ which is the order of $GF(16)^{*}$ and there will be a unique cyclic subgroup $G\subset GF(16)^{*}$ of order 5 such that for all $g \in G$ we have $g^n=1$. These are the fifth roots of unity in the extension that we were looking for. And because there must be a primitive element in every cyclic group, one of the roots $\alpha$ is a primitive root of unity. Thus $\alpha^k\ne 1$ for all $1\le k<n$.