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?
 A: 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$.
A: 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):
\begin{equation}
\varphi:(\mathbb Z_6,+) \longrightarrow (\mathbb Z_7^*, \cdot), \quad i\longmapsto 3^i
\end{equation}
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$.
