# If $n=2m$, what is the order of the permutation $\sigma(k)=2k , \quad \sigma(m+k)=2k-1$

Let $$n=2m$$. What is the order of the following permutation $$\sigma$$?

$$1\leq k\leq m \Rightarrow \sigma(k)=2k , \quad \sigma(m+k)=2k-1$$

• Could you share your data for small $m$? Feb 17 at 18:06
• There is only one guess: if $n=2^m$ then $|\sigma|=2^m$ (have no clear proof yet!)
– ABB
Feb 17 at 18:19
• If one may check by computer, a mysterious irregularity is observed for different cases $n$
– ABB
Feb 17 at 18:21
• Aside from a guess, presumably you have gathered data on specific values of small $m$. (If not, then that's where you should start!) What irregularity have you observed? Feb 17 at 19:12
• @ABB is not $|\sigma|=2m$ for $n=2^m$? Feb 17 at 20:19

By adding a fixed point at $$0$$ (which preserves the order), the permutation $$\sigma$$ considered is just the multiplication by $$2$$ modulo $$2m+1$$. Thus, for $$k \ge 0$$, $$\sigma^k$$ is the identity map if and only if it fixes $$1$$, namely if and only if $$2m+1$$ divides $$2^k-1$$.
Hence, the order of $$\sigma$$ is the order of $$2$$ in $$(\mathbb{Z}/(2m+1)\mathbb{Z})^\times$$. I do not think that there are formulas for this, although the order necessarily divides $$\phi(2m+1)$$ by Lagrange theorem.
• In more detail, this reduces to the case when $2m+1$ is a prime $p$, since the order of $2$ modulo $p^\nu$ is $p^{\nu-1}$ times the order of $2$ modulo $p$, while the order of $2$ modulo $mn$ for $m$, $n$ coprime is the lcm of orders modulo $m$ and $n$. Feb 23 at 5:56
• @მამუკაჯიბლაძე Is it easy to prove that the order of 2 modulo $p^\nu$ is $p^{\nu-1}$ times the order of 2 modulo $p$? I am a bit surprised by this statement. Feb 23 at 17:11
• Sorry, this is not actually true. The smallest counterexample I found is this: order of $2$ modulo $1093$ is the same as order of $2$ modulo $1093^2$, namely $364$. For a proof that once the order of some $1<a<p$ modulo $p^k$ is divisible by $p$ then order of $a$ modulo $p^{k+1}$ is $p$ times order of $a$ modulo $p^k$, see math.stackexchange.com/a/2217138/214353 It seems also true that these orders remain the same before becoming divisible by $p$. The smallest example when order modulo $p^3$ is not divisible by $p$ seems to be $p=113$, $a=68$. Feb 24 at 6:19