$p^2$ misses 2 primitive roots

Question

When I Checked primitive roots of some primes P, I found this following phenomenon:

• $14$ is a primitive root of prime $29$, but it's not primitive root of $29^2$

• $18$ is a primitive root of prime $37$, but it's not primitive root of $37^2$

• $19$ is a primitive root of prime $43$, but it's not primitive root of $43^2$

• $11$ is a primitive root of prime $71$, but it's not primitive root of $71^2$

  And they are all missing exactly one primitive root, which is P has one primitive root that cannot be found in primitive roots of $p^2$. My question is: What is the smallest prime P such that P has $2$ primitive roots that cannot be found in the primitive roots of $p^2$? ( Here I mean primitive roots between $0$ and $p-1$)

Answer 1

A small search with pari-gp shows that 367 is the smallest such prime, it misses the primitive roots 159 and 205. Then 653 misses four primitive roots 84,120,287 and 410.

A search up to 20000 shows that only 16631 misses 4, while several (1103, 6569, 13187, 14939, 15313, 16649 and 18587) misses 3 primitive roots.

By curiosity I have mesured how many primes have 0, 1, 2, .... primitive roots in the range 1, p-1 which are not primitive roots of $p^2$, it seems to behave like a Poisson distribution with $\lambda = -\log\log 2$. does somebody has an explanation?

Just to show how good is this estimate here is the count up to 409499 of primes with 0 to 6 primitive roots missing in mod $p^2$.

   Observed   Expected
0   23 949      23 962
1    8 695       8 782
2    1 696       1 609
3      210         197
4       19          18
5        0           1
6        1           0

So we should expect to have some prime with 7 or more after about 8 000 000 primes.

Answer 2

If you take a prime like 7, its square is 49, has 42 co-primes roots 0-49. These can be represented as some x=g^n, where n ranges from 0 to 6*7-1 = 41. When n is a multiple of p, then p divides its own period.

For example, 3 is a primitive root of 7. 3^5 gives 5 mod 7, and 3^35 gives 19 mod 49. We now observe that 19 is a primitive root of 7, but in base 19, 7 divides its own period.

The number of small sevenites (ie 1 < n < p), is relatively small, none has gone as far as 20 in the search range, although 3511 has 10. A run was done to find the 40 smallest sevenites for primes to something like 2,400,000. This is done by insertion-sort using 60p as the upper banker. From this table (it is about 2 cdrom's worth of zipped files), one extracts the list of small sevenites. There are lots of bases which do not have small sevenites.

A compound sevenite is one where a higher power divides b^(p-1). An example is the third-order 7³ divides 18^3-1, and the fourth-order 13^4 dividing 239^4-1. There is only one small compound sevenite: 113³ in base 68.

No sevenite is known for the fibonacci series, but the sqrt(2) series 1,2,5,12,... has no fewer than 3 (13, 31 and 1546463), and the Heron triangle series as used to find the Messerine primes, and also integer area triangles of the form b-1, b, b+1, has one (103), these searches been taken to two millions (ie 2*120^4).

Sevenites are closely connected to the thing about 'x²=x, mod b^n'. In practice, these are specific examples of the general case. Where p is a sevenite of x, then x written in base p will agree to the last n places.

For example, 10 is a primitive root and sevenite of 487. In base 487, the sevenite tail ending in 10 is ... 0, 10. The 0 in column-one tells us that it's a small sevenite.

In base 13, the number 239 is written as 155. The sevenite tail for 5, in 13 is 01550155. Because the last four, but not five digits agree with 0000155, we see that 13^4 divides it, but 13^5 does not.

There is a fairly authoritive page on the wikipedia at `Euler's quotient'.

There's a list of sevenites http://z13.invisionfree.com/DozensOnline/index.php?showtopic=737 or the DozensOnline forum | mathematics | number theory | sevenites.

Answer 3

I just got this from oeis ( thanks to Esteban) that $13425,18243,34196,38462,39362,51787$ are all primitive roots of prime $52517$ but they are all not primitive roots of $52517^2$. Is there a prime p such that $p^2$ misses $7$ or $8$ primitive roots?