Exercise 1.3.10 (The order of a cycle is its length)

Proof.

(1)

Let us denote the least positive residue $r$ of $n\in \mathbb{Z}$ modulo $m$ by $\mathrm{rem}(a,m)$, defined by $$a=\mathit{mq}+r,q\in \mathbb{Z},1\le r\le m.$$

Let $k$ be a fixed integer, where $1\le k\le m$.

We prove by induction on $i$ that ${\sigma }^i(a_k)=a_{\mathrm{rem}(k+i,m)}.$

We define for every $i\in \mathbb{N}$,

$$𝒫(i)⟺{\sigma }^i(a_k)=a_{\mathrm{rem}(k+i,m)}.$$

• If $i=0$, then ${\sigma }^0(a_k)=a_k$. Since $1\le k\le m$, $\mathrm{rem}(k+i,m)=\mathrm{rem}(k,m)=k$, so $a_{\mathrm{rem}(k,m)}=a_k$. Thus $𝒫(0)$ is true.

• Suppose that $𝒫(i)$ is true for some $i\in \mathbb{N}$. Then ${\sigma }^i(a_k)=a_{\mathrm{rem}(k+i,m)}$. Therefore

  $$\begin{array}{llll}\hfill {\sigma }^{i+1}(a_k)& =\sigma (a_{\mathrm{rem}(k+i,m)}).& \hfill & \end{array}$$

  • If $m\nmid k+i$, then $\mathrm{rem}(k+i,m)=r$, where $k+i=\mathit{mq}+r$, for some integer $q$ and $r$ such that $1\le r<m$.

    By the induction hypothesis $𝒫(i)$, ${\sigma }^i(a_k)=a_r$. Therefore

    $$\begin{array}{llllll}\hfill {\sigma }^{i+1}(a_k)& =\sigma (a_r)& \hfill & & \hfill & \\ \hfill & =a_{r+1}& \hfill (\text{since }1\le r<m)& & \hfill & & \hfill \\ \hfill & =a_{\mathrm{rem}(k+i+1,m)},& \hfill & & \hfill & \end{array}$$

    because $k+i+1=\mathit{mq}+r+1$ and $1\le r+1\le m$.

  • If $m\mid k+i$, then $k+i=\mathit{qm}$ for some integer $q$, so $k+i=(q-1)m+m$, so $\mathrm{rem}(k+i)=m$. The induction hypothesis $𝒫(i)$ gives then

    $${\sigma }^i(a_k)=a_{\mathrm{rem}(k+i,m)}=a_m.$$

    Therefore

    $$\begin{array}{llll}\hfill {\sigma }^{i+1}(a_k)& =\sigma (a_m)& \hfill & \\ \hfill & =a_1& \hfill & \\ \hfill & =a_{\mathrm{rem}(k+i+1,m)},& \hfill & \end{array}$$

    because $k+i+1=\mathit{qm}+1$, so $\mathrm{rem}(k+i+1,m)=1$.

  In both cases, ${\sigma }^{i+1}(a_k)=a_{\mathrm{rem}(k+i+1,m)}$ so $𝒫(i+1)$ is true, under the hypothesis $𝒫(i)$.

• The induction is done, so for all $k\in [[1,m]]$,

  $$\forall <!--\; FUNCTION\; APPLICATION\; -->i\in \mathbb{N},{\sigma }^i(a_k)=a_{\mathrm{rem}(k+i,m)}.$$

  This is true in particular for $i\in \{1,2,\dots ,m\}$.

  In conclusion, if $\sigma$ is the $m$-cycle $(a_1{a}_2\dots a_m)$, then for all $i\in \{1,2,\dots ,m\}$, ${\sigma }^i(a_k)=a_{k+i}$, where $k+i$ is replaced by its least positive residue mod $m$ when $k+i>m$

(2)

By part 1, we obtain in particular that for all $k\in [[1,m]]$, $${\sigma }^m(a_k)=a_{\mathrm{rem}(k+m,m)}=a_k.$$

(and ${\sigma }^m(x)=x$ if $x\notin \{a_1,a_2,\dots ,a_m\})$. This shows that ${\sigma }^m=e$.

Moreover, if $1\le i<m$, for some fixed $k$, ${\sigma }^i(a_k)=a_r$, where $r=\mathrm{rem}(k+i,m)$.

Assume for the sake of contradiction that $r=k$. Then $k=\mathrm{rem}(k+i,m)$, so $k+i=\mathit{qm}+k$ for some integer $q$, thus $i=\mathit{qm}$, and $m\mid i$. But $1\le i<m$: this is impossible. Therefore $r\ne k$. Since the $a_i$ are distinct, we obtain ${\sigma }^i(a_k)\ne a_k$, thus ${\sigma }^i\ne e$ if $1\le i<m$. We have proved

$$|\sigma |=m.$$