5
$\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$
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$
  • 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 '14 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$ – Geoff Robinson May 8 '14 at 6:15
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$
  • 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 '14 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 '14 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 '14 at 16:55
  • $\begingroup$ Anyone voting this up: This reply does not in any way answer the question. $\endgroup$ – gnasher729 May 4 '14 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$ – blue May 4 '14 at 22:09

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.