[Math] Generators of integers modulo n under multiplication

abelian-groupsdiscrete mathematicsgroup-theory

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:

  1. We have already shown that 2 is a generator.
  2. $ord(Z^*_5) = 4$
  3. Using Lagrange's Theorem: $ord(3) \; | \; 4$ i.e. the order of the subgroup generated by $3$ divides the order of the full group.
  4. $2^3 \equiv 3 \; mod \;5 \;$ so $ \; ord(2^3) = ord(3)$
  5. $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:

  1. $3 \; ord(3) \equiv ord(2) \; mod \; 4$
  2. 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:

  1. 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?

  2. 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?

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

Best Answer

  1. $\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.)

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

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

Related Question