I am learning elementary number theory and with some reasons I have to find out all the elements with some specific oder in $Z_p^*$, which is just the multiplicative group induced by $Z_p$.

For example, given a prime $p=7$, I need to find out all $a\in \{1,2,..,6\}$ s.t. $a^3\equiv 1$ (mod $7$). This problem is equivalent to find out all $a\in Z_7^*$ with order of $3$.

We know $Z_p^*$ is also a cyclic group. So if we can find out all generators of the multiplicative group $Z_7^*$, say $g_1,g_2,...,g_k,$ then $(g_1)^2,(g_2)^2,...,(g_k)^2$ are all the elements with order of $3$ in $Z_7^*$.

But usually it is not easy to find out all the generators of $Z_p^*$, which are called primitive roots in number theory by the way.

So my problem is that, is there a quick method to find out all such primitive roots given any prime $p$, or is there any better way to find out all the elements with some specific oder in $Z_p^*$?

I don't remember too much group theory, so a hint or answer without involving deep group theory will be better. But any help will be greatly appreciated.

  • $\begingroup$ note relabelling it as $\{1,2,3,3,-2,-1\}$ we get a and -a when raised to the third power have opposite sign if al elements get both a negative and positive label. $\endgroup$ – Roddy MacPhee May 13 at 9:01
  • 1
    $\begingroup$ See math.stackexchange.com/a/2512103/589 $\endgroup$ – lhf May 13 at 11:23

Your Answer

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

Browse other questions tagged or ask your own question.