How to count generators for a cyclic group

Question

Show that there are $\varphi (n)$ generators for a cyclic group $G$ of order $n$. Give their form explicitly. Here $\varphi (n)$ is the Euler's function. I don't know what to do, please help.

Answer 1

Note that $G\cong\Bbb Z_n$, so we can suppose that $G=\{\bar0, \bar1,\ldots,\overline{n-1}\}$. I'll prove that these sentences are equivalent:

1. $\bar a$ is a generator of $G$.
2. For each integer $k$, $n$ divides $ak$ if and only if $n$ divides $k$
3. $\gcd(a,n)=1$

$1\Rightarrow2$: Suppose that $\bar a$ generates $G$. Let be $k$ any integer. If $n$ divides $ak$ then $k\bar a=0$. Since the order of $\bar a$ in $G$ is $n$, then $n$ divides $k$. Conversely, if $n$ divides $k$, it is clear that divides also $ak$.

$2\Rightarrow3$: Suppose that $p$ is a common prime divisor of $a$ and $n$. Then $n$ divides $\frac apn$, and, by $2$, $n$ divides $\frac np$. This contradiction tell us that $\gcd(a,n)=1$.

$3\Rightarrow1$: Suppose that $\bar a$ does not generate $G$. This means that there exists some positive integer $m<n$ such that $n$ divides $am$. By $3$, $n$ divides $m$, so $n=m$, a contradiction.

We can now establish that there are as many generators of $G$ as numbers coprimes with $n$ in the set $\{1,\ldots,n\}$, that is, $\varphi(n)$.