Let $p \ne 2$ be a prime and $a$ the smallest positive integer that is a primitive root modulo $p$. Is $a$ necessarily a primitive root modulo $p^2$ (and hence modulo all powers of $p$)? I checked this for all $p < 3 \times 10^5$ and it seems to work, but I can't see any sound theoretical reason why it should be the case. What is there to stop the Teichmuller lifts of the elements of $\mathbb{F}_p^\times$ being really small?

2$\begingroup$ Well, the probability of a primitive root $r$ modulo $p$ not to be primitive modulo $p^2$ is $1/p$ (there is exactly one $a$ modulo $p$ such $(r+ap)^{p1}\equiv1\pmod{p^2}$). So, your search for larger $p$ will hardly lead to a counter example. But I've never heard on a theoretical background towards this. $\endgroup$ – Wadim Zudilin Jun 9 '10 at 13:55

2$\begingroup$ Since finite fields can not be ordered, I am sometimes a little bit annoyed by properties defining the smallest (natural) integers $a$ whose reduction modulo $p$ has a certain property in the finite field $\mathbb Z/p\mathbb Z$. $\endgroup$ – Roland Bacher Jun 9 '10 at 16:27

$\begingroup$ Well, but among the finite fields the prime field is a bit special, and it indeed has a canonical total order (which is not compatible with the field operations). $\endgroup$ – Matthieu Romagny Apr 12 '13 at 16:24
It is not true in general. See http://primes.utm.edu/curios/page.php/40487.html for the example, 5 mod 40487^2.

1$\begingroup$ Oops! There was a typo in my computer program, so I missed this example. Thanks for the quick response! $\endgroup$ – David Loeffler Jun 9 '10 at 13:58

4$\begingroup$ Good reason not to trust computerbased evidence. $\endgroup$ – Victor Protsak Jun 9 '10 at 18:54

$\begingroup$ Victor, I checked after all myself: $5^{40486}\equiv 1 \pmod{40487^2}$, but I am not very surprised after learning the story about Wolstenholme primes (en.wikipedia.org/wiki/Wolstenholme%27s_theorem): only two are known with the smallest 16843 of about the same magnitude as 40487. $\endgroup$ – Wadim Zudilin Jun 10 '10 at 2:40
The key term here is: Wieferich prime base $a$.
What you observed can be presented to children in the following form: if $p$ is a prime greater than 5 and the fraction $1/p$ has decimal period $d$, numerical tables show $1/p^2$ has decimal period $dp$, $1/p^3$ has decimal period $dp^2$, and generally the decimal period of $1/p^k$ is $dp^{k1}$. For example, 1/13 has decimal period 6, 1/169 has decimal period $78 = 6 \cdot 13$, and 1/2197 has decimal period $1014 = 6 \cdot 13^2$.
This works for primes below 100, but if you search far enough you will find a counterexample. The first one is $p = 487$: 1/487 and $1/487^2$ both have decimal period 486. The second counterexample is $p = 56,598,313$. (!!) This list has been Sloaned: http://oeis.org/A045616.
For a general article about this business, see http://www.jstor.org/stable/3219294.
Within algebraic number theory, this phenomenon appears when you compute the ring of integers of ${\mathbf Q}(\sqrt[n]{2})$, which turns out to be ${\mathbf Z}[\sqrt[n]{2}]$ for all $n \leq 1000$. With that evidence you might guess the ring of integers is always ${\mathbf Z}[\sqrt[n]{2}]$, just like the ring of integers of ${\mathbf Q}(\zeta_n)$ is always ${\mathbf Z}[\zeta_n]$. But in fact it's not always true. There are $n > 1000$ such that ${\mathbf Z}[\sqrt[n]{2}]$ is not the full ring of integers of ${\mathbf Q}(\sqrt[n]{2})$. If you search for Wieferich primes to base 2 you will find them.

1$\begingroup$ For the general statement: c.f. "Problems in Algebraic Number Theory", Murty and Esmonde, second edition, Exercise 5.6.12 $\endgroup$ – Dror Speiser Jun 9 '10 at 22:55

1

1$\begingroup$ @FilippoAlbertoEdoardo: I've heard Noam Elkies refer to a book as being Dovered. $\endgroup$ – KConrad Sep 8 '13 at 15:29
Primes $p$ for which $p^2$ divides $q^{p1}1$, for various small values of $q$, are often important in elementary attacks on Fermat's Last Theorem. See Lenstra and Stevenhagen's article "Class Field Theory and the First Case of Fermat's Last Theorem" in the book Modular Forms and Fermat's Last Theorem, for a quick survey. I don't see any reason, from this perspective, that $(q^{p1}1)/p$ should be particularly unlikely to be divisible by $p$. Nonetheless, that literature might give you some hints.
Crandall, Dilcher and Pomerance (see Section 3) present data suggesting that $(2^{p1}1)/p \mod p$ looks uniformly distributed in $[p/2, p/2]$. They suggest that the rarity of primes with $p$ dividing $(2^{p1}1)/p$ has no deeper reason than that, if $a_p$ is a random sequence indexed by primes, one only expects $p$ to divide $a_p$ for roughly $\log \log N$ primes less than $N$, and $\log \log$ of the computable range is quite small. Replacing $2$ by the smallest primitive root mod $p$ may exhibit similar behavior.

3$\begingroup$ David, they are more important for Catalan's equation! Such pairs are crucial in the final solutions, while for the FLT they only do the "1st case". $\endgroup$ – Wadim Zudilin Jun 10 '10 at 2:34
This would probably fit in the eventual counterexamples page too.
http://www.ams.org/journals/mcom/200978266/S0025571808020905/home.html

$\begingroup$ The main result of the cited paper was anticipated by Steven Glasby in a post to the Number Theory mailing list on 22 April 2001. See listserv.nodak.edu/cgibin/… $\endgroup$ – Gerry Myerson Jun 10 '10 at 0:48

$\begingroup$ The link didn't work when I tried it just now, but one can find the post by searching the nmberthry archive at the listserv for Glasby. $\endgroup$ – Gerry Myerson Sep 7 '13 at 23:40

$\begingroup$ For the record (in case the links disappear again): A. Paszkiewicz, "A new prime $p$ for which the least primitive root mod $p$ and the least primitive root mod $p^2$ are not equal", Math. Comp. 78 (2009), 11931195. The prime $p$ is $6692367337$; the least primitive root mod $p$ is $5$, but $5^{p1} \equiv 1 \bmod p^2$ (the least primitive root mod $p^2$ turns out to be $7$). $\endgroup$ – Noam D. Elkies Sep 8 '13 at 4:06

$\begingroup$ @Noam, sorry, I meant the link I posted to the Glasby post to the nmbrthry listserv  that's the one that seems to be broken. $\endgroup$ – Gerry Myerson Sep 9 '13 at 5:29

$\begingroup$ Just in case the link gets outdated: that prime counterexample is 6692367337. $\endgroup$ – Alex Sep 8 '16 at 2:51