GCD and the cycle decomposition of a permutation Take a permutation $\sigma \in \mathcal{S}_n$. Its cycle decomposition is the (essentially) unique decomposition in disjoint cycles : $\sigma = c_1 c_2 \cdots c_k$.
Write $p_i$ the length of each cycle $c_i$.
The lowest common multiple of all the $p_i$ is the order of the permutation, but is there anything interesting about the greatest common divisor of those same $p_i$?
$$
\gcd(p_1, \ldots ,p_k)\  =\  ?
$$
Notably, is there a name for permutations satisfying  $\gcd(p_1, \ldots ,p_k) = 1$
Thanks!
 A: I have not seen any name for such permutations, but I can give you some results when every cycle order $\vert c_i \vert$ is either $1$ or a prime not equal to any $\vert c_j \vert$
Taking this case, a permutation $\sigma = c_i \ldots c_r$ having $r$ disjoint cycles can be seen as a permutation with order $\prod_{i=1}^{r}\vert c_r \vert$ since cycle orders are guaranteed to not share common factors.
In the case of exponentiation, let $\sigma^x = c_1^x \ldots c_r^x = c_1^{x \pmod{\vert c_1\vert}}, \ldots, c_r^{x \pmod{\vert c_r \vert}}$. For example, in Cryptography, the Pohlig-Hellman algorithm, viewed as permutations, uses the advantage of the exponent $x$ being reduced in every cycle order. If we keep extending the definition, we find all the values $x \pmod{\vert c_i \vert}$, in the worst-case after $Deg(\sigma)$ iterations. The last step of the algorithm to recover $x$ is by solving an instance of the CRT (Chinese Remainder Theorem) as $\gcd(\vert c_i \vert , \ldots, \vert c_r \vert)=1$.  Time ago I wrote about these examples (p. 12-13).
Another fact in exponentiation, if we desire to build a permutation $\sigma$ with big order, the only way to have such order is having a distinct prime decomposition in the cycle orders. This way, even having big order, retrieving the exponent $x$ is possible using the exponentiation trick shown above. This is a consequence of finding the smallest tradeoff between $Deg(\sigma)=\sum_{i=1}^r \vert c_i \vert$ and $Ord_G(\sigma)=\prod_{i=1}^r \vert c_i \vert$. View it as having small degree (number of symbols) but a big order i.e $Deg(\sigma)=2+3+5+\ldots+29=129$ and $Ord(\sigma)=2\cdot 3 \cdot 5 \ldots 29=6469693230$ and we recover $1 < x < 6469693230$, in the worst case, after $129$ iterations plus the CRT solving
Moreover, the case where every cycle order $\vert c_i \vert$ is prime satisfies the $\gcd=1$ assumption. Those permutations in $S_n$ can be constructed by selecting a $r$-sum $\sum_{i=1}^{r} \lambda_i=n$ where every $\lambda_i$ is prime or $\lambda_i=1$. Once you find a valid sequence, you can count all the permutations in the same conjugacy class as integer partitions of $n$ and the conjugacy classes of $S_n$ are related. For counting permutations first list the $k$ primes under $n$, containing $1$ this is $S=(1,p_1,\ldots,p_k)$. Then the sum of the cardinality of each conjugacy class associated to a distinct sequence on $P$ that sums $n$ gives you the total nº of permutations having prime cycle order or equal to $1$.
