Theorem 1   The automorphism group of the cyclic group $\Ints/n\Ints$ is $\UI{n}$ , which is of order $\phi(n)$ (here $\phi$ is the Euler totient function).

Proof. Choose a generator $x$ for $\Ints/n\Ints$ . If $\rho\in \Aut(\Ints/n\Ints)$ , then $\rho(x) = x^a$ for some integer $a$ (defined up to multiples of $n$ ); further, since $x$ generates $\Ints/n\Ints$ , it is clear that $a$ uniquely determines $\rho$ . Write $\rho_a$ for this automorphism. Since $\rho_a$ is an automorphism, $x^a$ is also a generator, and thus $a$ and $n$ are relatively prime ¹. Clearly, then, every $a$ relatively prime to $n$ induces an automorphism. We can therefore define a surjective map$$ \Phi : \Aut(\Ints/n\Ints) \to \UI{n}: \rho_a\mapsto a\pmod n$$ $\Phi$ is also obviously injective, so all that remains is to show that it is a group homomorphism. But for every $a,b\in\UI{n}$ , we have$$ (\rho_a\circ\rho_b)(x) = \rho_a(x^b) = (x^b)^a = x^{ab} = \rho_{ab}(x)$$ and thus$$ \Phi(\rho_a\circ\rho_b) = \Phi(\rho_{ab}) = ab\pmod n = \Phi(\rho_a)\Phi(\rho_b)$$