TITLE: Prove that $\{1^n,2^n,3^n,\ldots,(p-1)^n\}$ is a reduced residue system modulo $p$
QUESTION [4 upvotes]: 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?

REPLY [0 votes]: Let $S:\{r_k\}$ be a reduced residue system  $\displaystyle \pmod m$  where $m$ is any integer 
$\displaystyle\implies 1\le k\le \phi(m)$ and $r_i\not\equiv r_j\pmod m$ for $1\le i,j\le \phi(m)$ and $i\ne j\  \ \ \ (1)$
If $\displaystyle r_i^n\equiv r_j^n\pmod m\implies  \left(\frac{r_i}{r_j}\right)^n\equiv1$
Let us denote ord$_ma$ as Multiplicative Order of $a\pmod m$
We know ord$_m\left(\frac{r_i}{r_j}\right)$ divides $n$ 
and also  ord$_m\left(\frac{r_i}{r_j}\right)$ divides $\lambda(m)$ where $\lambda(m)$  is the Carmichael function
$\displaystyle\implies$ ord$_m\left(\frac{r_i}{r_j}\right)$ divides $(n,\lambda(m))$
If $(n,\lambda(m))=1, $ ord$_m\left(\frac{r_i}{r_j}\right)$ divides $1\implies $ ord$_m\left(\frac{r_i}{r_j}\right)=1$
$\displaystyle\implies \left(\frac{r_i}{r_j}\right)^1\equiv1\pmod m\implies r_i\equiv r_j$ which contradicts $(1)$ 
$\displaystyle\implies r_i^n\not\equiv r_j^n\pmod m,$  for $1\le i,j\le \phi(m)$ and $i\ne j$
Hence, $\{r_k^n\}$ will form a reduced residue system $\displaystyle \pmod m$ if $(n,\lambda(m))=1$
One exercise can be what if $(n,\lambda(m))>1$ ?
{"set_name": "stack_exchange", "score": 4, "question_id": 602235}