## 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$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 89, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://crazyproject.wordpress.com/2010/01/12/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/", "fetch_time": 1490568993000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2017-13/segments/1490218189313.82/warc/CC-MAIN-20170322212949-00212-ip-10-233-31-227.ec2.internal.warc.gz", "warc_record_offset": 781276256, "warc_record_length": 20023, "token_count": 1275, "char_count": 3425, "score": 4.09375, "int_score": 4, "crawl": "CC-MAIN-2017-13", "snapshot_type": "latest", "language": "en", "language_score": 0.6924757361412048, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00062-of-00064.parquet"}