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?
Best Answer
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$.