Ytukyg

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!

Suppose $G$ is a cylcic 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 Euclids 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}
Since 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 $kin{0,ldots,n-1}$ such that:

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

You can find an explicit expression:

$$varphi(n)=nprod_{pmid n}left(1-frac 1pright).$$

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)^1neq e\(g^b)^2neq e\(g^b)^3neq 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)=|{kmid 1leq k< n,gcd(k,n)=1}|$$