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:
-
The Number of primitive roots is bounded between 1/5 and 1/2. It seems some might sneak lower than 1/5.
-
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.
Best Answer
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$$