1
$\begingroup$

An example of this would be a permutation of size 32. Can this be of order 62? I assume not because the only way to achieve this would be to have the permutation be made up out of a part with order 2 and one with order 31, but this is impossible.

Am I correct, and what is a formal way of proving this?

$\endgroup$
2
$\begingroup$

You are correct. All permutations consist of cycles, and the order of a permutation is the LCM of its cycle lengths.

Therefore, a permutation of size $n$ can be of order $m$ iff there exist numbers $p_1,p_2,\dots,p_k$ which sum to at most $n$ and multiply to $m$. Clearly, this remains true if the $p_i$ are required to be distinct coprime numbers greater than $1$, which can be used to simplify proofs of (non-)existence.

$\endgroup$
1
$\begingroup$

Each permutation of size $n\geq 1$ can be written as the product of $k\geq 1$ disjoint cycles $C_1,C_2,\dots,C_k$ and the order of $P$ is the least common multiple of the lengths of the cycles.

Hence, there is a permutation of size $n$ of order $m$ if and only $$ \begin{cases} l_1+l_2+\dots+l_k=n\\ \text{lcm}(l_1,l_2,\dots,l_k)=m \end{cases} $$ has a solution with $1\leq l_1\leq l_2\leq \dots\leq l_k$ positive integers and $k\geq 1$.

In your case $n=32$ and $m=62$. Since $62=2\cdot 31$ and $1\leq l_i\leq 32$, it follows easily that there are no solutions. So, yes, you are correct.

$\endgroup$

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.