Exercise 2.8.13 (When $1^k,2^k,\ldots,(p-1)^k$ form a reduced residue system modulo $p$)

Proof. Consider the map

Note first that $({(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}},\times )$ is a group, and that $\phi$ is a group homomorphism: for $x,y\in {(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$,

We will prove that $\phi$ is bijective if and only if $k\wedge (p-1)=1$.

• Suppose that $k\wedge (p-1)=1$. There exists a pair $(\lambda ,\mu )\in {\mathbb{Z}}^2$ such that

  $$\mathit{\lambda k}+\mu (p-1)=1.$$

  By Fermat’s theorem $x^{p-1}=1$. If $x\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )$, $x^k=1$, therefore $x=x^{\mathit{\lambda k}+\mu (p-1)}={(x^k)}^{\lambda }{(x^{p-1})}^{\mu }=1$. This shows that $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )=\{1\}$, so $\phi$ is injective (one-to-one). Moreover $\phi :\mathbb{Z}∕\mathit{p\mathbb{Z}}{\text{)}}^{\text{∗}}\to {(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$, where ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$ is a finite set, hence $\phi$ is bijective.

• To prove the converse, suppose that $k\wedge (p-1)=d>1$. Let $g$ be a generator of ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$ and let $x\in {(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{∗}}$. Then $x=g^y$ for some integer $y$, $0\le y<p-1$. Then

  $$\begin{array}{llllll}\hfill x\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )& ⟺x^k=1& \hfill & & \hfill & \\ \hfill & ⟺g^{\mathit{ky}}=1& \hfill & & \hfill & \\ \hfill & ⟺p-1\mid \mathit{ky}& \hfill & & \hfill & \\ \hfill & ⟺\frac{p-1}{d}\mid \frac{k}{d}y& \hfill & & \hfill & \\ \hfill & ⟺\frac{p-1}{d}\mid y& \hfill (\text{since }\frac{p-1}{d}\wedge \frac{k}{d}=1)& & \hfill & & \hfill \\ \hfill & ⟺y\in \left\{0,\frac{p-1}{d},2\frac{p-1}{d},\dots ,(d-1)\frac{p-1}{d}\right\}& \hfill (\text{since }0\le y<p-1)& & \hfill & & \hfill \\ \hfill & ⟺x\in \left\{1,g^{\frac{p-1}{d}},g^{2\frac{p-1}{d}},\dots ,g^{(d-1)\frac{p-1}{d}}\right\},& \hfill & & \hfill & \end{array}$$

  where $1,g^{\frac{p-1}{d}},g^{2\frac{p-1}{d}},\dots ,g^{(d-1)\frac{p-1}{d}}$ are distinct. Therefore $|\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )|=d>1$, thus $\phi$ is not bijective.

This shows that $\phi$ is injective if and only if $\phi$ is bijective, if and only if $k\wedge (p-1)=1$.

So $k\wedge (p-1)=1$ if and only if no two integers of the set $\{1^k,2^k,\dots ,{(p-1)}^k\}$ (of cardinality $p-1$) are congruent modulo $p$, that is if and only if $\{1^k,2^k,\dots ,{(p-1)}^k\}$ is a reduced residue system modulo $p$. □