Is there a permutation $\sigma(n)$ of $\{0,1,2,\ldots,m-1\},$ such that $\{(n+\sigma(n))\pmod m:0\leq n\leq m-1\}=\{0,1,2,\ldots m-1\}?$

Question

Given $m\in\mathbb{N},$ is there a permutation $\sigma(n)$ of $\{0,1,2,\ldots,m-1\},$ such that $\{ (n+\sigma(n))\pmod m: 0\leq n \leq m-1 \} = \{0,1,2,\ldots m-1\},\ ?$

Based on computation with Python for low numbers, the answer seems to be, "yes for prime numbers; no for non-primes", although this might not be true as the results of low numbers (up to $m=9$) could be deceptive. However, there is some evidence that the conjecture is true: for $m=3$ there are about $3$ "successes" (successful permutations). For $m=4$ there are no successes. For $m=5$ there are about $10$ successes. For $m=6$ there are no successes. For $m=7$ there are lots of successes. For $m=8$ there are no successes.

Edit: for $m=9$ there are lots of successes, so this suggests the answer is "yes for odd, no for even", rather than "yes for primes", which also matches the current only answer.

Python code for $m=5$:

import itertools
length_five_list=[0, 1, 2, 3,4]
permutations_list=list(itertools.permutations(length_five_list))

print(permutations_list)
    
for x in permutations_list:
    current_zip = zip(x,length_five_list)
    sum_list = []
    for y in current_zip:
        sum_list.append(sum(y)%5)
        if set(sum_list) == set(length_five_list):
            print('sum_list=', sum_list)
            print( 'success: permutation was', x)

I also have a similar question for $n\sigma(n)$ instead of $n+\sigma(n),$ but let's deal with one question at a time.

Answer 1

Such a permutation exists iff $m$ is odd. For any odd $m$, choose $\sigma(n) = n$. Then $2$ resulting values being congruent to each other means

$$n_1 + \sigma(n_1) \equiv n_2 + \sigma(n_2) \pmod{m} \;\to\; 2(n_1 - n_2) \equiv 0 \pmod{m}$$

Since $m$ is odd, with $0 \le n_1, n_2 \le m - 1 \;\to\; -m \lt n_1 - n_2 \lt m$, then $m\mid n_1 - n_2 \;\to\; n_1 - n_2 = 0 \;\to\; n_1 = n_2$. Thus, all of the modulo values are unique and, by the Pigeonhole Principle, must comprise the values between $0$ and $m - 1$, inclusive.

With $m$ being even, assume such a permutation exists. We then get

$$\begin{equation}\begin{aligned} \sum_{n=0}^{m-1}(n+\sigma(n)) & \equiv \sum_{n=0}^{m-1}n \pmod{m} \\ 2\left(\frac{(m-1)m}{2}\right) & \equiv \frac{(m-1)m}{2} \pmod{m} \\ (m-1)\left(\frac{m}{2}\right) & \equiv 0 \pmod{m} \end{aligned}\end{equation}$$

This means $m \mid (m-1)\left(\frac{m}{2}\right)$. However, $\gcd(m-1,m) = 1$ (with $\gcd(m-1,m)=d$, then $d\mid m-1$ and $d\mid m$, so $d\mid(m - (m-1))$, i.e., $d\mid 1$, so $d=1)$. As mentioned in Adam's comment, using the theorem that if $a\mid bc$ with $\gcd(a,b)=1$ then $a\mid c$, we get $m \mid \frac{m}{2}$. However, this is not possible. Thus, the assumption that such a permutation exists is false.