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.

Improve this question
$\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
    Commented Aug 7, 2020 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
    Commented Aug 7, 2020 at 14:10
  • 1
    $\begingroup$ oops, the second $(p-1)\varphi(p-1)$ should be a $p\,\varphi(p-1)$, sorry. $\endgroup$
    – Chris Wuthrich
    Commented Aug 7, 2020 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$
    – მამუკა ჯიბლაძე
    Commented Aug 15, 2020 at 13:14

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Surprising how much work needs to go in from $p^1$ to $p^{0.99}$. $\endgroup$
    – Chris Wuthrich
    Commented Aug 7, 2020 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$
    – user156885
    Commented Aug 7, 2020 at 18:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .