I was thinking about shuffling, mapping ${(1,2,...,n-1)}$ to a permutation of itself using a mapping like $x\to x^k \mod(n)$ and clearly $k=2$ cannot work since $1$ and $n-1$ have the same image for all values of n.
I'm trying to exhaust the particular case of $k=3$ i.e.
For what values of n is $f(x) = x^3 mod(n)$ a bijection from $X={(0,1,2,...,n-1)}$ to itself.
I've observed that
$f$ need not necessarily be a bijection when n is prime (eg: $1^3\mod(13) \equiv 3^3mod(13)$ and $1^3\mod(19)\equiv7^3\mod(19)$)
n must be square free since if: $n=p^2*k$ then $(pk)^3\equiv0\mod(n)$
- My grunt work suggests that f is a bijection for $n=n_1$ iff $f$ is a bijection for all $p_i$ where $n_1=p_1p_2...p_k$
I am unaware of concepts related to cubic reciprocity but am familiar with elementary number theory and quadratic reciprocity.
My bigger question, that i'm planning to build upto is: Is there always some $n$ such that $f(x)=x^k\mod(n)$ is a bijection on $X$, $\forall k>2$ (i.e can i always find a mapping of this type to shuffle n-1 objects?)
I would like some help with the stated problem and also some direction as to what concepts i'm dealing with, is it just number theory or is some concept of abstract algebra better suited for such a question.
I'm trying to give a complete solution, where the I try to expand on the very good hints given by Μάρκος Καραμέρης and Ivan Neretin to find out which primes are 'good' (see below).
First, as already mentioned and proved by the problem author, $n$ needs to be square free as a necessary condition, so we have to look only at
$$ n = p_1p_2\ldots p_k$$
with the $p_i$ being the (different) prime factors of $n$. For ease of formulation, let's call a number $n \in \mathbb N$ 'good' if the considered mapping is a bijection, otherwise we call $n$ 'bad'.
A bad number $n$ can be characterized in 2 ways: It means that there is an $y \in X$ that is not in the image of $f$, or, equivalently, that there are 2 different $x,y \in X$ with $x^3 \equiv y^3 \pmod n$.
Lemma 1: If any $p_i$ is bad, then $n$ is bad.
Proof: Since $p_i$ is bad, there exists a value $b \in \{0,\ldots,p_i-1\}$ such that the equation $x^3 \equiv b \pmod {p_i}$ has no solution. If the equation $x^3 \equiv b \pmod n$ had a solution, the same value $x$ would also be a solution of $x^3 \equiv b \pmod {p_i}$, since $p_i|n$. $\blacksquare$
Lemma 2: If all $p_i$ are good, then $n$ is good.
Proof: Choose any $m \in X$. Because $p_i$ is good, the equation $x^3 \equiv m \pmod {p_i}$ has a (unique) solution $m_i \mod p_i$: Any $x$ with $x \equiv m_i \pmod {p_i}$ will satisfy $x^3 \equiv m \pmod {p_i}$.
By the chinese reminder theorem, there is a number $x$ (unique $\mod n$) that will satisfy all the $k$ equations $x \equiv m_i \pmod {p_i}$ at the same time. That means it will also satisfy all the $k$ equations $x^3 \equiv m \pmod {p_i}$ at the same time, which implies $x^3 \equiv m \pmod n$. Since you can change $x$ freely $\mod n$, you can choose one $x \in X$, which proves that $n$ is good. $\blacksquare$.
Lemma 1 and Lemma 2 show that we can now restrict ourselves to study only prime numbers as $n$. As often done, I'll denote that prime by $p$.
Theorem : $p \equiv 1 \pmod 3$ $\iff$ $p$ is bad.
Proof: $\Rightarrow$: It is known that the multiplicative group $\mod p$ is cyclic, so there exists a $g$ (generating element) such that $g^{p-1} \equiv 1 \pmod p$, but that this is not true for any lower positive exponent. Since $p \equiv 1 \pmod 3$, $\frac{p-1}3$ is an integer and hence with $r=g^{\frac{p-1}3}$ we have $r^3 \equiv 1 \pmod p$, whith $r \neq 1 \pmod p$. This concludes the $\Rightarrow$ direction of the proof.
$\Leftarrow$: If $p$ is bad, then there exist $x,y$ with $x\neq y \pmod p$ such that $x^3 \equiv y^3 \pmod p$. Since $p$ is a prime, the only solution to $x^3 \equiv 0 \pmod p$ is $x \equiv 0 \pmod p$, so we canonot have $x^3 \equiv y^3 \equiv 0 \pmod p$ and hence we have $x,y \neq 0 \pmod p$. That means we can divide both sides by $y^3$ and get $\frac{x^3}{y^3} \equiv 1 \pmod p$, which means we have a $z=\frac{x}y \neq 1 \pmod p$ with
$$ z^3 \equiv 1 \pmod p$$
The order of $z$ in the multiplicatice group $\mod p$ is therefore a divisior of 3. Since $z\neq 1 \pmod p$, we get that the order of $z$ is 3, which implies that $3|(p-1)$, as $p-1$ is the order of the group. This concludes the final part of the proof of the theorem.$\blacksquare$
To sum up, a number $n$ is good iff it is the product of distinct primes that are not $\equiv 1 \pmod 3$.