# Orders of elements and subgroups in a cyclic group

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?

• Find elements $g$ with nontrivial order, then $\langle g \rangle$ is a non-trivial subgroup. – Qi Zhu Aug 21 '19 at 8:06
• @QiZhu how do i do that? what does non trivial even mean, are you able to show an example in the context of Z*73 – user6973173333 Aug 21 '19 at 8:17
• Non-trivial means $1 < \operatorname{ord}(g) < |G|$. Finding the order of elements is not easy in general - see e.g. math.stackexchange.com/questions/1025578. – Qi Zhu Aug 21 '19 at 8:45
• @QiZhu I dont suppose you show me one example for my question please? I just want to understand it better – user6973173333 Aug 21 '19 at 9:39
• The link I gave you, does exactly this for $41$, it's no different here... – Qi Zhu Aug 21 '19 at 9:45

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 $$$$ 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 $$$$ 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 $$$$ is $$\frac{|G|}{\text{GCD}(k,|G|)}$$.

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

• So in the case of 72, a non-trivial subgroup would be 15? Sorry its just i dont know where the 15 even came from in your example – user6973173333 Aug 21 '19 at 12:21
• @user6973173333 First you need to find a primitive root of $73$ - a number with order $72$ in $\mathbb{Z}^{\times}_{73}$. Then you raise this primitive root to the power of $15$ modulo $73$. This number will then generate a non-trivial sub-group of $\mathbb{Z}^{\times}_{73}$. There is nothing special about $15$ - $g^2$, $g^3$, $g^4$, $g^6$, $g^8$ etc. will all generate non-trivial sub-groups. – gandalf61 Aug 21 '19 at 12:28
• how would one find a primitive root of 73? So are you saying that <15> is 1 non trivial subgroup and likewise I have to find other subgroups? Also where did the 15 come from? – user6973173333 Aug 21 '19 at 12:33
• @user6973173333 I picked the power $15$ at random - it is not important. If you want to understand $\mathbb{Z}^{\times}_{73}$ you should start by reading these Wikipedia articles: Primitive root modulo n, Multiplicative group of integers module n. – gandalf61 Aug 21 '19 at 12:53