# The smallest primitive root modulo powers of prime

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.

• 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 – Gerry Myerson Aug 7 '20 at 13:03
• 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. – Chris Wuthrich Aug 7 '20 at 14:10
• oops, the second $(p-1)\varphi(p-1)$ should be a $p\,\varphi(p-1)$, sorry. – Chris Wuthrich Aug 7 '20 at 14:55
• 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$. – მამუკა ჯიბლაძე Aug 15 '20 at 13:14

• Surprising how much work needs to go in from $p^1$ to $p^{0.99}$. – Chris Wuthrich Aug 7 '20 at 16:25