# 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$?

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} \rangle$$. 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.

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 \implies 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 \implies \left(\alpha^{q^{i-1}}\right)^q - \left(\alpha^{q^{m-1}}\right)^q = 0 \implies \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. Jul 4, 2012 at 4:46
• More than fine now, as far as I can tell. I'll delete the previous comment. Jul 4, 2012 at 4:51
• Why is $(a-b)^q = a^q-b^q$ in every field extension? Jul 4, 2012 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$. Jul 4, 2012 at 16:35

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.