Why is $| \rm{Aut}(\mathbb{Z}_n) | = \varphi(n)$? 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?
 A: 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? 
A: 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'$.
A: Hint: Prove $G\cong \prod C_{p^{k}},p|\text{order}(G)$. Then try to tackle the $G=C_{p}$ case first. 
