It is conjectured by Artin that for every number $g$ which is not $-1$ and not a square number, there is an infinite number of $m$ such that $g$ is a primitive root modulo $m$.

How to find $m$ efficiently given primitive root $g$?

The reverse problem that given modulo $m$, find the primitive root $g$ can be solved faster than brute force with random trying with checking $g^{(m-1)/d} \neq 1$ ( $d\mid m$ ).

But I can't find something like that for this problem.

  • $\begingroup$ Sorry, that first statement is not known. Well, as stated it is obviously false (take $g=1$ say). See Artin's Conjecture $\endgroup$ – lulu Apr 29 '18 at 20:08
  • $\begingroup$ I'm sorry. I edit the statement .Thank you for pointing out. $\endgroup$ – Koreyuki Apr 29 '18 at 20:19

Your Answer

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

Browse other questions tagged or ask your own question.