[Math] Cyclic Group Generators of Order $n$

abstract-algebragroup-theory

How many generators does a cyclic group of order $n$ have? I know that a cyclic group can be generated by just one element while using the operation of the group. I am having trouble coming up with the generators of a group of order $n$.

Any help would be great! Thanks!

Best Answer

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.

Related Question