2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – lulu Mar 23 at 16:57
  • $\begingroup$ 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. $\endgroup$ – lulu Mar 23 at 16:58
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.