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$?
 A: 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.
A: 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.
A: 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]$.
