I'm currently looking at the following problem.
Let $p$ be a prime number. If $n$ is a positive integer with
$(n,p-1)=1$, prove that $$\{1^n,2^n,3^n,\ldots,(p-1)^n\}$$ is a
reduced residue system modulo $p$.
So we need to show that none of the elements in the above set are congruent modulo $p$ and that they are all relatively prime to $p$, knowing that $(n,p-1)=1$.
Since $p$ is a prime, we know that a primitive root modulo $m$ exists. Then the integer $a$ is an $n$th power residue modulo $p$ if and only if $$a^{(p-1)/d} \equiv 1 \pmod p$$ where $d=(n,p-1)$. But we know that $(n,p-1)=1$, so that $a$ is an $n$th power residue if and only if $a^{p-1}\equiv 1 \pmod p$.
How can we use this information?
Best Answer
Hint: if $(n, p-1)=1$ then you can find $a, b$ such that $an+(p-1)b=1$. Then for any $x$ invertible mod $p$,
$$(x^n)^a = x^{an} = x^{an+(p-1)b} = x.$$
(I used that $x^{p-1}=1$.)
Therefore the map $x \mapsto x^n$ has a double sided inverse given by $y \mapsto y^a$...