Is the smallest primitive root modulo p a primitive root modulo p^2? - MathOverflow

Is the smallest primitive root modulo p a primitive root modulo p^2?

2010-06-09T13:43:44Z

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?

Answer by Jack Schmidt for Is the smallest primitive root modulo p a primitive root modulo p^2?

2010-06-09T13:55:10Z

It is not true in general. See http://primes.utm.edu/curios/page.php/40487.html for the example, 5 mod 40487^2.

Answer by Gjergji Zaimi for Is the smallest primitive root modulo p a primitive root modulo p^2?

2010-06-09T14:03:07Z

This would probably fit in the eventual counterexamples page too.

http://www.ams.org/journals/mcom/2009-78-266/S0025-5718-08-02090-5/home.html

Answer by David Speyer for Is the smallest primitive root modulo p a primitive root modulo p^2?

2010-06-09T15:06:42Z

Primes $p$ for which $p^2$ divides $q^{p-1}-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^{p-1}-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^{p-1}-1)/p \mod p$ looks uniformly distributed in $[-p/2, p/2]$. They suggest that the rarity of primes with $p$ dividing $(2^{p-1}-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.

Answer by KConrad for Is the smallest primitive root modulo p a primitive root modulo p^2?

2010-06-09T22:06:24Z

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^{k-1}$. 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.