How many generator has a cyclic group of order n? [duplicate]

I need to find how many generators has a cyclic group $G=<g>$ of order $n$. I know that I have to prove that if $G$ is a cyclic group with order $n$, then the number of generators of $G$ is $\phi(n)$. But I don't know how can I prove that.

I already know that $<g^k>=<g^{gcd(k,n)}>$, so the generators of $G$ will be $g^k$ where $gcd(k,n)=1$

Solution 1:

$G$ is a finite group which is cyclic with order $n$. So, $G=<g>$. So any element is of the form $g^{r}$; $0\leq r\leq n-1$. Now you already know $o(g^{k})=\frac{o(g)}{gcd(n,k)}$. Now some $g^{k}$ is a generator iff $o(g^{k})=n$ iff $(n,k)=1$. If S is the set of generators, $S=\{\ g^{r}|1<r\leq n-1 \;\; and \;\; (n,r)=1 \}\ $.

$|S|=\phi(n)$, which is Euler's phi function, is the number of positive integers relatively prime to $n$ and less than $n$. There is a formula to find this quantity that you can easily find out.