# How to find all generators for a cyclic group of order $n$?

Let us say I have to find all the generators for modulo $$p=7$$. That must mean that:

$$\mathbb{Z}_7 = \mathbb{Z}^*_7 = \{1,2,...,7-1\}$$

So now I need to get all the generators for $$7$$. Now I choose randomly from the group $$\mathbb{Z}_7$$ and pick the number $$3$$. So if $$3^n$$ for $$n = \{1,2,\dotsc,7-1\}$$ can generate all elements from $$\mathbb{Z}_7$$, the number is considered a generator.

$$3^1 \pmod 7\equiv 3\\ 3^2 \pmod 7\equiv 2\\ 3^3 \pmod 7\equiv 6\\ 3^4 \pmod 7\equiv 4\\ 3^5 \pmod 7\equiv 5\\ 3^6 \pmod 7\equiv 1$$

Now I have found one generator. Someone claimed one can find all generators in the group with a faster method, when one already has one generator. Can someone please show me how that works?

• How can $\Bbb Z_7$ be the same as $\Bbb Z_7^*$? – Bernard Apr 1 at 21:32
• Hi and welcome! Your question is not really clear. Are you finding a method to discover all the generator of $\mathbb Z_7^*$ having found a generator of this group? – Menezio Apr 1 at 21:36
• @Bernard hi, I always thought they were the same? Aren't they the same? – Heinrich Jensen Apr 1 at 21:42
• @Menezio hi, I'm just trying to find all the generators in the cyclic group as fast as possible. I've read a lot of different things online, but I would just love when someone could go through my example and explain how they find the generators. The fastest method I have found is when you find a generator and then, so it is claimed online, it is easy to find all the other elements. KR – Heinrich Jensen Apr 1 at 21:44
• No: the first is the field with $7$ elements, the other is its set of units (non-zero elements). Only the latter is a multiplicative group, and it has order $6$. – Bernard Apr 1 at 21:45

We know that $$\mathbb Z_7^*$$ is a group with multiplication, and it is cyclic with generator the element $$3$$ as you show. To find the other generators you can do this: since $$\mathbb Z_7$$ has got six elements and it is cyclic, then it's isomorphic to $$\mathbb Z_6$$ and the isomorphism is the following (try to show this as exercise): $$$$\varphi:(\mathbb Z_6,+) \longrightarrow (\mathbb Z_7^*, \cdot), \quad i\longmapsto 3^i$$$$ Now, since $$\varphi$$ is an isomorphism, it maps generators in generators (and vice-versa). The generators of $$\mathbb Z_6$$ are just $$1$$ and $$5$$ (numbers coprime with $$6$$ smaller than $$6$$), so the generators of $$\mathbb Z_7^*$$ are $$\varphi(1)=3^1=3$$ and $$\varphi(5)=3^5=5$$ modulo $$7$$.

• Thank you so much! Now I understand it! Last question: it is the correct way I find the first generator (the three) which you use to calculate 3 and 5? Or is there a faster method? – Heinrich Jensen Apr 1 at 21:58
• I don't know a general method to find the first generator, so it is ok what you have done – Menezio Apr 1 at 22:04

Here it is: in a cyclic group of order $$n$$, with generator $$a$$, all subgroups are cyclic, generated (by definition) by some $$a^k$$, and the order of $$a^k$$ is equal to $$\frac n{\gcd(n,k)}.$$ Therefore $$a^k$$ is another generator of the group if and only if $$k$$ is coprime to $$n$$.

• Hi, thanks. So I find the co-primes to three that are elements of the cyclic group? Which in this case would be 2, 4, 5? And then I say 7/gcd(7,2), 7/gcd(7,4) and 7/gcd(7,5)? And the result(s) will be the other generators? – Heinrich Jensen Apr 1 at 21:53
• No quite: the exponents which are coprime to $6$. This makes much less. Further, it is very long to check, you indeed obtain generators. – Bernard Apr 1 at 21:58