# Roots of an irreducible polynomial in a finite field

Given a irreducible polynomial $f \in K[x]$ where $|K|=q$ is a finite field and $\deg(f)=n$. If $\alpha$ is a root of $f$ why are $\alpha, \alpha^q, \dots, \alpha^{q^{n-1}}$ the only possible candidates for the roots of $f$?

-

Amended in response to Arturo Magidin's comments.

$\beta^q = \beta$ for all $\beta \in \mathbb F_q$. Also, in any field that includes $\mathbb F_q$ as a subfield, $(a-b)^q = a^q - b^q$. Now suppose that $\alpha$ is an element in a field that contains $\mathbb F_q$ as a subfield, and that $f(\alpha)= 0$. Then, $$0 = [f(\alpha)]^q = \left[\sum_{i=0}^n f_i \alpha^i\right]^q = \sum_{i=0}^n (f_i)^q (\alpha^i)^q = \sum_{i=0}^n f_i (\alpha^q)^i = f(\alpha^q)$$ and so $f(\alpha) = 0 \Rightarrow f(\alpha^q) = 0$. It follows that the elements $\alpha, \alpha^q, \alpha^{q^2}, \alpha^{q^3}\cdots$ are roots of $f(x)$. How many of these are distinct? Suppose that $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{m-1}}$ are distinct elements but $\alpha^{q^m}$ is a repeat, that is, $\alpha^{q^m} = \alpha^{q^i}$ for some $i \in \{0, 1, \ldots, m-1\}$. If $i$ were greater than $0$, then we would have that $$\left(\alpha^{q^{i-1}}\right)^q = \alpha^{q^i} = \alpha^{q^m} = \left(\alpha^{q^{m-1}}\right)^q \Rightarrow \left(\alpha^{q^{i-1}}\right)^q - \left(\alpha^{q^{m-1}}\right)^q = 0 \Rightarrow \left(\alpha^{q^{i-1}} - \alpha^{q^{m-1}}\right)^q = 0$$ and so $\alpha^{q^{i-1}} = \alpha^{q^{m-1}}$ in contradiction to the hypothesis that $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{m-1}}$ are distinct elements. We conclude that $\alpha^{q^m} = \alpha$. Now consider the polynomial $g(x)$ defined as $$g(x) = \prod_{i=0}^{m-1}\left(x - \alpha^{q^i}\right) = \sum_{j=0}^m g_jx^j$$ whose roots are the $m$ distinct elements $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{m-1}}$. Then \begin{align*} [g(x)]^q &= \left[\prod_{i=0}^{m-1}\left(x - \alpha^{q^i}\right)\right]^q = \prod_{i=0}^{m-1}\left(x - \alpha^{q^i}\right)^q = \prod_{i=0}^{m-1}\left(x^q - \alpha^{q^{i+1}}\right)\\ &= \prod_{k=1}^{m}\left(x^q - \alpha^{q^{k}}\right) = \prod_{i=0}^{m-1}\left(x^q - \alpha^{q^i}\right) = g(x^q). \end{align*} Thus, $\displaystyle [g(x)]^q = \left[ \sum_{j=0}^m g_jx^j\right]^q = \sum_{j=0}^m (g_j)^q(x^j)^q = \sum_{j=0}^m (g_j)^q(x^q)^j$ equals $\displaystyle g(x^q) = \sum_{j=0}^m g_j(x^q)^j$, that is, proving that $(g_j)^q = g_j$ for $0 \leq j \leq m$. Therefore, we see that $g(x) \in \mathbb F_q[x]$. But, $g(x)$ is a divisor of $f(x)$ which is given to be irreducible over $\mathbb F_q$. So it must be that $m = n$ and $f(x)$ is a scalar multiple of $g(x)$. Thus, $\alpha^{q^0}, \alpha^{q^1}, \cdots, \alpha^{q^{n-1}}$ are precisely the $n$ distinct roots of the degree-$n$ irreducible polynomial $f(x) \in \mathbb F_q[x]$.

-
@ArturoMagidin Yes, I should have been more careful in what I wrote. Comments on the revised version would be appreciated. –  Dilip Sarwate Jul 4 '12 at 4:46
More than fine now, as far as I can tell. I'll delete the previous comment. –  Arturo Magidin Jul 4 '12 at 4:51
Why is $(a-b)^q = a^q-b^q$ in every field extension? –  joachim Jul 4 '12 at 16:12
@joachim: Because the field is of characteristic $p$, so $(a-b)^p = a^p-b^p$ (every other term has coefficient a multiple of $p$). Inductively, we obtain $(a-b)^{p^n} = a^{p^n} - b^{p^n}$ for all $n\geq 1$; and $q$ is a power of $p$. –  Arturo Magidin Jul 4 '12 at 16:35

They are all roots, at any rate.

Note that $K(\alpha)$ is an extension of degree $n$ of $K$. The Galois group is cyclic, generated by the Frobenius automorphism $a\longmapsto a^q$. As always, the image of a root $\alpha$ of a polynomial $f(x)\in K[x]$ under any element of $\mathrm{Gal}(E/K)$, where $E$ is a Galois extension of $K$, must also be a root of $f$. In particular, if $\alpha$ is a root, then so is $\alpha^q$, hence so is $\alpha^{q^2}$, and so on. The Galois group is of order $n$, so we end up with $\alpha$, $\alpha^q,\ldots,\alpha^{q^{(n-1)}}$ are all roots.

Now, there are $n$ of them. The questions is whether they are all distinct. If they are indeed all distinct, then that's it, they are all the roots and the only possible roots.

If $\alpha^{q^i} = \alpha^{q^j}$ with $0\leq i\leq j\leq n-1$, then that means that $\sigma^i(\alpha) = \sigma^j(\alpha)$ (where $\sigma$ is the Frobenius automorphisms); then $\alpha = \sigma^{j-i}(\alpha)$, which would mean that $\alpha$ lies in the fixed field of $\langle \sigma^{j-i}$. But since $K(\alpha)$ is generated by $\alpha$, $\alpha$ does not lie in any strictly intermediate field of $K(\alpha)/K$; that means that the fixed field of $\sigma^{j-i}$ must be $K(\alpha)$, hence $\sigma^{j-i} = \mathrm{id}$, so $j=i$. Therefore, they are all distinct, so they are in fact all the roots.

-

Let $E = K(\alpha) = K[x] / (f(x))$. For $\sigma \in \text{Gal}(E / K)$, $\sigma(\alpha)$ is a root of $f(x)$. The Galois group of finite extensions of finite fields is (cyclic) of order $n$. $\sigma_k(x) = x^{q^k}$ for $0 \leq k < n$ are $n$ of these automorphisms.

-