Proving that $(\mathbb{Z}/23\mathbb{Z})^*=\langle{}5 \, \text{mod} \, 23\rangle$

Question

I don't quite understand what's going on here, and more primarily I don't see what they're asking either. We have to show that the set of all integers modulo 23 is equal to that of the set generated by 5 modulo 23 right? Why does the order of 5 mod 23 play a role here? Any help would be appreciated.

Answer 1

$\newcommand{\z}{\left(\mathbb Z \over 23 \mathbb Z\right)^*}$

I have to prove that one group is subset of the other, and vice versa.

That is one way of doing it. Not the way here.

Here, the fact that $\langle 5 \mod 23\rangle$ is a subset of $\z$ should be obvious. If this is not, then you need to look back at your definitions.

Now, just show they have the same size! That of course, will show that they are equal.

The size of $\z$ is $22$.

The order of $5$ mod $23$, is exactly the size of the group generated by the element $5$. If the order was equal to $22$, then this means that $\langle5 \pmod{23}\rangle$ has size $22$ and is a subgroup of a group of size $22$ itself, since $\z$ has size $22$. This would therefore show the equality that you want to show.

So all you need to show is that the order of $5$ mod $23$ is equal to $22$.

The idea of using the order is to simplify the process of showing equality. Yes, you will want to show that one is a subset of the other and vice-versa, but the reason why we have tools like order and so on is because they simplify things very well.

Finding the order of $5$ mod $23$ is tantamount, by Lagrange's theorem, to checking whether or not $5^d \equiv 1 \mod 23$ for every proper divisor $d$ of $22$, something far easier than showing explicitly that one is a subset of the other.