11
$\begingroup$

Given a positive integer $n > 1$, is it true that there exists infinitely many primes $p$ such that $n$ is a primitive root modulo $p$.

$\endgroup$
4
  • $\begingroup$ What is the motivation of your question? $\endgroup$ Apr 24, 2011 at 18:17
  • 9
    $\begingroup$ It's a natural question, isn't it? But I think this is wide open. See en.wikipedia.org/wiki/Artin's_conjecture_on_primitive_roots . $\endgroup$ Apr 24, 2011 at 18:22
  • $\begingroup$ Well, it would be still nice to have some discussion of the problem and not just throw up a (probably unsolved) question. $\endgroup$ Apr 24, 2011 at 18:29
  • 3
    $\begingroup$ Artin's conjecture assumes that $n$ is not a square. Otherwise it's false. $\endgroup$ Apr 24, 2011 at 18:29

2 Answers 2

21
$\begingroup$

There is a simple answer here, so someone might as well record it.

Let $n$ be a nonzero integer. If $n = -1$ or $n$ is a square then there is no prime $p > 3$ such that $n$ is a primitive root modulo $p$. There are no other obvious obstructions. (It is worth thinking for a second why we do not have to rule out $n$ being a cube, for instance: this is a nice exercise in cyclic group theory.)

There is a famous conjecture that these obvious necessary conditions are the only ones: namely Artin's Primitive Root Conjecture asserts that for any integer $n$ which is not $0$, $-1$ and not a square, there are infinitely many prime numbers $p$ such that $n$ is a primitive root modulo $p$. In fact the conjecture is more precise than this: the set of primes $p$ for which such an $n$ is a primitive root is conjectured to have positive relative density among all primes and, at least under some mild additional restrictions, this density is conjectured to be a certain specific number which is independent of $n$:

$ C = \prod_{p \text{ prime}} \left(1- \frac{1}{p(p-1)} \right)$;

this $C$ is known as Artin's constant. This conjecture was proved by C. Hooley in 1967 assuming the Generalized Riemann Hypothesis. More recently unconditional results have been given by Gupta, R. Murty and Heath-Brown which consider several numbers $n$ at a time and show that Artin's Conjecture must be true for at least one of them. But the conjecture is still open for any one fixed value of $n$.

$\endgroup$
3
  • 1
    $\begingroup$ Um, you folks do realize that I'm mostly repeating material from the wikipedia article I linked to (and Qiaochu pointed out first), right? Just so you know... $\endgroup$ Apr 25, 2011 at 13:50
  • $\begingroup$ technically -1 is a primitive root modulo p=3. I still like your answer though. $\endgroup$ Apr 27, 2011 at 20:59
  • $\begingroup$ @Greg: good point. I have changed my answer accordingly. $\endgroup$ Apr 27, 2011 at 21:08
12
$\begingroup$

It showed up in a recent question so one might wonder. The article Artin's conjecture for primitive roots, Math. Intelligencer, 10 (4) (1988) 59-67 by Ram Murty seems like a good survey. The link is to a dvi copy. It informs one that the result follows from a Generalized Riemann Hypothesis and is unconditionally true for at least one of $2,3,5.$

The first $12000$ primes for which $7$ is a primitive root run from $11$ to $378011$. This proportion $\frac{12000}{32141} \approx 0.3734$ agrees well with the theoretical expected proportion of $\prod(1-\frac{1}{p(p-1)}) \approx 0.3739$ where the product is over the primes. The distribution according to congruence class $\mod 7$ is $[1, 1748], [2, 2074], [3, 2032], [4, 2058], [5, 2065], [6, 2023].$ This slight deficit in congruence class 1 seems to hold through this range.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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