Let be the -cycle . Show that is also an -cycle if and only if .
First, we prove some technical lemmas.
Lemma 1. If and is fixed, then . Proof: Reducing mod , we know that each is equal to for some . Note that the are distinct; to see why, suppose with , but that mod . Then mod , and since we have , a contradiction. Thus the are all distinct, and so by the pigeonhole principle and a previous exercise we have .
Lemma 2. If , then the map given by is a permutation of . Proof: First, is well defined because multiplication in is well defined. Now to see that is a permutation, it suffices to show that it is injective. To that end, suppose . Then we have . Now since , there exists with . So and we have ; hence is injective.
Lemma 3. If , then every equivalence class is equal to for some . Proof: Since , there exits with . By Lemma 1 we have . Now under the permutation defined in Lemma 2 with gives us that .
Now to the main result.
First we show that if , then is not an -cycle. Suppose . Then we have and for some positive integers and . Note that , since otherwise we have a contradiction. Now , so that . By a previous exercise, since , is not an -cycle.
Now suppose that ; we show that is an -cycle. Let ; then by the previous exercise, , where is the least positive residue of mod m. By Lemma 3, takes on all the values with , and we know that ; so in the cycle decomposition of , the cycle containing has length . Since is a permutation of elements, is a permutation of elements. Thus the cycle decomposition of consists of a single -cycle.
Thus, we conclude that is an -cycle if and only if .