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 the order of the group. If the order of a group is $$8$$ then the total number of generators of group $$G$$ is 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 the 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

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

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.

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.