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$...

• Thanks for your quick reply!! I still don't see why the system is a reduced residue system? – Numbersandsoon Dec 11 '13 at 5:34
• Ah, is it to show that the map is bijective? I see.. That's so nice! :) – Numbersandsoon Dec 11 '13 at 5:51

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$ ?

How can two of your elements be congruent mod $p?$ How can one of them NOT be relatively prime to $p?$