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?

$\endgroup$
5
  • $\begingroup$ Find elements $g$ with nontrivial order, then $\langle g \rangle$ is a non-trivial subgroup. $\endgroup$
    – Qi Zhu
    Aug 21, 2019 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$ Aug 21, 2019 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, 2019 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$ Aug 21, 2019 at 9:39
  • $\begingroup$ The link I gave you, does exactly this for $41$, it's no different here... $\endgroup$
    – Qi Zhu
    Aug 21, 2019 at 9:45

1 Answer 1

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

$\endgroup$
4
  • $\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$ Aug 21, 2019 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, 2019 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$ Aug 21, 2019 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, 2019 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.