Exercise 2.8.32* (When is $x \mapsto x^k$ a permutation of $(\mathbb{Z}/ m \mathbb{Z})^\times$ ?)

Proof. This is a generalization of Problem 13. As usual, this is clearer if we translate the sentence in $\mathbb{Z}∕\mathit{m\mathbb{Z}}$.

Write ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ the group of invertible elements of $\mathbb{Z}∕\mathit{m\mathbb{Z}}$. We show that the map

is bijective if and only if $k\wedge \varphi (m)=1$. Note that $\phi$ is a group homomorphism.

• Suppose that $k\wedge \varphi (m)=1$. Then $1=\mathit{\lambda k}+\mathit{\mu \varphi }(m)$ for some integers $\lambda ,\mu$. If $x\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )$, then $x^k=1$. By Euler’s Theorem, $x^{\varphi (m)}=1$. Therefore

  $$x=x^{\mathit{\lambda k}+\mathit{\mu \varphi }(m)}={(x^k)}^{\lambda }{(x^{\varphi (m)})}^{\mu }=1.$$

  This shows that $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )=\{1\}$, thus $\phi$ is injective. Since $\phi$ applies ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ on itself, where ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ is a finite set, $\phi$ is bijective.

• Suppose now that $k\wedge \varphi (m)=d>1$.

  We begin with the particular case $m=p^{\alpha }$.

  • If $p\ne 2$, or $p=2$ and $\alpha \le 2$, by Corollary 2.42, the equation $x^k=1$ has $d>1$ solutions in ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{×}}$, thus $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )\ne \{1\}$. This shows that $\phi$ is not bijective. (Alternatively, we can proceed as in Problem 13, since $\mathbb{Z}∕p^{\alpha }\mathbb{Z}$ has a generator.)
  • If $p=2$ and $\alpha \ge 3$, then $k$ is even, otherwise $d=\varphi (n)\wedge k=2^{\alpha -1}\wedge k=1$. By Corollary 2.44, the equation $x^k=1$ has $2^{\beta +1}$ solutions in ${(\mathbb{Z}∕\mathit{p\mathbb{Z}})}^{\text{×}}$, where $n\wedge 2^{\alpha -2}=2^{\beta }$. Since $2^{\beta +1}>1$, $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )\ne \{1\}$ and $\phi$ is not bijective.

  Now we deal with the general case, where $m=p_1^{{\alpha }_1}\cdots p_l^{{\alpha }_l}.$ Since $\varphi (m)=\varphi (p_1^{{\alpha }_1})\cdots \varphi (p_l^{{\alpha }_l})$, and $k\wedge \varphi (m)=d>1$, there exists some index $j\in [[1,l]]$ such that $k\wedge \varphi (p_j^{{\alpha }_j})>1$.

  Using the proof of the particular case, there is some $x_j\in \mathbb{Z}∕p_j^{{\alpha }_j}\mathbb{Z}$ such that $x_j^k=1,x_j\ne 1$, so there is some integer $a_j$ such that $a_j^k\equiv 1(\mathit{mod}{p}_j^{{\alpha }_j})$ and $a_j\not\equiv 1(\mathit{mod}{p}_j^{{\alpha }_j})$. By the Chinese Remainder Theorem, there exists an integer $a$ such that

  $$a\equiv 1(\mathit{mod}{p}_i^{{\alpha }_i})\text{ if }1\le i\le l,i\ne j,a\equiv a_j(mod{p}_j^{{\alpha }_j}).$$

  Then $a\wedge p_i^{{\alpha }_i}=1$ for all indices $i$, thus $a\wedge m=1$, so $x={[a]}_m\in {(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$. Moreover, $a^k\equiv a_j^k\equiv 1(\mathit{mod}{p}_j^{{\alpha }_j})$, and $a^k\equiv a_i^k\equiv 1(\mathit{mod}{p}_i^{{\alpha }_i})$ if $i\ne j$, thus $a^k\equiv 1(\mathit{mod}m)$, and so $x^k=1$ in ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$. But $a_j\not\equiv 1(\mathit{mod}{p}_j^{{\alpha }_j})$, a fortiori $a\not\equiv 1(\mathit{mod}m)$, so $x\ne 1$. This shows that $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )\ne \{1\}$, thus $\phi$ is not bijective.

We have proved that

is bijective if and only if $k\wedge \varphi (m)=1$.

If $r_1,r_2,\dots ,r_n$ is a reduced system modulo $m$, where $n=\varphi (m)$, then ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}=\{{[r_1]}_m,{[r_2]}_m,\dots ,{[r_n]}_m\}$. Since $\phi$ is bijective, ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}=\phi ({(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}})=\{{[r_1^k]}_m,{[r_2^k]}_m,\dots ,{[r_n^k]}_m\}$, therefore $r_1^k,r_2^k,\dots ,r_n^k$ form a reduced residue system $(\mathit{mod}m)$.

Conversely, if $r_1^k,r_2^k,\dots ,r_n^k$ form a reduced residue system $(\mathit{mod}m)$, then $\phi ({(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}})=\{{[r_1^k]}_m,{[r_2^k]}_m,\dots ,{[r_n^k]}_m\}$, then $\phi$ is surjective. Since $\phi$ applies ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ on itself, where ${(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ is a finite set, $\phi$ is also injective. Therefore $\phi$ is bijective, and this implies that $k\wedge \varphi (m)=1$. □