# 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?

• Well, $g=3^2$ isn't a primitive root because $\gcd(2,30)=2$ and $g^{15}=1$, noting that $15=\frac {30}2$. Do you see the pattern? – lulu Mar 23 at 16:57
• Phrased differently, you say that you know that there are $\varphi(30)=8$ primitive roots. How do you know that? The proof of that tells you how to find all the others, given one. – lulu Mar 23 at 16:58

## 3 Answers

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$$.

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))}$$.

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.