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

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: