Roots of an irreducible polynomial in a finite field

Solution 1:

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.

Solution 2:

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]$.