# Distribution of primitive roots mod p

Let $$p$$ be a prime number. I am interested in knowing how many primitive roots mod $$p$$ there are; at least, gaining some insight into the distribution of primitive roots mod $$p$$.

If I need to go looking for a primitive root, how far down the list of integers should I expect to look before I find one?

I know there are $$\phi(p-1)$$-many primitive roots mod $$p$$. Therefore the ratio of primitive roots mod $$p$$ is given by $$\phi(p-1)/(p-1)$$.

I could not find any theorems talking about bounds on this value for any primes of a certain form. So I plotted it for the first 100000 primes

I appreciate that there are infinitely many primes and that the behaviour of the first 100000 need not tell us anything about the overall behaviour. That being said, I am hoping someone could explain some of the features of this plot that stand out to me. For example:

1. The Number of primitive roots is bounded between 1/5 and 1/2. It seems some might sneak lower than 1/5.

2. There are a number of dense lines. For example: It seems there are lots of primes with 1/3 of integers being primitive roots.

If anyone can point out any references about the distribution of primitive roots. Or say anything about what might be happening here, that would be great.

• – lhf Sep 25 '19 at 23:49
• Of course $1/2$ is an upper bound. The only lower bound is zero. The lines you see come from $p=kq+1$ where $k$ is small and $q$ is prime. – Gerry Myerson Sep 26 '19 at 0:47
• The random model for the primes predicts that studying $\phi(p-1)/(p-1)$ is quite the same as studying $\phi(n)/n$. Now studying primitive roots is more than just $\phi(p-1)/(p-1)$ see for example the estimates for the least primitive root $\bmod p$ – reuns Sep 26 '19 at 1:04
• @GerryMyerson do you mean to say there exist primes $p$ such that $\phi(p-1)/(p-1)$ can be made arbitrarily close to 0? Or that no lower-bound is known? – user256340 Sep 26 '19 at 1:10
• See P. J. Stephens' result cambridge.org/core/journals/mathematika/article/… The average is known and its around 0.37 – Sungjin Kim Sep 26 '19 at 1:41

One can certainly find integers $$n$$ with

$$\frac{\varphi(n)}{n} \sim \frac{e^{-\gamma}}{\log \log(n)}$$

(for example, the product of the first $$k$$ primes), and this is best possible. By Dirichlet's theorem, there exists a prime

$$p \equiv 1 \mod n.$$

Linnik proved there exists such a prime $$p < n^{C}$$ for some absolute fixed constant $$C$$ whose value will not be important. (Allowing an extra constant factor, I think the best known bound has $$C$$ roughly aroung $$5$$.) Since

$$\frac{\varphi(p-1)}{\varphi(n)} = \frac{p-1}{n} \prod_{q|n}^{q \nmid p-1} \left(1 - \frac{1}{q} \right) \le \frac{p-1}{n},$$

it follows that, for such a $$p < n^C$$ (so $$n > p^{1/C}$$),

$$\frac{\varphi(p-1)}{p-1} \le \frac{\varphi(n)}{n} \sim \frac{e^{-\gamma}}{\log \log(n)} \le \frac{e^{-\gamma}}{\log \log(p^{1/B})} \sim \frac{e^{-\gamma}}{\log \log(p)}.$$

Hence

$$\liminf \frac{ \log \log p \cdot \varphi(p-1)}{p-1} = e^{-\gamma}.$$

On the other end, standard sieving certainly shows you can find primes $$p$$ such that $$p-1 = 2 q_1 \ldots q_k$$ where all the $$q_k$$ are greater than (say) $$p^{1/100}$$. For these primes, you certainly have

$$\frac{\varphi(p-1)}{p-1} \sim \frac{1}{2}.$$

Random example: $$p = 106696591 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11^2 \cdot 13 \cdot 17 \cdot 19 + 1,$$ $$\frac{\varphi(p-1)}{p-1} \sim 0.17\ldots$$ $$\frac{e^{-\gamma}}{\log \log p} = 0.19 \ldots$$

• Your inequality $\phi(p-1)/(p-1)\le \phi(n)/n$ suggests that the liminf is $\le e^{\gamma}$. – Sungjin Kim Sep 26 '19 at 15:54
• I meant $\liminf (\log\log p)\phi(p-1)/(p-1)\le e^{-\gamma}$ – Sungjin Kim Sep 26 '19 at 18:29
• Obviously $\liminf (\log \log p) \phi(p-1)/(p-1) \ge \liminf (\log \log n) \phi(n)/n = e^{-\gamma}.$ – user708710 Sep 28 '19 at 1:54
• Thank you very much! – Sungjin Kim Sep 28 '19 at 2:38