Is the smallest primitive root modulo p a primitive root modulo p^2? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T03:16:54Z http://mathoverflow.net/feeds/question/27579 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2 Is the smallest primitive root modulo p a primitive root modulo p^2? David Loeffler 2010-06-09T13:43:44Z 2013-04-12T15:30:46Z <p>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 &lt; 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?</p> http://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2/27581#27581 Answer by Jack Schmidt for Is the smallest primitive root modulo p a primitive root modulo p^2? Jack Schmidt 2010-06-09T13:55:10Z 2010-06-09T13:55:10Z <p>It is not true in general. See <a href="http://primes.utm.edu/curios/page.php/40487.html" rel="nofollow">http://primes.utm.edu/curios/page.php/40487.html</a> for the example, 5 mod 40487^2.</p> http://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2/27582#27582 Answer by Gjergji Zaimi for Is the smallest primitive root modulo p a primitive root modulo p^2? Gjergji Zaimi 2010-06-09T14:03:07Z 2010-06-09T14:03:07Z <p>This would probably fit in the eventual counterexamples page too.</p> <p><a href="http://www.ams.org/journals/mcom/2009-78-266/S0025-5718-08-02090-5/home.html" rel="nofollow">http://www.ams.org/journals/mcom/2009-78-266/S0025-5718-08-02090-5/home.html</a></p> http://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2/27587#27587 Answer by David Speyer for Is the smallest primitive root modulo p a primitive root modulo p^2? David Speyer 2010-06-09T15:06:42Z 2010-06-09T15:06:42Z <p>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 <em>Modular Forms and Fermat's Last Theorem</em>, 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.</p> <p><a href="http://www.ams.org/mathscinet-getitem?mr=1372002" rel="nofollow">Crandall, Dilcher and Pomerance</a> (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.</p> http://mathoverflow.net/questions/27579/is-the-smallest-primitive-root-modulo-p-a-primitive-root-modulo-p2/27619#27619 Answer by KConrad for Is the smallest primitive root modulo p a primitive root modulo p^2? KConrad 2010-06-09T22:06:24Z 2013-04-12T15:30:46Z <p>The key term here is: Wieferich prime base $a$.</p> <p>What you observed can be presented to children in the following form: if $p$ is a prime <em>greater than 5</em> 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$.</p> <p>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: <a href="http://oeis.org/A045616" rel="nofollow">http://oeis.org/A045616</a>.</p> <p>For a general article about this business, see <a href="http://www.jstor.org/stable/3219294" rel="nofollow">http://www.jstor.org/stable/3219294</a>.</p> <p>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.</p>