5
$\begingroup$

I wrote a program to calculate the minimal primitive root modulo $p^a$ where $p > 2$ is a prime, by enumerating $g$ from $2$ and checking whether it's a primitive root, but I forgot to check $\gcd(g, p) = 1$. However, it still worked in all the test cases.

So is it true that the smallest primitive root modulo $p^a$ is smaller than $p$?

P.S. I think this should be right because the smallest primitive root modulo $p$ is $O(\log^6 p)$ (assuming the generalized Riemann hypothesis), which is much smaller than $p$ when $p$ is large enough. But I have no idea how to prove this.

$\endgroup$
4
  • 1
    $\begingroup$ Note that the smallest primitive root modulo $p=40487$ is $5$, but $5$ is not a primitive root modulo $p^2$. See also primes.utm.edu/curios/page.php/40487.html $\endgroup$ – Gerry Myerson Aug 7 '20 at 13:03
  • 5
    $\begingroup$ There are $(p-1)\varphi(p-1)$ primitive roots mod $p^2$ and $(p-1)\varphi(p-1)$ elements mod $p^2$ are primitive elements mod $p$. Assume your claim is wrong: all primitive roots mod $p$ between $1$ and $p$ are not primitive roots mod $p^2$, but all between $p$ and $p^2$ are. Now take any, say $g$ below $p$, then its inverse $h$ mod $p^2$ has the same property, so $1<h<p$. But then $gh\equiv 1$ mod $p^2$ is not possible. $\endgroup$ – Chris Wuthrich Aug 7 '20 at 14:10
  • 1
    $\begingroup$ oops, the second $(p-1)\varphi(p-1)$ should be a $p\,\varphi(p-1)$, sorry. $\endgroup$ – Chris Wuthrich Aug 7 '20 at 14:55
  • $\begingroup$ Adding to the information by @GerryMyerson - the smallest (?) example of some primitive root modulo $p$ which is not a primitive root modulo $p^2$ seems to be: $14$ is a primitive root modulo $29$ but not modulo $29^2$. $\endgroup$ – მამუკა ჯიბლაძე Aug 15 '20 at 13:14
5
$\begingroup$

This is known, see

https://arxiv.org/abs/1908.11497

where it is show for squares of primes. Higher powers then follow from other elementary arguments

$\endgroup$
2
  • 1
    $\begingroup$ Surprising how much work needs to go in from $p^1$ to $p^{0.99}$. $\endgroup$ – Chris Wuthrich Aug 7 '20 at 16:25
  • $\begingroup$ Yeah, Paul Pollack has a very nice and simple argument which gets down to p no problems. It might be mentioned in the published version of this article ( somewhere in Journal Number Theory) $\endgroup$ – zz7948 Aug 7 '20 at 18:55

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.