# Cyclic Group Generators of Order $n$

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!

• Why would $n$ not be finite? Commented Feb 21, 2017 at 19:45

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

$$$$(g^s)^n = (g^n)^s = e$$$$

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 $$$$e = (g^s)^k = (g^s)^{qn} \cdot (g^s)^r = (g^s)^r = g^{sr}.$$$$

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.

• I was writing my answer when you posted yours; since they are very similar, I thought about deleting mine, but in the end I shall leave it here simply for the sake of the time wasted to type it. Anyway, +1 for your work. Commented Feb 21, 2017 at 20:44
• No I would totally leave it! First of all: This was an exercise in my algebra class, so it gives me another way to solve this exercise (thanks for that!). Second: your answer also shows that it is an 'if and only if' condition that $\text{gcd}(s,n) = 1$ ($s$ in my solution being your $m$). Commented Feb 21, 2017 at 20:52
• Student, what do you think of my proof please?
– BCLC
Commented Aug 28, 2018 at 6:03
• I didn't understand why is it must that $n$ divides $r$? @Student Commented Oct 30, 2018 at 16:09
• @J.Doe $n$ divides $sr$, but has no common primedivisors with $s$. Therefore, all primedivisors of $n$ are primendivisors of $r$ and hence $n$ must divide $r$. Commented Oct 30, 2018 at 17:34

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.

• Alex M., what do you think of my proof please?
– BCLC
Commented Aug 28, 2018 at 6:03

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).$$

• E. Joseph, what do you think of my proof please?
– BCLC
Commented Aug 28, 2018 at 6:03

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\}|$$

• 1. If g^b is a generator, it means every element of G is equal to some (g^b)^k. Why does that mean that (g^b)^n equals e? 2. What is the reasoning behind “this means that b,n have no common factors? Thanks! Commented Oct 30, 2018 at 10:15
• @ikoikoia 1. The order of the group is $n$, which means that $a^n$ for all $a\in\Bbb Z_n$. 2. If $b,n$ had some common factor, say $d=\gcd(b,n)$, then we could write $b=db',n=dn'$. And so $bn'=nb'$ is divisible by $n$. Since $n'<n$ we could only generate $n'$ elements of $\Bbb Z_n$, namely $g^b, (g^b)^2, \dots, (g^b)^{n'}=e$ Commented Oct 30, 2018 at 11:20

Let $$G$$ be a group of order $$n$$.
Let $$g$$ be a generator of $$G$$.
Then, $$G = \{e, g, g^2, \cdots, g^{n-1}\}$$.
If $$h = g^i$$ is a generator of $$G$$, then, $$h^k = g^{k i} = g$$ for some $$k \in \mathbb{Z}$$.
So, $$g^{k i - 1} = e$$.
So, $$k i - 1 = (-l) n$$ for some $$l \in \mathbb{Z}$$.
$$\therefore k i + l n = 1$$.
So, $$gcd(i, n) = 1$$.

Conversely, if $$\gcd(i, n) = 1$$, then, there exist $$k, l \in \mathbb{Z}$$ such that $$k i + l n = 1$$.
$$g = g^1 = g^{k i + l n} = g^{k i} (g^n)^l = g^{k i} e^l = g^{k i} e = g^{k i}$$.
So, $$g^i$$ is a generator of $$G$$.

$$\therefore$$ There exist $$\#\{i \in \{0, 1, \cdots, n-1\} | \gcd(i, n) = 1\}$$ generators in $$G$$.

• Why on the 'Conversely' part you know that $g^i$ generates $G$ at the end? I can't follow the last implication. Commented Oct 27, 2020 at 18:42
• @xtreyreader $g=(g^i)^k,g^2=(g^i)^{2k},g^3=(g^i)^{3k},\cdots,g^{n-1}=(g^i)^{(n-1)k},e=g^n=(g^i)^{nk}.$ So $g^i$ is also a generator of $G$. Commented Oct 28, 2020 at 8:32