Generators of integers modulo n under multiplication I was shown an alternate way of finding the generators of $Z^*_5 = Z_5 - \{0\}$ (i.e. the integers greater than $0$ modulo $n$) using Lagrange's Theorem opposed to calculation by hand. The steps are thus:


*

*We have already shown that 2 is a generator.

*$ord(Z^*_5) = 4$ 

*Using Lagrange's Theorem: $ord(3) \; | \; 4$ i.e. the order of the subgroup generated by $3$ divides the order of the full group.

*$2^3 \equiv 3  \; mod \;5 \;$ so $ \; ord(2^3) = ord(3)$

*$3^{ord(3)} \equiv 2^{3ord(3)}  \equiv 1 \; mod \; 5 $


Thus far I understand entirely what is going on. However, the next two steps, whilst I understand the maths i.e. I can work out the numbers I am not entirely sure why they are performed:


*$3 \; ord(3) \equiv ord(2) \; mod \; 4$ 

*As $3$ and $4$ are co-prime, we can deduce that $ ord(3) \equiv 4 \equiv ord(Z^*_5)$ i.e. $3$ is a generator of $Z^*_5$.


So I have 3 questions:


*

*In the case of step 6 my question is: why is this significant? Why $mod \; 4 \;$ and not $ \; mod \;5  \;$ ? How does this help us find the generator?

*In the case of step 7 my question is: why does the fact they are co-prime imply this and why did we have to do all the prior working? Is this a property of such groups?

*If a number is co-prime with the order of the group is it always a generator?
Thank you for any answers, I've been looking through some textbooks but I couldn't find a comprehensive discussion of this particular case.
 A: *

*$\DeclareMathOperator{\ord}{ord}$The order of 2 is four (it's a generator.) So the fact that 2 raised to $3\ord(3)$  is 1 (step 5) tells us that $3\ord(3)$ is equivalent to 4 mod 4 (because the powers of 2 repeat every four steps.)

*If $3x$ is a multiple of 4, then $x$ is already a multiple of 4, because 3 and 4 are coprime.

*No. For instance, 1 is always coprime to the order of the group, but never a generator. Or take 3, which is coprime to $\ord(Z_{11}^*)$, but is not a generator.
The more general conclusion is rather that, if $a$ is a generator and $k$ is coprime to $\ord(a)$, then $a^k$ is also a generator.
In fact, given a generator $a$, $a^k$ is a generator iff $k$ is coprime to $\ord(a)$.
The way I would have presented the whole argument is more like this:
Suppose $a$ is a generator of a group $G$ of order $m$. Then each element of $G$ is $a^k$ for some $k$.
If $n = \ord(a^k)$, then $a^{kn} \equiv 1 \equiv a^m$, so $kn \equiv m \pmod m$. That is, $m \mid kn$.
If $k$ is relatively prime to $m$, then in fact $m \mid n$; but by Lagrange's theorem, $n \mid m$, so in this case $n = m$ and $a^k$ is a generator.
(On the other hand, if $k$ is not relatively prime to $m$, then $m \mid kd$ for some $d < m$. But then $a^{kd} \equiv 1$, so $n \mid d$, so $n \neq m$, so $a^k$ is not a generator.)
