Exercise 2.3.26 ($\mathrm{Aut}(Z_n) \simeq (\mathbb{Z}/n\mathbb{Z})^\times$)

Proof. Let $Z_n$ be a cyclic group of order $n$ and for each integer $a$ let

(a)

Suppose that $a\wedge n=1$. Then

• ${\sigma }_a$ is a homomorphism: Since $Z_n$ is abelian, for all $x,y\in Z_n$,

  $${\sigma }_a(\mathit{xy})={(\mathit{xy})}^a=x^a{y}^a={\sigma }_a(\mathit{xy}).$$

• ${\sigma }_a$ is injective: Since $a\wedge n=1$, there are integers $u,v$ such that $\mathit{au}+\mathit{nv}=1$. Since $x^n=1$ for all $x\in G$,

  $${\sigma }_a(x)=1\Rightarrow x^a=1\Rightarrow x=x^{\mathit{au}+\mathit{nv}}={(x^a)}^u{(x^n)}^v=1,$$

  so $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )\subseteq \{1\}$ (and of course $\{1\}\subseteq \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )$), thus $\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )=\{1\}$ and $\phi$ is injective.

• Since ${\sigma }_a:Z_n\to Z_n$ is injective, and $Z_n$ is a finite set, then ${\sigma }_a$ is surjective. (Alternatively, we may use the proof of Exercise 25.)

This shows that ${\sigma }_a\in \mathrm{Aut}(Z_n)$.

Conversely, suppose that $d=a\wedge n\ne 1$. Since $d\mid n$, there is an element $g\in G$ of order $d$ (Theorem 7). Then $g^d=1$, and since $d\mid a$, $g^a=1$, thus $g\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )$, where $|g|=d>1$, so $g\ne 1$, therefore $\ker <!--\; FUNCTION\; APPLICATION\; -->({\sigma }_a)\ne \{1\}$. Hence ${\sigma }_a$ is not injective, and a fortiori ${\sigma }_a$ is not an automorphism.

To conclude,

$$a\wedge n=1⟺{\sigma }_a\in \mathrm{Aut}(Z_n).$$

(b)

If $a\equiv b(\mathit{mod}n)$ then $b=a+\mathit{\lambda n}$ for some integer $\lambda$. For all $x\in Z_n$, $x^n=1$, so $${\sigma }_b(x)=x^b=x^{a+\mathit{\lambda n}}=x^a{(x^n)}^{\lambda }=x^a={\sigma }_a(x),$$

so ${\sigma }_a={\sigma }_b$.

Conversely, if ${\sigma }_a={\sigma }_b$, then for all $x\in G$, $x^a=x^b$. Since $G$ is cyclic, there is some $g\in Z_n$ such that $Z_n=⟨g⟩$, where $g$ of order $n$ satisfies $g^a=g^b$, thus $g^{a-b}=1$. Therefore $n\mid b-a$, so $a\equiv b(\mathit{mod}n)$.

For all integers $a,b$,

$${\sigma }_a={\sigma }_b⟺a\equiv b(\mathit{mod}n).$$

(c)

Let $\tau$ be some automorphism of $Z_n$. Consider some fixed generator $g$ of $Z_n$, so that $Z_n=⟨g⟩$. Since $\tau (g)\in Z_n=⟨g⟩$, there exists an integer $a$ such that $\tau (g)=g^a$. Let $x$ be any element of $Z_n$. Then $x=g^k$ for some integer $k$, thus $$\tau (x)=\tau (g^k)=\tau {(g)}^k={(g^a)}^k=g^{\mathit{ak}}={(g^k)}^a=x^a={\sigma }_a(x).$$

Since this is true for every $x\in Z_n$, $\tau ={\sigma }_a$.

Every automorphism of $Z_n$ is equal to ${\sigma }_a$ for some integer $a$.

(d)

For every $x\in Z_n$, $$({\sigma }_a\circ {\sigma }_b)(x)={(x^b)}^a=x^{\mathit{ab}}={\sigma }_{\mathit{ab}}(x),$$

so

$${\sigma }_a\circ {\sigma }_b={\sigma }_{\mathit{ab}}.$$

Consider the map

$$\phi \{\begin{array}{ccc}\hfill {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}\hfill & \hfill \text{→}\hfill & \mathrm{Aut}(Z_n)\hfill \\ \hfill \bar{a}\hfill & \hfill \mapsto \hfill & {\sigma }_a\hfill \end{array}$$

• $\phi$ is well defined: If $a\equiv b(\mathit{mod}n)$, then ${\sigma }_a={\sigma }_b$ by part (b). Moreover, for every $\bar{a}\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$, where $a\in \mathbb{Z}$, then $a\wedge n=1$, thus ${\sigma }_a\in \mathrm{Aut}(Z_n)$ by part (a).

• $\phi$ is a homomorphism: For all $a,b\in Z_n$,

  $$\phi (a)\phi (b)={\sigma }_a{\sigma }_b={\sigma }_{\mathit{ab}}=\phi (\mathit{ab}).$$

• $\phi$ is surjective: if $\tau$ is any automorphism of $Z_n$, there exists by part (c) an integer $a$ such that $\tau ={\sigma }_a$. Moreover, since ${\sigma }_a=\tau$ is an automorphism, $a\wedge n=1$ by part (a), thus $\bar{a}\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$ and $\tau =\phi (\bar{a})$.
• $\phi$ is injective: If $\phi (\bar{a})=\phi (\bar{b})$, where $\bar{a},\bar{b}\in {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}$, then ${\sigma }_a={\sigma }_b$, therefore $a\equiv b(\mathit{mod}n)$ by part (b), so $\bar{a}=\bar{b}$.

This shows that $\phi$ is an isomorphism, and

$$\mathrm{Aut}(Z_n)\simeq {(\mathbb{Z}∕\mathit{n\mathbb{Z}})}^{\text{×}}.$$

(So $\mathrm{Aut}(Z_n)$ is an abelian group of order $\phi (n)$).