## The order of a cycle in a symmetric group is its length

Prove that if $\sigma$ is the $m$-cycle $(a_1 a_2 \ldots a_m)$, then for all $i \in \{ 1, 2, \ldots, m \}$, $\sigma^i(a_k) = a_q$, where $q$ is the least positive residue of $k+i$ mod $m$. Deduce that $|\sigma| = m$.

We proceed by induction on $i$. Note that the least positive residue of $a$ mod $b$ is precisely the (unique) remainder $r$ satisfying $0 \leq r < |b|$, given $a = qb + r$ by the Division Algorithm.

The base case $i = 1$ follows from the definition of cycle notation; either $k+1 < m$, so $\sigma(a_k) = a_{k+1}$ and we have $k+1 = 0 \cdot m + (k+1)$, or $k+1 = m$, so that $\sigma(a_k) = a_1$ and we have $k+1 = 1 \cdot m + 0$.

Now suppose the conclusion holds for 1 and for some $n$ with $1 \leq n < m$. Then we have $\sigma^{n+1}(a_k) = \sigma(\sigma^n(a_k)) = \sigma(a_p) = a_q$, where p is the least positive residue of $k+n$ mod m, and $q$ the least positive residue of $p+1$ mod m; say $k+n = g \cdot m + p$ with $0 \leq p < |m|$ and $p+1 = h \cdot m + q$ with $0 \leq h < |m|$. Solving the second equation for $p$ and substituting into the first, we have $k+n+1 = (h-g) \cdot m + q$, and by the uniqueness part of the Division Algorithm, $q$ is in fact the least positive residue of $k+n+1$ mod m. Thus, by induction, the conclusion holds for all $1 \leq n \leq m$.

Note in particular that $\sigma^m(a_k) = a_k$ for all $1 \leq k \leq m$; hence $\sigma^m = 1$. Moreover, if $1 \leq i < m$, $\sigma^i \neq 1$ since in particular, $\sigma^i(a_1) = a_{1+i}$; if $a_1 = a_{1+i}$ then we have $i = 0$ mod m, a contradiction. Hence $|\sigma| = m$.