[step: A finite subgroup of the multiplicative group of a field is cyclic] Let $F$ be any field and let $G$ be a finite subgroup of $F^{\times}$ with $|G| = n$. We claim $G$ is cyclic. Suppose for contradiction that $G$ is not cyclic. By the classification of finite abelian groups, $G$ decomposes as a direct sum of cyclic groups. If $G$ is not itself cyclic, there exists a prime $p$ and an integer $k \geq 1$ such that $\mathbb{Z}/p^k\mathbb{Z} \times \mathbb{Z}/p^k\mathbb{Z}$ appears as a subgroup of $G$. In particular, setting $d = p^k$, the subgroup $\mathbb{Z}/d\mathbb{Z} \times \mathbb{Z}/d\mathbb{Z}$ sits inside $G \subseteq F^{\times}$. Every element of $\mathbb{Z}/d\mathbb{Z} \times \mathbb{Z}/d\mathbb{Z}$ satisfies $x^d = 1$, and this subgroup has $d^2$ elements. But the polynomial $x^d - 1$ has degree $d$ over the field $F$, so it has at most $d$ roots in $F$. This is a contradiction, since we have exhibited $d^2 > d$ distinct roots. Therefore $G$ must be cyclic. [guided] **Why does the classification of finite abelian groups guarantee a repeated cyclic factor when $G$ is not cyclic?** By the structure theorem, $G \cong \mathbb{Z}/d_1\mathbb{Z} \times \cdots \times \mathbb{Z}/d_r\mathbb{Z}$ with $d_i \mid d_{i+1}$. If $r = 1$ then $G$ is already cyclic. If $r \geq 2$, let $p$ be any prime dividing $d_1$. Then $\mathbb{Z}/d_1\mathbb{Z}$ contains a copy of $\mathbb{Z}/p\mathbb{Z}$, and since $d_1 \mid d_2$, the group $\mathbb{Z}/d_2\mathbb{Z}$ also contains a copy of $\mathbb{Z}/p\mathbb{Z}$. This gives the subgroup $\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z} \hookrightarrow G$, which suffices for the argument with $d = p$. [/guided] [/step] [step: $\mathbb{F}_q^{\times}$ is cyclic of order $q - 1$] Now let $q = p^n$ be a prime power and consider the finite field $\mathbb{F}_q$. The multiplicative group $\mathbb{F}_q^{\times}$ consists of the $q - 1$ nonzero elements of $\mathbb{F}_q$, so $|\mathbb{F}_q^{\times}| = q - 1$. Since $\mathbb{F}_q^{\times}$ is a finite subgroup of the multiplicative group of the field $\mathbb{F}_q$, Step 1 applies directly: \begin{align*} \mathbb{F}_q^{\times} \cong \mathbb{Z}/(q-1)\mathbb{Z}. \end{align*} That is, $\mathbb{F}_q^{\times}$ is cyclic of order $q - 1$. In particular, there exists a generator $g \in \mathbb{F}_q^{\times}$ such that every nonzero element of $\mathbb{F}_q$ can be written as $g^k$ for some $0 \leq k \leq q - 2$. $\blacksquare$ [guided] **Why is it important that we work over a field, not just an integral domain?** The key fact used is that a polynomial of degree $d$ over $F$ has at most $d$ roots. This holds because $F[x]$ is a unique factorization domain and every root $\alpha$ gives a factor $(x - \alpha)$, so there can be at most $d$ such linear factors. This property holds in any integral domain, so the result actually extends: any finite subgroup of the multiplicative group of an integral domain is cyclic. However, for the application to $\mathbb{F}_q^{\times}$ we only need the field case. [/guided] [/step]