7
$\begingroup$

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.

$\endgroup$
2

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I'd say that is a quite non-standard interpretation of "primitive root", so I'll change the question accordingly. For example, Wikipedia says "Gauss proved[4] that for any prime number p (with the sole exception of p = 3), the product of its primitive roots is congruent to 1 modulo p." Which doesn't make any sense if you accept an infinite number of primitive roots. $\endgroup$
    – gnasher729
    May 2, 2014 at 15:41
  • $\begingroup$ I think the question is whether any prime less than p can be a primitive root mod $p$. $\endgroup$
    – fretty
    May 2, 2014 at 15:47
  • $\begingroup$ No, my question is whether for every prime p other than 2, there is a prime number among the primitive roots of p. Yours is an interesting but different question. $\endgroup$
    – gnasher729
    May 2, 2014 at 16:55
  • 1
    $\begingroup$ Anyone voting this up: This reply does not in any way answer the question. $\endgroup$
    – gnasher729
    May 4, 2014 at 21:19
  • 2
    $\begingroup$ @gnasher729 There are infinitely many integers that represent a given residue class modulo $n$. When we speak of the product of primitive roots, we mean their residue classes. When we speak of a primitive root being prime, we mean being represented by a prime integer (note that primitive roots, as residue classes, are units hence cannot be prime in the ring of integers mod $n$). $\endgroup$
    – anon
    May 4, 2014 at 22:09
3
$\begingroup$

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$).

$\endgroup$
2
  • 1
    $\begingroup$ I think it also works if p = 4q + 1 for some odd prime q. Let g be a primitive root, and s = g^q (modulo p). If s > 2q then replace g with p-g, and s <= 2q. x is a primitive root iff x^q = s or -s (modulo p) and x ≠ s, x ≠ p - s, and x ≠ p - 1. If (ab)^q = +/- s (modulo p) then either a^q or b^q is +/- s (modulo p). Take the smallest primitive root which is not divisible by an odd power of s, and that primitive root is prime or has a prime factor which is a primitive root. This fails if p = 6q + 1. $\endgroup$
    – gnasher729
    May 8, 2014 at 0:54
  • $\begingroup$ Yes, I agree. In fact, I think $2$ is always a generator for such a prime. For note that $(s+1)^{2} = s^{2}+1 + 2s$ is a residue. But $s^{2}+1 = 0,$ so $2s$ is residue. But $s$ is a non-residue, so $2$ is a non-residue, and the order of $2$ is divisible by $4$. However $2^{4}-1 = 15$ is not divisible by $p,$ so $2$ does not have order exactly $4,$ and must have order $4q,$ so is primitive. $\endgroup$ May 8, 2014 at 6:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .