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

  • $\begingroup$ Thanks for your quick reply!! I still don't see why the system is a reduced residue system? $\endgroup$ – Numbersandsoon Dec 11 '13 at 5:34
  • $\begingroup$ Ah, is it to show that the map is bijective? I see.. That's so nice! :) $\endgroup$ – 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?$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.