# Finding the elements with order $30$ in group $\mathbb Z^*_{31}$. [duplicate]

The elements of the group $$\mathbb Z^*_{31}$$ is $$1$$ to $$30$$. I found the first element with order $$30$$ is $$11$$ by checking the powers of each element by $$2,3,5,6,10,15,30$$. My professor mentioned that the other elements with order $$30$$ can be found after finding the first element using a theorem. Could someone please help me with that.

• You needed to check only $6, 10,$ and $15$, not $2, 3,$ and $5$ – J. W. Tanner Apr 5 at 23:31
• Hi and welcome! I think you can find the answer to your question here – Menezio Apr 5 at 23:42
• @J.W.Tanner , Could you please explain why not 2,3 and 5. Because, i found the order of 2 in the group as 5 (2^5 = 1(mod 31). perhaps, you mean for the elements after 11? – Art Apr 6 at 0:20
• you would have found $2$ not to be a primitive root when you checked $2^{15}$ – J. W. Tanner Apr 6 at 0:25
• @J.W Tanner Yes.Understood. Thanks – Art Apr 6 at 0:32

Since $$\Bbb Z_{31}^*\cong\Bbb Z_{30}$$ and $$\varphi(30)=8$$, there are $$8$$ with order $$30$$. They are $$1,7,11,13,17,19,23,29$$, each of which is coprime with $$30$$.

The theorem your professor is referring to is $$|g^k|=|g|/\operatorname{gcd}(|g|,k)$$.

You can use any generator, say $$11$$, to construct an isomorphism $$\psi$$ between the multiplicative group $$\Bbb Z_{31}^*$$ and the additive group $$\Bbb Z_{30}$$, given by $$\psi(11^n)=n$$.

So, under the isomorphism, we get $$\{11,11^7,11^{11},11^{13},11^{17},11^{19},11^{23},11^{29}\}$$ as the generators.

• $27$ is not coprime to $30$. $(27,30) = 3$ – user100101212 Apr 5 at 23:44
• Oops. Thanks for catching that. @user100101212 – Chris Custer Apr 5 at 23:57
• You should give some details on the isomorphism: one is a multiplicative group, the other an additive group, and it may be not completely trivial to every reader. – Bernard Apr 6 at 13:46
• @Bernard I've added something on that. – Chris Custer Apr 6 at 15:37

Yes, there is a way to find all other elements of order $$30$$, once you find one element of order $$30$$. This is because $$31$$ is a prime number so $$\mathbb{Z}_{31}^{*}$$ is cyclic, and once you have found a generator, say $$g$$, you can find all other elements. The theorem you need to use is that $$|g^{s}| = \frac{|g|}{(s,|g|)}$$, where $$|\cdot|$$ denote the order of an element. Then all elements of the form $$g^{s}$$, with $$(s,|g|) = (s,30) = 1$$, will have order $$30$$ by the theorem. After doing the computation, you get the set: $$\{ 11^1, 11^7 , 11^{11}, 11^{13}, 11^{17} , 11^{19} , 11^{23}, 11^{29} \} = \{ 11 , 13 , 24 , 21 , 3 , 22 , 12 , 17\} \pmod{31}$$

• $24 \equiv 11^{11} \pmod{31}$ , and $22 \equiv 11^{19} \pmod{31}$. – user100101212 Apr 5 at 23:42
• No, those are exponents of the generator. – user100101212 Apr 5 at 23:44
• I'm sorry. Under the isomorphism you would be correct. – Chris Custer Apr 6 at 0:09

Hint:

Welcome! You've found that every element in $$(\mathbf Z/31\mathbf Z)^\times$$ is a power of $$11$$.

Now, if an element $$a$$ in a group has order $$n$$, $$a^k$$ has order $$\;\dfrac{n}{\gcd(n,k)}$$.