= Solution
{c}
If a <permutation> has disjoint cycle lengths $d_1,\ldots,d_t$, then its $k$th power is the identity exactly when every $d_j$ divides $k$. Thus its <order of a permutation> is $\operatorname{lcm}(d_1,\ldots,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$. Moreover
$$
ab-a-b=(a-1)(b-1)-1\geq0,
$$
so $a+b\leq 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> $\operatorname{lcm}(a,b)=ab=n$, but it is not an $n$-cycle. This proves the <prime-power characterization by full permutation cycles>:
$$
\boxed{\text{every element of order }n\text{ in }S_n\text{ is an }n\text{-cycle}\iff n=p^r.}
$$
Back to article page
