# How to find out all elements with specific order in $Z_p^*$

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.

• 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. – Roddy MacPhee May 13 at 9:01
• – lhf May 13 at 11:23