Past exam of the mathematics course of the University of Oxford / 2017 / Prelims / Mathematics I / 5 / c

If a permutation has disjoint cycle lengths $d_1,\dots ,d_t$, then its $k$th power is the identity exactly when every $d_j$ divides $k$. Thus its order of a permutation is $\mathrm{lcm}(d_1,\dots ,d_t)$.

Suppose $n=p^r$ is a prime power and $\sigma \in S_n$ has order $n$. Each $d_j$ divides $p^r$, so is a power of $p$. Their least common multiple is therefore their maximum, forcing some $d_j=p^r=n$. This cycle already uses all $n$ symbols, so $\sigma$ is an $n$-cycle.

Conversely, if $n>1$ is not a prime power, choose a prime-power factor $a=p^r$ containing the full power of one prime divisor of $n$, and put $b=n/a$. Then $a,b>1$, they are coprime, and $ab=n$. Moreoverso $a+b\le n$. We can therefore take disjoint cycles of lengths $a$ and $b$ in $S_n$, fixing all remaining symbols. Their product has order of a permutation $\mathrm{lcm}(a,b)=ab=n$, but it is not an $n$-cycle. This proves the prime-power characterization by full permutation cycles: