## A cycle and its power have the same cycle shape if and only if the exponent is relatively prime to the length of the cycle

Let $\sigma$ be the $m$-cycle $(1\ 2\ \ldots\ m)$. Show that $\sigma^i$ is also an $m$-cycle if and only if $\mathsf{gcd}(m,i) = 1$.

First, we prove some technical lemmas.

Lemma 1. If $n \in \mathbb{Z}^+$ and $k \in \mathbb{Z}$ is fixed, then $\mathbb{Z}/(n) = \{ \overline{a+k} \ |\ 0 \leq a < n \}$. Proof: Reducing mod $n$, we know that each $\overline{a+k}$ is equal to $\overline{r}$ for some $0 \leq r < n$. Note that the $\overline{a+k}$ are distinct; to see why, suppose $0 \leq a_1, a_2 < n$ with $a_1 \neq a_2$, but that $a_1 + k = a_2 + k$ mod $n$. Then $a_1 = a_2$ mod $n$, and since $a_1, a_2 < n$ we have $a_1 = a_2$, a contradiction. Thus the $r$ are all distinct, and so by the pigeonhole principle and a previous exercise we have $\{ \overline{a+k} \ |\ 0 \leq a < n \} = \{ \overline{r} \ |\ 0 \leq r < n \} = \mathbb{Z}/(n)$. $\square$

Lemma 2. If $\mathsf{gcd}(a,b) = 1$, then the map $\varphi : \mathbb{Z}/(a) \rightarrow \mathbb{Z}/(a)$ given by $\overline{k} \mapsto \overline{bk}$ is a permutation of $\mathbb{Z}/(a)$. Proof: First, $\varphi$ is well defined because multiplication in $\mathbb{Z}/(a)$ is well defined. Now to see that $\varphi$ is a permutation, it suffices to show that it is injective. To that end, suppose $\varphi(\overline{x}) = \varphi(\overline{y})$. Then we have $\overline{bx} = \overline{by}$. Now since $\mathsf{gcd}(a,b) = 1$, there exists $\overline{c} \in \mathbb{Z}/(a)$ with $\overline{cb} = \overline{1}$. So $\overline{cbx} = \overline{cby}$ and we have $\overline{x} = \overline{y}$; hence $\varphi$ is injective. $\square$

Lemma 3. If $\mathsf{gcd}(a,b) = 1$, then every equivalence class $\overline{x} \in \mathbb{Z}/(a)$ is equal to $\overline{1 + rb}$ for some $0 \leq r < a$. Proof: Since $\mathsf{gcd}(a,b) = 1$, there exits $\overline{c} \in \mathbb{Z}/(a)$ with $\overline{cb} = \overline{1}$. By Lemma 1 we have $\mathbb{Z}/(a) = \{ \overline{c+r} \ |\ 0 \leq r < a \}$. Now under the permutation defined in Lemma 2 with $\overline{b}$ gives us that $\mathbb{Z}/(a) = \{ \overline{bc+br} \ |\ 0 \leq r < a \} = \{ \overline{1+rb} \ |\ 0 \leq r < a \}$. $\square$

Now to the main result.

First we show that if $\mathsf{gcd}(m,i) \neq 1$, then $\sigma$ is not an $m$-cycle. Suppose $\mathsf{gcd}(m,i) = d > 1$. Then we have $m = dk$ and $i = d \ell$ for some positive integers $k$ and $\ell$. Note that $k, \ell < m$, since otherwise we have a contradiction. Now $(\sigma^i)^k = (\sigma^{d \ell})^k = (\sigma^{dk})^\ell = 1^\ell = 1$, so that $|\sigma| \leq k < m$. By a previous exercise, since $|\sigma^i| \neq m$, $\sigma^i$ is not an $m$-cycle.

Now suppose that $\mathsf{gcd}(m,i) = 1$; we show that $\sigma^i$ is an $m$-cycle. Let $0 \leq k < m$; then by the previous exercise, $(\sigma^i)^k(1) = q$, where $q$ is the least positive residue of $1+ik$ mod m. By Lemma 3, $q$ takes on all the values with $0 \leq q < m$, and we know that $(\sigma^i)^m(1) = 1$; so in the cycle decomposition of $\sigma^i$, the cycle containing $1$ has length $m$. Since $\sigma$ is a permutation of $m$ elements, $\sigma^i$ is a permutation of $m$ elements. Thus the cycle decomposition of $\sigma^i$ consists of a single $m$-cycle.

Thus, we conclude that $\sigma^i$ is an $m$-cycle if and only if $\mathsf{gcd}(m,i) = 1$. $\blacksquare$