A prime primitive root below every prime: does one always exist? (Erdős #985)
Statement
Recall that $g$ is a primitive root modulo a prime $p$ if $g$ generates the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, i.e. the powers $g,g^2,\ldots,g^{p-1}$ run through every nonzero residue modulo $p$ (equivalently $g$ has multiplicative order exactly $p-1$). Is it true that for every prime $p$ there is a prime $q<p$ which is a primitive root modulo $p$?
Acceptance. FULLY RESOLVES (OPEN, proof-shaped): a complete proof — machine-checkable (Lean/Coq, e.g. discharging the existing formal-conjectures stub) preferred, otherwise a full written proof — that for every prime $p$ there is a prime $q<p$ that is a primitive root modulo $p$; OR a single explicit prime $p$ together with a program-checkable certificate that no prime $q<p$ is a primitive root modulo $p$ (a finite counterexample disproving the statement). ADVANCES: with reproducible code, certify that every prime $p$ up to a new record bound $N$ admits a prime primitive root $q<p$ — state the current verified bound in words and require strictly larger; OR a conditional proof under a clearly stated hypothesis (e.g. GRH). Deliver the proof or formal artifact, or the counterexample prime with its non-primitivity certificate, or the search program together with the attained bound $N$.
Background
Posed by Erdős [Er65b]; listed as open on erdosproblems.com/985 (fetched 2026-07-21, status 'open'). The problem sits alongside Artin's conjecture on primitive roots, which asserts that a fixed integer that is neither $-1$ nor a perfect square (e.g. $2$) is a primitive root for infinitely many primes: Hooley [Ho67b] proved Artin's conjecture assuming the Generalised Riemann Hypothesis, and Heath-Brown [He86b] proved unconditionally that at least one of $2,3,5$ is a primitive root for infinitely many primes. Those results fix the base and vary the prime; #985 instead fixes $p$ and asks only that SOME prime below $p$ be a primitive root modulo $p$. Since there are $\phi(p-1)$ primitive roots in $\{1,\ldots,p-1\}$, one expects a prime among them for every $p$, but this is unproven. The relevant data is OEIS A002233 (least prime primitive root of the $n$-th prime). No cash prize. A formalised statement of the problem exists in the google-deepmind/formal-conjectures Lean repository. Attacker's tool: for each prime $p$, enumerate the primes $q<p$ and test whether any has order $p-1$ modulo $p$; a single prime $p$ admitting no prime primitive root below it would be a finite, machine-checkable counterexample, so the realistic lines of attack are extending the exhaustively verified range and (failing that) an analytic proof, possibly GRH-conditional.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #985 (T. F. Bloom) | website |
| REF-02 | OEIS A002233 — least prime primitive root of the n-th prime | website |
| REF-03 | Lean formalisation (google-deepmind/formal-conjectures) of Erdős #985 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.