3
$\begingroup$

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?

$\endgroup$

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.