---
tag: 6PW2GW276F
kind: proof
name: Proof of the description of the automorphism group of a cyclic group
msc: [20F28]
proves: 0G4C8SJ6PV
uses: [0B85Q41RP6, 0YT586TKXF, 031M8HX7DA, 00DRK90Z6K, 0HV9Y7WG5R, 0TPW25CBN6, 0DQVHMYAGA, 02WF878BH1, 01VG2A0BHW, 0CWXCWP0Y0, 08FHNR8Z5D, 0GXNHEHQNA, 0F5QC101Q7, 08FKQD7NJ3, 085PND4KNT]
sources:
  - url: https://en.wikipedia.org/wiki/Cyclic_group
    locator: Endomorphisms
---

## 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|0B85Q41RP6]]. By the [[definition of $\langle g \rangle$|0YT586TKXF]], 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|031M8HX7DA]]. 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|00DRK90Z6K]], $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|0HV9Y7WG5R]] from $G$ to $G$.
6. Let $a \equiv b$ [[modulo $n$|0TPW25CBN6]], 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|0DQVHMYAGA]], 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|01VG2A0BHW]].
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|0CWXCWP0Y0]] $\operatorname{Aut}(G)$.
11. By [[the units of Z/nZ are the residues coprime to n|0GXNHEHQNA]], the [[group of units|08FHNR8Z5D]] $(\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$|0F5QC101Q7]], $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|08FKQD7NJ3]], 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|02WF878BH1]] 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|085PND4KNT]] from $(\mathbb{Z}/n\mathbb{Z})^\times$ to $\operatorname{Aut}(G)$.

## Idea

Every automorphism is fixed by where it sends the generator $g$, and it must send $g$ to some power $g^a$. Then it is the power map $x \mapsto x^a$, which only depends on $a$ modulo $n$. The power map is invertible exactly when $a$ is invertible modulo $n$, and composing power maps multiplies the exponents.