To find a primitive $n$-th root of unity in a field $F_q$ of size $q$, one takes the smallest positive integer $m$ such that $q^m \equiv 1 \bmod n$ and finds a primitive $n$-th root of unity in $\mathbb{F}_{q^m}$ by the formula $$\beta = \alpha^{\frac{q^m-1}{n}},$$ where $\alpha$ is a primitive element of $\mathbb{F}_{q^m}$.
But what is the reasoning behind this formula?
Best Answer
Hint: in any group, $$\text{ord}(\alpha^k) = \frac{\text{ord}(\alpha)}{\text{gcd}(\text{ord}(\alpha), k)}.$$