# Finding a primitive root

I'm trying to find a small primitive root modulo $p^k$, where $p$ is prime. My strategy is to test small numbers $g=2,3,\ldots$ until I find a primitive root modulo $p$. That is, until $ord_pg=\phi(p)=p-1$. There are results that suggest such a search won't take long.

To go from modulo $p$ to modulo $p^k$, there is the following well-known theorem:

Thm: If $g$ is a primitive root modulo $p$, then $$\begin{cases} g+p & g^{p-1}\equiv 1\pmod{p^2}\\g & g^{p-1}\not\equiv 1\pmod{p^2}\end{cases}$$ is a primitive root modulo $p^k$, for all $k\in\mathbb{N}.$

However, I was unable to find an example that falls into the first case (except $p=2$, trivially). Hence, I have two related questions:

1. Are there any odd primes $p$, and primitive roots $g$, such that $g^{p-1}\equiv 1\pmod{p^2}$?
2. Are there any odd primes $p$, and minimal primitive roots $g$, such that $g^{p-1}\equiv 1\pmod{p^2}$?
• I have heard finding primitive roots is not easy. – Pedro Tamaroff Mar 19 '14 at 18:33

With computer search I found that $g=5$ for $p = 40487$ is an example of (2) . http://www.wolframalpha.com/input/?i=5%5E40486+mod+1639197169

I would guess that this should happen with probability $1/p$. $\sum_{2 < p \le 40487} \frac 1p = 2.1235$ only. In retrospect it makes sense that the examples are rare.

• Nice, thanks. Will pay bounty once permitted. – vadim123 Mar 23 '14 at 18:16
• Whoops, awarded bounty incorrectly. Will fix. – vadim123 Mar 24 '14 at 14:41

For your first question, consider $p=71$ and $g=11$. Here, $11$ is a primitive root modulo $71$, but $11^{70}\equiv 1 \bmod 71^2$. Unfortunately, this is not an example of your second question, because $7\bmod 71$ is also a primitive root.

I found this example looking at lists of Wieferich primes with respect to a certain base. There is probably an example for your second question farther down the list; I see no reason why there couldn't be one.

I just checked the first $103$ odd primes $p$ and none of them satisfy $(2)$, with $g$ the smallest positive primitive root modulo $p$.

Surprisingly, only two odd primes are known such that the smallest primitive root mod $p$ is not a primitive root mod $p^2$: $40487$ and $6692367337$. See OEIS:A055578.