Special properties to calculate the power of a permutation I have a permutation like $\alpha=(1,5,7)(2,4,6,10)(3,8,9)$. I want to calculate $\alpha^6$. what would be the fastest way.
At the start I though that if $\sigma\in S_n$ of order $k$ then $\sigma^m=id$ if $gcd(m,k)\neq 1$ but it is not correct (for example $o((2,4,6,10))=4$ and $gcd(6,4)\neq 1$ even though $(2,4,6,10)\neq id$). 
What could we say about the gcd? what would be the best way to calculate the permutation of $\sigma^k$. I could calculate $\alpha^i$ (not just the order) when $i\in \{2,6\}$ but its feels like hard work and there could be a faster way. for example, calculating $\alpha^{67}$ will be much harder.
I know that I can use the formula: $o(g^n)=\frac{o(g)}{gcd(o(g),n)}$ but I would like to calculate the structure, and not just the order.
 A: I assume that by "the structure of a permutation $\alpha$", you mean the number and lenghts of the cycles in its cycle decomposition, because this is the "interesting" information :-).
So let's consider a permutation $\alpha$ and its cycle decomposition
$$
\alpha = \beta_1 \cdots \beta_n,
$$
where the $\beta_j$ are disjoint cycles, and the length of $\beta_j$ is $\ell_j$.
Now, for a given power $m$, we have
$$
\alpha^m = \beta_1^m \cdots \beta_n^m,
$$
since the $\beta_j$ are disjoint and commute.
So, to determine the cycle decomposition of $\alpha^m$, it's enough to determine the cycle decomposition of each $\beta_j^m$.
It's not too difficult to see that $\beta_j^m$ consists of $gcd(\ell_j, m)$ disjoint cycles, each of length $\ell_j / gcd(\ell_j, m)$.
An intuitive proof of this is as follows. We can assume that $\beta_j$ is of the form
$$
\beta_j = (1, 2, \ldots, \ell_j).
$$
Let's determine the cycle $\gamma_1$ of $\beta_j^m$ that contains $1$. In order to do this, we start at $1$ and move $m$ steps to the right in a cyclic manner (i.e. when we get past $\ell_j$, we start again at $1$) to find the second element in the cycle $\gamma_1$. We repeat this construction ($m$ steps to the right in a cyclic manner) to find the third element of $\gamma_1$, and so on. The process stops, when we hit $1$ again. Then we have determined the complete cycle $\gamma_1$.
I assume that you're familiar enough with properties of the $gcd$ to know that we hit $1$ again after exactly $\ell_j / gcd(\ell_j, m)$ steps. In other words, $\gamma_1$ has length $\ell_j / gcd(\ell_j, m)$.
Side note: another view on this construction is that we're examining the size of the subgroup of $\mathbb Z / \ell_j \mathbb Z$ generated by $m$.
If we want to determine another cycle of $\beta_j^m$, say the cycle $\gamma_k$ starting with $k$, the construction is completely analogous, except that we start with $k$ instead of $m$. The reason is that cycles are - well - cyclic, and we have just rotated the starting point of the construction from $1$ to $k$. So we find that $\gamma_k$ also has length $\ell_j / gcd(\ell_j, m)$.
All in all, we find that $\beta_j^m$ decomposes into a number of cycles of equal length $\ell_j / gcd(\ell_j, m)$. Using the length of $\beta_j$, we find the number of cycles:
$$
\ell_j / (\ell_j / gcd(\ell_j, m)) = gcd(\ell_j, m).
$$
So, we found a good description of the structure of $\beta_j^m$ and thus also of $\alpha^m$.
