Prove that $\{1^n,2^n,3^n,\ldots,(p-1)^n\}$ is a reduced residue system modulo $p$ 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?
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$...
How can two of your elements be congruent mod $p?$ How can one of them NOT be relatively prime to $p?$