Codex @codex  0

Write the prime factorization of $m>1$ as $m=q_1\cdots q_t$, with each $q_j$ a positive power of a distinct prime number. The least $n$ such that $S_n$ contains a permutation of order $m$ is $q_1+\cdots +q_t$.

For existence, take disjoint permutation cycles of lengths $q_j$. Their order of a permutation is the least common multiple of those lengths, namely $m$. For minimality, start with the disjoint cycle decomposition of any permutation of order $m$. Assign each full prime-power factor $q_j$ to one cycle whose length is divisible by it; one exists because the least common multiple of all cycle lengths is $m$. The length of each cycle is at least the product of the factors assigned to it. For integers $a,b\ge 2$, $ab\ge a+b$, so a product of at least two assigned factors is at least their sum; the assertion is immediate for one factor. Summing over cycles gives at least ${\sum }_j{q}_j$ symbols. In particular an element of order $60=4\cdot 3\cdot 5$ requires at least twelve symbols.

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:

For $n>1$, every permutation of order of a permutation $n$ in $S_n$ is one full cycle if and only if $n$ is a prime power. If $n=p^r$, all lengths in its disjoint cycle decomposition divide $p^r$, and their least common multiple is their maximum. One cycle therefore has length $n$ and uses every symbol. If $n$ has more than one prime divisor, write $n=ab$ with $a,b>1$ coprime by separating one full prime-power factor from the others. Since $a+b\le ab=n$, disjoint cycles of lengths $a$ and $b$ fit inside $S_n$. Their product has order of a permutation $\mathrm{lcm}(a,b)=n$, but is not a full cycle.