Why is $| \rm{Aut}(\mathbb{Z}_n) | = \varphi(n)$?

Question

If $G$ is a finite cyclic group of order $n$, prove that $| \rm{Aut}(G) | = \varphi(n)$, where $\varphi(n)$ is the Euler's totient function.

Can someone please help me with this?

Answer 1

Let's fix a generator $x\in\mathbb{Z}_n$, so that any $y\in\mathbb{Z}_n$ may be written in the form $$y=\underbrace{x+x+\cdots +x}_{m\text{ times}}$$ for some $m\in\mathbb{N}$.

If $\varphi:\mathbb{Z}_n\rightarrow \mathbb{Z}_n$ is a homomorphism, we then have that $$\varphi(y)=\varphi\left(\underbrace{x+x+\cdots +x}_{m\text{ times}}\right)=\underbrace{\varphi(x)+\varphi(x)+\cdots +\varphi(x)}_{m\text{ times}}.$$ For convenience, let's write $y=m\cdot x$ instead of $\underbrace{x+x+\cdots +x}_{m\text{ times}}$, so that $$\varphi(y)=\varphi(m\cdot x)=m\cdot \varphi(x).$$ Notice that this is a formula for $\varphi(y)$ for any $y\in\mathbb{Z}_n$ that only depends on $\varphi(x)$, which means that $\varphi$ is completely determined by the value of $\varphi(x)$.

Now, if we assume that $\varphi$ is an automorphism, we must have that $\varphi$ is bijective. In particular, this means that $\varphi$ maps $x$ to a generator of $\mathbb{Z}_n$. (why?) The number of automorphisms is then exactly the number of generators to whcih we can map $x$. How many of these are there?

Answer 2

Hint: Prove $G\cong \prod C_{p^{k}},p|\text{order}(G)$. Then try to tackle the $G=C_{p}$ case first.

Answer 3

Hints: Suppose $G = \langle a \rangle$ is a finite cyclic group generated an element $a$ of order $n$. You should be able to prove the following:

1) Any homomorphism $\phi : G \rightarrow G$ is completely determined by the value of $\phi(a)$. That is, once you know what $a' = \phi(a) \in G$ is, you know what $\phi(x)$ is for any $x \in G$.

2) In order for the homomorphism $\phi$ to be an isomorphism, it must be bijective and, in particular, $a' = \phi(a)$ must be an element of order $n$ in $G$.

3) There are $\phi(n)$ elements of order $n$ in $G$.

4) If $a' \in G$ is any element of order $n$, then there is a (unique by (1)) automorphism $\phi : G \rightarrow G$ with $\phi(a) = a'$.