# Reluctant roots: $n$ is a primitive root of $p$ but not of $p^2$

I was looking at the primitive roots $n \bmod p$ and $p^2$ to see how often we get primitive roots of a prime that are not primitive roots of the square of that prime. I'll call this a reluctant root of $p$.

It's really rare.

With $p$ limited to a little under $38000$, I didn't find any such cases at all for $n<10$. In particular I started out looking specifically for cases when $2$ is a reluctant root, and finding none I widened the search. The first case I found was $n=11, p=71$, when I was just looking at $n$ prime, but there is also a case for $n=10, p=487$. In these cases, as in most others, and taking only $n<p,$ this was the only such case despite many hundreds of primes for which $n$ was a primitive root.

Searching the other way around, looking for reluctant roots of various primes $p,$ I found that in the first $400$ primes, which have a total of $190111$ primitive roots, there are only $143$ reluctant roots across $122$ primes. Most primes have no reluctant roots; the first few primes that have reluctant roots are $29, 37, 43, 71, 103, 109, 113, 131\ldots$; even fewer ($18$ in this range) have more than $1$, with $653$ taking the golden cupcake (so far) with $4$ reluctant roots - $84, 120, 287, 410$.

Main question: what is the smallest prime that has $2$ as a reluctant root, or is there no such prime?

Other questions: why are reluctant roots so rare? and is there any more investigative work on these (perhaps under a less Harry-Potteresque name)?

• I found the primes here are recorded under OEIS A060503, but no further information. They include $2$ in the set which I guess is technically true (the "primitive root" $\bmod 2$ is $1$, whereas $4$'s primitive root is $3$). – Joffan Apr 16 '18 at 1:51
• Reluctant roots might also be called "jump the gun" roots in the sense that $r^{p-1}$, intended merely to be $\equiv 1 \bmod p$, turns out to be $\equiv 1 \bmod p^2$. For instance, $11^{70}\equiv 1 \bmod 5041$. Hitting this "jump the gun" condition is expected to be rare and to become more so as we go to larger primes. – Oscar Lanzi Apr 16 '18 at 2:03
• en.wikipedia.org/wiki/Wieferich_prime – Angina Seng Apr 16 '18 at 2:40
• You might also be interested in oeis.org/A060520, primes that have at least 4 reluctant roots. – Gerry Myerson Apr 16 '18 at 3:09
• – lhf Apr 16 '18 at 11:09

If $g$ is a primitive root modulo $p$ (or even if it isn't), then $g^{p-1}\equiv1+kp\bmod{p^2}$ for some $k$, $0\le k\le p-1$. As Oscar Lanzi points out in the comments, $g$ is "reluctant" if and only if $k=0$, so there is (in some sense) only a 1-in-$p$ chance that $g$ is reluctant. That, I think, would explain why they are rare.

• Agreed, but the chances seem to be even lower than that, at least for primitive roots. – Joffan Apr 16 '18 at 3:11

One word to search is Wieferich primes in base $a$ — for which $a^{p-1} = 1 (p^2)$, and they are (pretty obviously) related to periods of "decimal" expansions in different bases; they are really rare. For example, first (and only ones in range $\leq 10^{12}$) examples for which $2^{p-1} = 1 (p^2)$ are 1093 and 3511. So your reluctant roots are sort of $a$'s for generalized Wieferich primes. More scientific interest in these numbers is that if $p$ is Wieferich in $a$, then $\Bbb Z[a^{\frac 1 p}]$ is not full ring of integers of $\Bbb Q(a^{\frac 1 p})$; reluctant roots should be related to branching of analogous extensions.

On the reason of rarity: Dilcher and Pomerance proved in mid 90s that $(2^{p-1} - 1)/p$ is uniformly distributed mod $p$, and methods suggest that it should be close to uniform when you replace $2$ by something else. So when you have a "function", say $W$, defined on primes with values uniformly distributed on $\{0, \dots, p-1\}$ and nothing on composites, it'll have roughly $\ \log \log N$ zeroes in long run (by prime distribution theorem). And double logarithm is very slowly growing function. Even if you count primes for which $W(p)$ just divides $p-1$, you'll have not much, because divisor function is not so large.

I'd say that this business overall is not very popular (because it's pretty hard to prove something here).

For odd primes $p$ and natural integers $a\neq 0,1$, the "Fermat quotients" $q_a(p):=\frac {a^{p-1}-1}{p}$ mod $p$ have been given much attention by Georges Gras and his collaborators (see ref. below). Let me sketch their results in two directions :

1) Concerning the "rarity" the "Harry Potteresque" reluctant roots mod $p$ : For fixed $a\ge 2$, it is suggested in [G] that the probability of nullity mod $p$ of the $q_p(a)$'s is less than $\frac {1}{p}$ for any arbitrary large prime $p$. To justify this the author proposes various heuristics, supported by numerical computations and analytical results, which may imply the finiteness of the number of the $q_p(a)$'s that are $0$ mod $p$, and the existence of integers $a$ such that $q_p(a) \neq 0$ mod $p$. He shows that the density of integers A such that $q_p(A)\neq 0$ mod $p$ is about $O(\frac {1}{log (x)})$ for all $p \le x$.

2) In relation with the works of Vandiver and Furtwängler, [GQ] lay the foundations of a new global cyclotomic approach to FLT. One significant results reads : Let $p>3$. If there exists a prime $l\neq p$ s.t. $q_p (l)\neq 0$ mod $p$ and s.t. for any prime ideal $\mathcal L$ above $l$ in $\mathbf Q(\mu _{l-1})$ one has the relation $\mathcal L^{1-c}=(\alpha)\mathcal A^p$, where $c$ denotes complex conjugation, $\mathcal A$ is an ideal in $\mathbf Q(\mu _{l-1})$ and $\alpha \in \mathbf Q(\mu _{l-1})$ with $\alpha\equiv 1$ mod $p^2$, then the first case of FLT holds; the second case holds for $p$ as soon as there exist infinitely many such primes $l$.

[G] G. Gras, "Etude probabiliste des $p$-quotients de Fermat", Functiones et Approximatio, Vol. 54.1 (2016), 1–26

[GQ] G. Gras, R. Quême, "Vandiver papers on cyclotomy revisited and FLT", Publ. Math. Besançon, Vol.2 (2012), 47-111