Proof of the description of the automorphism group of a cyclic group

Proof

We compute with powers of a generator, and we use Bézout's identity to invert $\sigma_a$.

1. Let $G$ be a cyclic group of order $n$ with identity $e$, and let $g$ be a generator. By the definition of $\langle g \rangle$, each $x \in G$ is $g^k$ for some integer $k$.
2. If $g$ had infinite order, $\langle g \rangle$ would be infinite by the order of a cyclic subgroup. So $g$ has finite order $m$, and $|\langle g \rangle| = m$. Hence $g$ has order $n$.
3. Let $x = g^k \in G$. By the laws of exponents, $x^n = g^{kn} = (g^n)^k = e$.
4. For an integer $a$, let $\sigma_a \colon G \to G$, $\sigma_a(x) = x^a$. Let $x = g^i$ and $y = g^j$. The laws of exponents give $(xy)^a = (g^{i+j})^a = g^{ia + ja} = g^{ia} g^{ja} = x^a y^a$.
5. By step 4, each $\sigma_a$ is a group homomorphism from $G$ to $G$.
6. Let $a \equiv b$ modulo $n$, say $a = b + tn$ with $t \in \mathbb{Z}$. For $x \in G$, step 3 gives $x^a = x^b (x^n)^t = x^b$. So $\sigma_a = \sigma_b$.
7. For integers $a, b$ and $x \in G$, $\sigma_a(\sigma_b(x)) = (x^b)^a = x^{ab}$. So $\sigma_a \circ \sigma_b = \sigma_{ab}$.
8. Let $\gcd(a, n) = 1$. By Bézout's identity, there are integers $u, v$ with $au + nv = 1$. So $au \equiv 1$ and $ua \equiv 1$ modulo $n$.
9. By steps 6 to 8, $\sigma_a \circ \sigma_u = \sigma_u \circ \sigma_a = \sigma_1$, which is the identity of $G$. So $\sigma_a$ is bijective.
10. By steps 5 and 9, $\sigma_a$ is an automorphism of $G$ when $\gcd(a, n) = 1$. This is the first claim, and $\sigma_a$ lies in the automorphism group $\operatorname{Aut}(G)$.
11. By the units of Z/nZ are the residues coprime to n, the group of units $(\mathbb{Z}/n\mathbb{Z})^\times$ is the set of classes $a \bmod n$ with $\gcd(a, n) = 1$.
12. By steps 6, 10 and 11, the rule $\Phi(a \bmod n) = \sigma_a$ defines a map $\Phi \colon (\mathbb{Z}/n\mathbb{Z})^\times \to \operatorname{Aut}(G)$.
13. The product of the classes of $a$ and $b$ is the class of $ab$. By step 7, $\Phi$ of this product is $\sigma_{ab} = \sigma_a \circ \sigma_b$. So $\Phi$ is a homomorphism.
14. Let $\Phi(a \bmod n) = \Phi(b \bmod n)$. Then $g^a = g^b$, so $g^{a-b} = e$. By step 2 and the criterion for $g^n = e$, $n$ divides $a - b$. So $\Phi$ is injective.
15. Let $\alpha \in \operatorname{Aut}(G)$. By step 1, $\alpha(g) = g^a$ for some integer $a$.
16. For $k \ge 0$, $\alpha(g^k) = \alpha(g)^k$ by induction on $k$. The case $k = 0$ holds since homomorphisms preserve the identity, and $\alpha(g^{k+1}) = \alpha(g^k) \alpha(g)$.
17. For $k > 0$, $\alpha(g^{-k}) = \alpha((g^{-1})^k) = \alpha(g^{-1})^k = (\alpha(g)^{-1})^k = \alpha(g)^{-k}$, since homomorphisms preserve inverses.
18. By steps 16 and 17 and the laws of exponents, $\alpha(g^k) = (g^a)^k = g^{ak} = \sigma_a(g^k)$ for each integer $k$. By step 1, $\alpha = \sigma_a$.
19. Since $\alpha$ is surjective, $g = \alpha(g^k) = g^{ak}$ for some integer $k$. So $g^{ak - 1} = e$, and by the criterion used in step 14, $ak - 1 = nt$ for some integer $t$.
20. Thus $ak - nt = 1$. Each common divisor of $a$ and $n$ divides $1$, so the greatest common divisor of $a$ and $n$ is $1$.
21. By steps 18 to 20, $\alpha = \Phi(a \bmod n)$. So $\Phi$ is surjective.
22. By steps 13, 14 and 21, $\Phi$ is a bijective homomorphism, that is, an isomorphism from $(\mathbb{Z}/n\mathbb{Z})^\times$ to $\operatorname{Aut}(G)$.