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:


*

*Are there any odd primes $p$, and primitive roots $g$, such that $g^{p-1}\equiv 1\pmod{p^2}$?

*Are there any odd primes $p$, and minimal primitive roots $g$, such that $g^{p-1}\equiv 1\pmod{p^2}$?

 A: 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$.
A: 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.
A: 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.
