My approach:
There exist $\phi(31-1) = \phi(30) = 8$ primitive roots.
If $x^6 \not\equiv 1$,$x^{10} \not\equiv 1$, and $x^{15} \not\equiv 1$, then $x$ is a primitive root modulo $31$.
$x = 1, 2$ fails this but $x = 3$ passes this, thus $3$ is a primitive root.
I then know that $\{3^0, 3^1, 3^2, \dots, 3^{29}\}$ is a residue system mod $31$.
How can I then determine which elements are the primitive roots of this set?
Best Answer
Once you found one primitive root, the others are its powers which are relatively prime to $\phi(31)=30$. The numbers in $\{0,1,2,...,29\}$ which are relatively prime to $30$ are $1,7,11,13,17,19,23,29$ and hence the primitive roots are $3,3^7,3^{11},...,3^{29}$.
The reason why this is the case is the general formula $ord_n(a^k)=\frac{ord_n(a)}{gcd(k,ord_n(a))}$.