Does every prime > 2 have a primitive root that is a prime?

Question

Every prime number has a primitive root. Actually, for every prime number p a considerable percentage of the numbers from 2 to p-1 are primitive roots (with the exception p = 2 which is the only prime that has 1 as a primitive root).

Following a discussion how to find primitive roots, I thought it would be a good idea to start checking whether the small primes (2, 3, 5, 7, 11, ... ) are primitive roots because they seem to be more than average likely to be primitive roots. That obviously raises the question whether every prime p other than 2 actually has a primitive root in the range from 2 to p-1 that is prime.

Googling didn't find any answer. There doesn't seem to be an obvious answer, for example p = 41 has the primitive root 6 but neither 2 nor 3 are primitive roots (2^20 = 3^8 = 1 modulo 41). There should always be a prime primitive root because of the sheer numbers of primitive roots (p = 271 with smallest prime primitive root 43 seems quite exceptional), but a proof would be nice.

Answer 1

The answer is yes. Let $a$ be a primitive root of $p$. Then $a+kp$ is a primitive root of $p$ for every $k$. By Dirichlet's Theorem on primes in arithmetic progression, there are infinitely many primes of the form $a+kp$.

Remark: The problem of whether for any prime $p\gt 2$ there is a primitive roots $a$ with $2\le a\le p-1$ is open. I believe that the best unconditional result is that for large enough $p$, the least prime primitive root of $p$ is $\lt p^k$, for a constant $k\approx 3$. Under reasonable but unproved hypotheses (versions of GRH) one can bring this down to a power of $\log p$.

One can find some information, and references, in Greg Martin's The Least Prime Primitive Root and the Shifted Sieve.

You may also want to look at this paper, sadly behind a pay wall. There is a fair literature on the subject.

Answer 2

Probabilistically, the answer seems likely to be yes, but proving it (at least for sufficiently large $p$) might be a different matter. Here is a very special case where the answer is provably yes, in the strict sense asked for in the question. Let $p$ be a Fermat prime. Then the primitive roots (mod $p$) are the quadratic non-residues (mod $p$). Since the multiplicative group of the field of $p$-elements is cyclic of order a power of $2,$ it is generated by any element which is not a square, and obviously can't be generated by any square. There are $\frac{p-1}{2}$ quadratic residues, so there is an integer $n$ with $1 < n < p$ which is not a quadratic residue (mod $p$). Hence there must be a prime divisor $q$ of $n$ which is not a quadratic residue either. This prime $q$ must be a primitive root (mod $p$). Unfortunately, Fermat primes seem to be rather thin on the ground.

Note added later: in fact, using quadratic reciprocity, it is possible to see that $3$ is a quadratic non-residue (mod $p$) whenever $p >3$ is a Fermat prime. This is because $p \equiv 2$ (mod $3$) and $p \equiv 1$ (mod $4$). Hence $3$ is a primitive root (mod $p$) for any Fermat prime $p \geq 5.$ Clearly $2$ is a primitive root (mod $3$).

Even later edit: If $p = 2q+1$ for some odd prime $q,$ then it is again easy to see that any quadratic non-residue (mod $p$) other than $p-1$ is a primitive root (mod $p$)- possible element orders in the multiplicative group are $1,2, q$ and $2q$, and the quadratic residues other than $1$ are the elements of order $q.$ It follows that the smallest integer $n$ with $1 < n < p-1$ which is a quadratic non-residue (mod $p$) is a prime, and is a primitive root (mod $p$).