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.

someprimitive 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