I have a question taken from Abstract Algebra by Dummit and Foote
(pg. 33, q.11):
Let $\sigma\in S_{n}$ be an $m$-cycle. Show that $\sigma^{k}$ is
also an $m$-cycle iff $\gcd(k,m)=1$.
My efforts:
By considering a few examples I believe that $\sigma^{k}$ decomposition
is a multiplication of cycles where each cycle is of length $\frac{m}{\gcd(k,m)}$
I have tried proving this by showing that
$$
\frac{m}{\gcd(k,m)}+k\equiv_{m}1
$$
which shows that $\sigma^{k}$ maps $\frac{m}{\gcd(k,m)}$ back to
$1$ hence is the cycle length (at least for the first cycle in the
decomposition, but I imagine that proving similar claim for the other
circles can be done analogy) .
I have tried showing this by writing the equivalence as
$$
m\mid\frac{m}{\gcd(k,m)}+k-1
$$
and trying to manipulate the above expression to see the divisibility,
but I haven't managed to do so.
Best Answer
The number of cycles in a permutation is equal to the number of orbits it has (meaning, the number of orbits of the cyclic subgroup it generates). Without loss of generality $\sigma=(1\cdots m)$ and we can consider it acting on $\Bbb Z/m\Bbb Z$ via $x\mapsto x+1$ (every other orbit of $\sigma$ is a fixed point) so $\sigma^k$ acts by $x\mapsto x+k$.
The orbits of $x\mapsto x+k$ look like $\{x,x+k,x+2k,\cdots\}$ which are precisely the cosets $x+\langle k\rangle$ of the additive subgroup $\langle k\rangle=\{0,k,2k,\cdots\}$ of $\Bbb Z/m\Bbb Z$. Thus, the number of orbits is equal to $m/|k|$ where we let $|k|$ represent the additive order of $k$ mod $m$ (equivalently, the size of $\langle k\rangle$). At this point, for the purpose of the problem, it suffices to determine when $|k|=m\Leftrightarrow \langle k\rangle=\Bbb Z/m\Bbb Z\Leftrightarrow [k]\in(\Bbb Z/m\Bbb Z)^\times$ is a unit mod $m$, but we could also more generally prove the formula for the order $|k|$.
Units of $\Bbb Z/m\Bbb Z$ are precisely residues of integers coprime to $m$. Clearly any noncoprime integer will have a residue which is a zero divisor, and conversely multiplication by the residue of a coprime integer is an injective map on a finite set hence bijective, so $1$ has a preimage which must be the multiplicative inverse mod $m$.
Now for the more general formula, which isn't strictly part of the original problem. Note the additive subgroups of the ring $\Bbb Z/m\Bbb Z$ are ideals, which correspond to ideals in $\Bbb Z$ containing the ideal $m\Bbb Z$ by the fourth isomorphism theorem; moreover, since $\Bbb Z$ is a PID, so must its quotients be, so $\langle k\rangle=\langle d\rangle$ for some divisor $d\mid m$. In fact since we easily compute $\left(\frac{k}{(k,m)},m\right)=\frac{(k,m)}{(k,m)}=1$ (so $\frac{k}{(k,m)}$ represents a unit mod $m$), we know $k$ is associate to $k/\frac{k}{(k,m)}=(k,m)\mid m$ hence $\langle k\rangle=\langle (k,m)\rangle$ which has order $\frac{m}{(k,m)}$.
Hence this is the number of orbits of $\sigma^k$, and the number of cycles in $\sigma^k$ is $m/\frac{m}{(k,m)}=(k,m)$.
In an abstract algebra course, there is usually an exercise to prove $|\sigma^k|=|\sigma|/(k,|\sigma|)$ in the section on cyclic groups. I consider this to be kind of tricky to prove at this level using only arithmetic, it's like programming in a machine language instead of something higher. One time a professor and I spent ten minutes lamely trying to remember how to prove the formula with just arithmetic. But later in a course in abstract algebra one becomes acquainted with the rings $\Bbb Z/m\Bbb Z$, and when one has a toolkit involving not just gcds but units and associates and ideals as well, the problem (at least in my opinion) becomes not only tolerable but intuitive and fun.