Orders of elements and subgroups in a cyclic group

Question

I was trying to understand more about orders of elements in a cyclic group $G$ and non-trivial subgroups that were generated from a cyclic group $G$ and so read the following example: Non trivial subgroups in cyclic group G.

But I do not how one would find trivial and non-trivial groups for say a group $G = \mathbb{Z}^{\times}_{73}$. I get that you have to do $73-1$, as $73$ is prime so you are left with $72$ and then we find all the factors of $72$ which are $\{1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72\}.$

After this, we have to try and find numbers that are not $1 \text{ mod } 72$. I do not where to start in terms of finding the subgroups like do I start with $2^1 \text{ mod } 72, 2^2 \text{ mod } 72, 2^3 \text{ mod } 72, \dots,2^{72} \text{ mod } 72$ to find the subgroups.

Like is there a way of finding non trivial subgroups in a cyclic group?

Answer 1

First find a generator $g$ of $G$ i.e. an element of $G$ that has order $|G|$. If $G=\mathbb{Z}_p$ for a prime $p$ then a generator of $G$ is called a primitive root of $p$.

Each element of $G$ can be expressed as $g^k$ for some integer $1 \le k \le |G|$. And $g^k$ will generate a sub-group $<g^k>$ of $G$ with elements $\{g^k, g^{2k}, g^{3k}, \dots \}$. Eventually we reach a multiple of $k$ which is also a multiple of $|G|$ i.e. $nk=m|G|=\text{LCM}(k,|G|)$. At this point we have

$g^{nk}=g^{m|G|}=(g^{|G|})^m=e^m=e$

where $e$ is the identity element in $G$ (we know that $g^{|G|}=e$ because $g$ has order $|G|$). So $<g^k>$ has $n$ elements.

We also know that

$(nk)\text{GCD}(k,|G|)=\text{LCM}(k,|G|)\text{GCD}(k,|G|)=k|G|$

so the order of $<g^k>$ is $\frac{|G|}{\text{GCD}(k,|G|)}$.

For example, if $|G|=72$ then the order of $<g^{15}>$ is $\frac{72}{\text{GCD}(15,72)}=\frac{72}{3}=24$, and the order of $<g^{16}>$ is $\frac{72}{\text{GCD}(16,72)}=\frac{72}{8}=9$.