# How to find a generator of a cyclic group?

A cyclic group is a group that is generated by a single element. That means that there exists an element $g$, say, such that every other element of the group can be written as a power of $g$. This element $g$ is the generator of the group.

Is that a correct explanation for what a cyclic group and a generator are? How can we find the generator of a cyclic group and how can we say how many generators should there be?

Finding generators of a cyclic group depends upon order of group. If order of a group is 8 then total number of generators of group G are equal to positive integers less than 8 and co-prime to 8. The numbers 1,3,5,7 are less than 8 and co-prime to 8, therefore if a is generator of G, then a^3,a^5,a^7 are also generators of G. Hence there are four generators of G. Similarly you can find generators of groups of order 10,12,6 etc.

• Can you explain this comment about $C_8$ "Cycles[{{1, 2, 3, 4, 5, 6, 7, 8}}] is the generator for the cyclic group of size 8, because it corresponds to the simple permutation on the set {1, 2, 3, 4, 5, 6, 7, 8} in which 1 -> 2, 2 -> 3, etc. Multiplying that permutation by itself yields the first of the two Cycles at the end of your post, which I think makes good sense: every element moves two elements to the right" here? So the cycle is generator or 1,3,5,7? – hhh Feb 14 '16 at 12:12

Your explanation sounds good to me.

In the general case, finding the generator of a cyclic group is difficult. For example, I believe there is no fast algorithm to find a generator for the multiplicative group $(\mathbb Z/p^k\mathbb Z)^\times$ when $p$ is a large prime. But much of the time when you work with a cyclic group you will also naturally know of a generator.

If your cyclic group has order $n$, I claim that there will be one generator for every number between $1$ and $n-1$ (inclusive) that is relatively prime to $n$: in other words, there are $\varphi(n)$ generators, where $\varphi$ is Euler's totient function. Why is my claim correct? Suppose $g$ is a generator for the group, so that $g$ has order $n$. It is a fact, which I encourage you to prove if you have not encountered it, that for an integer $m$ between $1$ and $n$ the order of $g^m$ is $n/(m,n)$, where $(m,n)$ is the greatest common denominator of $m$ and $n$. So for $g^m$ to be a generator -- or equivalently, for $g$ to have order $n$ -- it is both necessary and sufficient that $m$ be relatively prime to $n$. And every element of the group has the form $g^m$ for some $m$. Hence there are $\varphi(n)$ generators.

If your cyclic group has infinite order then it is isomorphic to $\mathbb Z$ and has only two generators, the isomorphic images of $+1$ and $-1$. But every other element of an infinite cyclic group, except for $0$, is a generator of a proper subgroup which is again isomorphic to $\mathbb Z$.

• is it true that the highest common factor between the generator g and the order n is 1? – user3543192 May 8 '14 at 17:32
• Do you mean the order of $g$? Because $g$ is not a number (in general) it doesn't make sense to talk about the highest common factor of $g$ and $n$. – user134824 May 8 '14 at 17:42
• If n is prime, then every element of g is relatively prime to n. But it isnt true that they are all generators is it? – Paul Sep 18 '16 at 14:46
• @Paul Every element of a (cyclic) group of prime order, except for the identity, does generate the whole group. If this seems strange to you, I encourage you to work out a few examples in groups of small order, like $C_3$, $C_5$, and $C_7$. – user134824 Sep 18 '16 at 23:04

I list computational methods in group theory. The $C_8$ example by Sharma is visualised in Mathematica below. Python one-liners are convenient way to verify generator guesses, in the case of multilpicative group just change one $*$ (multiplication) to $**$ (power).

Python

For example to check that 1 and 5 generate $(\mathbb Z_6,+)$ and all relative prime numbers $\{1,3,5,7\}$ generate $(\mathbb Z_8,+)$

>>> [(1*x)%6 for x in range(20)]
[0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1]
>>> [(5*x)%6 for x in range(20)]
[0, 5, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 5]

>>> [(3*x)%8 for x in range(20)]
[0, 3, 6, 1, 4, 7, 2, 5, 0, 3, 6, 1, 4, 7, 2, 5, 0, 3, 6, 1]
>>> [(5*x)%8 for x in range(20)]
[0, 5, 2, 7, 4, 1, 6, 3, 0, 5, 2, 7, 4, 1, 6, 3, 0, 5, 2, 7]
>>> [(7*x)%8 for x in range(20)]
[0, 7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5]


Mathematica (source)

On Sharma's example: the $C_8$ isomorphic to $(\mathbb Z_8,+)$ group visualised below.   Other and discussion

1. CAS programs for the first course in abstract algebra?

2. https://math.stackexchange.com/questions/1653673/software-for-generators-of-different-structures-such-mathbb-z-5-and-such-as

3. How to declare a $(\mathbb Z_8,+)$ in Mathematica?

4. Maple has Generators(group) command but you need to specify the group somehow, unsolved.

1.) For large group orders it is no suitable to explicitly evaluate all powers of an optional generator to prove the element's order.

2.) The fact, that a multiplicative cyclic finite group is isomorphic to some additive finite subgroup in Z is not helpful, as the isomorphism is defined exactly by a generator.

Criterion: An element g of multiplicative group of order (p-1) in Z/pZ with prime p is a generator, iff for each prime factor q in the factorization of (p-1)
g^((p-1)/q) <> 1
holds.

This excludes g from being generator of a real subgroup and reduces the problem to factorization of (p-1).

Your explanation is correct. If the group is finite, then there is some order to $g$, i.e. $g^n=e$, and $n$ is minimal. Then $g^m$ is a generator, for each $m$ that satisfies $\gcd(m,n)=1$. Hence there are $\phi(n)$ generators, where $\phi$ denotes the Euler totient. Generally there are lots of generators, so it's not that hard to find one. Just take random elements and compute their orders.

• why we are saying euler phi function gives the number of generators as in case of group {1,3,5,7} modulo 8 operation (multiplicative group of order 8) ?? we are getting 4 as result but only 3,5,7 are generators..am i right? Can you clear that confusion? – ViX28 Aug 7 '16 at 13:40

That sounds right. The number of generators depends on the order of the group. The infinite cyclic group $\mathbb{Z}$ has two generators, $\pm 1$. A finite cyclic group of order $k$ has $\phi(k)$ generators where $\phi$ is the Euler phi function.

Yes, your explanation is fine. Let $G$ be your cyclic group.

1. If $G$ is infinite, then $G\cong \mathbb Z$, which has two generators, $\pm \,1$.
2. If $G$ is finite, of order $n$, then $G\cong \mathbb Z/n\mathbb Z$. If you have a generator $g\in G$ (for instance: the image of the class of $1$ under an isomorphism $\mathbb Z/n\mathbb Z\to G$), then $g^i\in G$ is a generator if and only if $(n,i)=1$. Hence there are exactly $\phi(n)$ generators in a finite cyclic group.

Every cyclic group is isomorphic to either $\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z}$ if it is infinite or finite. If it is infinite, it'll have generators $\pm1$. If it is finite of order $n$, any element of the group with order relatively prime to $n$ is a generator. The number of relatively prime numbers can be computed via the Euler Phi Function $\phi(n)$.

Thus for an arbitrary group $G$, you can define an isomorphism to $\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z}$ and those elements that map to the generators of $\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z}$ are the generators of $G$. That is, the orders of the elements in $G$ must be relatively prime to the degree of $G$ for them to be a generator.