Cyclic Group Generators of Order $n$

Suppose $G$ is a cyclic group of order $n$, then there is at least one $g \in G$ such that the order of $g$ equals $n$, that is: $g^n = e$ and $g^k \neq e$ for $0 \leq k < n$. Let us prove that the elements of the following set $$\{g^s \: \: \vert \: \: 0 \leq s < n, \text{gcd}(s,n) = 1\}$$ are all generators of $G$.

In order to prove this claim, we need to show that the order of $g^s$ is exactly $n$. Suppose that it is $k$, where $0 < k \leq n$. We have that

\begin{equation} (g^s)^n = (g^n)^s = e \end{equation}

and therefore we must have that $k$ divides $n$. Let us now prove that $n$ divides $k$. Because of Euclid's lemma, there are $q, r \in \mathbb{N}$ such that $k = qn + r$, where $0 \leq r < n$. We have that \begin{equation} e = (g^s)^k = (g^s)^{qn} \cdot (g^s)^r = (g^s)^r = g^{sr}. \end{equation}

Because the order of $g$ is $n$, we must have that $n$ divides $sr$. However, because $\text{gcd}(s,n) = 1$, we must have that $n$ divides $r$, but this would mean that either $n \leq r$ (impossible because of $0 \leq r < n$) or $r = 0$. Since $r = 0$ is the only possibility, we have that $k = qn$, so $n$ divides $k$ and therefore we must have that $k = n$. So $g^s$ is a generator of $G$ in the case that $\text{gcd}(s,n) = 1$.

This proves the claim made in the answer of E.Joseph, that there are exactly $\varphi(n)$ generators (since $\varphi(n)$ is exactly the number of elements which are coprime to $n$). It also gives you an idea on how to find all generators, given that you know one generator.

Let $g$ be a generator of $G$. Let $g^m$ be another generator, with $2 \le m \le n-1$. This means that $(g^m)^k \ne e$ for all $1 \le k \le n-1$, i.e. $n \nmid mk$ for all $1 \le k \le n-1$.

If $\gcd(n,m) = d > 1$ then, letting $m = da$ and $n = db$, the above condition becomes $b \nmid ak$ for all $1 \le k \le n-1$. Since $d>1$, it follows that $b<n$, so if you choose $k=b$ you get $b \mid ab$, which is contradicts the assumption that $n \nmid mk$ for all $1 \le k \le n-1$. It follows that, necessarily, $\gcd(n,m) = 1$.

Let us show that the condition $\gcd(m,n) = 1$ is also sufficient for $g^m$ to be a generator. Assume there exist $2 \le k \le n-1$ with $(g^m)^k = e$. Since $\gcd(m,n) = 1$, by Bézout's theorem there exist $s,t \in \Bbb Z$ such that $sm + tn = 1$, which implies $smk + tnk = k$, whence it follows that

$$e = e^s = (g^{mk})^s = g^{mks} = g^{k - tnk} = g^k (g^n)^{-tk} = g^k ,$$

so $g^k = e$, which contradicts the fact that $g$ is a generator.

We have discovered that in order for $g^m$ to be a generator, it is necessary and sufficient that $\gcd(m,n)=1$, for $2 \le m \le n-1$. How many numbers coprime with $n$ do we have in $\{2, 3, \dots, n-1\}$? By definition, $\varphi(n)-1$, where $\varphi$ is Euler's totient function. We have a "$-1$" because we start counting from $m=2$; taking into consideration that $g$ is a generator, too, and it corresponds to $m=1$, we get a total of $\varphi(n)$ generators.

A cyclic group of order $n$ has exactly $\varphi(n)$ generators where $\varphi$ is Euler's totient function.

This is the number of $k\in\{0,\ldots,n-1\}$ such that:

$$\gcd(k,n)=1.$$

You can find an explicit expression:

$$\varphi(n)=n\prod_{p\mid n}\left(1-\frac 1p\right).$$

Suppose $g$ is a generator of $G$, then any element in $G$ may be written $g^b$. Now we only have to figure out which $b$'s make $g^b$ a generator.

If $g^b$ is a generator, then $(g^b)^n=g^{bn}=e$, and $$(g^b)^1\neq e\\(g^b)^2\neq e\\(g^b)^3\neq e\\\dots\\(g^b)^{n-1}\neq e$$ This means that $b,n$ have no common factor, that is $\gcd(b,n)=1$. So every $b$, for which $\gcd(b,n)=1$, makes $g^b$ a generator of $G$. The number of generators is therefore $$\phi(n)=|\{k\mid 1\leq k< n,\gcd(k,n)=1\}|$$