1
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ Find elements $g$ with nontrivial order, then $\langle g \rangle$ is a non-trivial subgroup. $\endgroup$ – Qi Zhu Aug 21 '19 at 8:06
  • $\begingroup$ @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 $\endgroup$ – user6973173333 Aug 21 '19 at 8:17
  • $\begingroup$ 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. $\endgroup$ – Qi Zhu Aug 21 '19 at 8:45
  • $\begingroup$ @QiZhu I dont suppose you show me one example for my question please? I just want to understand it better $\endgroup$ – user6973173333 Aug 21 '19 at 9:39
  • $\begingroup$ The link I gave you, does exactly this for $41$, it's no different here... $\endgroup$ – Qi Zhu Aug 21 '19 at 9:45
1
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user6973173333 Aug 21 '19 at 12:21
  • $\begingroup$ @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. $\endgroup$ – gandalf61 Aug 21 '19 at 12:28
  • $\begingroup$ 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? $\endgroup$ – user6973173333 Aug 21 '19 at 12:33
  • $\begingroup$ @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. $\endgroup$ – gandalf61 Aug 21 '19 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.