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 enter image description here

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.

  • $\begingroup$ See also en.wikipedia.org/wiki/Euler%27s_totient_function#Growth_rate $\endgroup$ – lhf Sep 25 '19 at 23:49
  • 2
    $\begingroup$ 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. $\endgroup$ – Gerry Myerson Sep 26 '19 at 0:47
  • 1
    $\begingroup$ 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$ $\endgroup$ – reuns Sep 26 '19 at 1:04
  • $\begingroup$ @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? $\endgroup$ – user256340 Sep 26 '19 at 1:10
  • 2
    $\begingroup$ See P. J. Stephens' result cambridge.org/core/journals/mathematika/article/… The average is known and its around 0.37 $\endgroup$ – 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)}.$$


$$\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$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy