Having some doubts proving exercise statement from Pinter's book. Here's quote:

Let $\alpha $ be a cycle of length $s$, say $\alpha = ( a_1, a_2 ... a_s )$. Prove that, if $s$ is a prime number, every power of $\alpha$ is a cycle.

I know well that power $k$ of cycle of length $k \cdot t$ is a product of $k$ disjoint cycles of length $t$. Prime number length will not let this happen with any power. But I'm not sure whether powering the cycle to a divisor of its length is the only way to break cycle apart.

Thank you for your attention.

  • 2
    $\begingroup$ consider the group generated by $\alpha$. it is cyclic of order $p$ and every non-identity element is a generator. $\endgroup$ – yoyo Dec 16 '11 at 20:58
  • 2
    $\begingroup$ Here's one way of looking at it. Let's label the cycle as $(a_0, \ldots, a_{s - 1})$ instead. Then we can view the subscripts as being the distinct elements of the group $\mathbf Z/s\mathbf Z$. Then $\alpha^k$ sends $a_i$ to $a_{i + k}$. Note that every non-zero element of $\mathbf Z/s\mathbf Z$ generates that group. $\endgroup$ – Dylan Moreland Dec 16 '11 at 21:04
  • $\begingroup$ @DylanMoreland: I think $\alpha^k$ sends $a_i$ to $a_{ik}$, not $a_{i+k}$. $\endgroup$ – Greg Martin Dec 16 '11 at 22:48
  • $\begingroup$ @DylanMoreland: yeah, I think you're right ... sorry.... $\endgroup$ – Greg Martin Dec 18 '11 at 3:44
  • 1
    $\begingroup$ For reference, this is exercise 8.B.8 in Pinter. $\endgroup$ – dharmatech Aug 3 '17 at 2:47

The claim is slightly incorrect. The correct claim is:

The permutation $\beta = \alpha^k$ is a cycle if and only if $s$ does not divide $k$.

Clearly, if $s$ divides $k$, then $\alpha^k$ is just the identity permutation, and hence not a cycle. Now for the other direction, assume $s$ does not divide $k$. It suffices to show that for each $t \in \{ 1, 2, \ldots, s \}$, there exists an $i$ such that $\beta^{i}(a_1) = a_t$; i.e., $\alpha^{ki}(a_1) = a_t$. But this happens if and only if $$ ki \equiv t-1 \pmod s. $$

Assuming $s$ does not divide $k$, since $s$ is a prime, $k$ has a multiplicative inverse $k^{-1}$ modulo $s$. Now picking $i = k^{-1} \cdot (t-1)$ gives what we want.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.