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?
$\begingroup$
$\endgroup$
4
asked Jun 9, 2010 at 13:43
-
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)^{p-1}\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 ZudilinCommented Jun 9, 2010 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 BacherCommented Jun 9, 2010 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 RomagnyCommented Apr 12, 2013 at 16:24
-
$\begingroup$ The counterexamples are listed in OEIS A055578. So other than the trivial term $2$, the known examples are $40487$ and $6692367337$, both with smallest primitive root $5$. $\endgroup$– Jianing SongCommented May 14 at 2:25
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
3
It is not true in general. See http://primes.utm.edu/curios/page.php/40487.html for the example, 5 mod 40487^2.
answered Jun 9, 2010 at 13:55
-
1$\begingroup$ Oops! There was a typo in my computer program, so I missed this example. Thanks for the quick response! $\endgroup$ Commented Jun 9, 2010 at 13:58
-
6$\begingroup$ Good reason not to trust computer-based evidence. $\endgroup$ Commented Jun 9, 2010 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$ Commented Jun 10, 2010 at 2:40
$\begingroup$
$\endgroup$
3
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.
-
1$\begingroup$ For the general statement: c.f. "Problems in Algebraic Number Theory", Murty and Esmonde, second edition, Exercise 5.6.12 $\endgroup$ Commented Jun 9, 2010 at 22:55
-
3$\begingroup$ +1 for the verb "to Sloane" $\endgroup$ Commented Sep 8, 2013 at 2:39
-
2$\begingroup$ @FilippoAlbertoEdoardo: I've heard Noam Elkies refer to a book as being Dovered. $\endgroup$– KConradCommented Sep 8, 2013 at 15:29
$\begingroup$
$\endgroup$
1
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.
answered Jun 9, 2010 at 15:06
-
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$ Commented Jun 10, 2010 at 2:34
$\begingroup$
$\endgroup$
5
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
answered Jun 9, 2010 at 14:03
-
$\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/cgi-bin/… $\endgroup$ Commented Jun 10, 2010 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$ Commented Sep 7, 2013 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), 1193-1195. The prime $p$ is $6692367337$; the least primitive root mod $p$ is $5$, but $5^{p-1} \equiv 1 \bmod p^2$ (the least primitive root mod $p^2$ turns out to be $7$). $\endgroup$ Commented Sep 8, 2013 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$ Commented Sep 9, 2013 at 5:29
-
$\begingroup$ Just in case the link gets outdated: that prime counterexample is 6692367337. $\endgroup$– AlexCommented Sep 8, 2016 at 2:51