Find the Primitive Roots $\mod 31$ 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?
 A: 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))}$. 
A: There are indeed $\phi(\phi (31))=8$ primitive roots modulo $31$ and you can find them as described here:
Finding a primitive root of a prime number
For example, $3^k\equiv 1\bmod 31$ only holds for $k=30$, if $1\le k\le 30$. Hence $3$ is a primitive root modulo $31$. Now compute the orders of powers of $3$. 
A: 
I then know that $\{3^0,3^1,3^2,…,3^{29}\}$ is a residue system $\mod 31$.

And you are sooo close.
$(3^k)^m = 3^{mk}$.  So for $3^k$ to be a primitive root we need $mk$ to not be a multiple of $30$ for any natural $m < 30$. 
In other words if $k$ is relatively prime to $30$.
In fact, that is precisely why we know there are $\phi(30)$ primitive roots.
