Let $g(p)$ be the least positive primitive root of the prime $p$, the primitive roots being the generators of the cyclic group $\mathbb{Z}_{p-1}$. These are the values for the first prime numbers:

$$g(3) = 2$$

$$g(5) = 2$$

$$g(7) = 3$$

$$g(11) = 2$$

$$g(13) = 2$$

$$g(17) = 3$$

$$g(19) = 2$$

$$g(23) = 5$$

$$g(29) = 2$$

$$g(31) = 3$$

$$g(37) = 2$$

$$g(41) = 6$$

I've learned that it's hard to calculate $g(p)$ for arbitrary $p$.

Main questions

(1) Is there a known connection between $g(p)$ and some other number theoretic functions?
E.g. $g(p)=$ some number theoretic function $f$ of the number $\phi(p-1)$

(2) Is there a known connection between the property $g(p)=2$ and some other number theoretic properties?
E.g. $g(p)=2$ iff the number $\phi(p-1)$ has some number theoretic property $P$

Side questions

(3) What's the asymptotic probability that $g(p) = 2$?

(4) Are there values $g(p)$ cannot take?
What about $g(p) = 4$ and higher powers of $2$? What about $g(p) = 9$? See OEIS.

(5) How hard is $g(p)$ exactly?
Is it possibly NP hard?


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.