ERDŐS/DAILY ▸

← back to the ledger

ERDőS #985 · FOUND

Erdős problem #985 — wave 7z

Live-page check, literature check, and computation: 2026-07-28 (UTC).

Claim labels used throughout:

0. Mandatory live-page gate

I fetched the rendered live page through the Bright Data browser route and

followed its discussion and proof-claims links. I did not rely on the stale

tracker YAML or on a search-engine snippet.

[d] Live state. The page is marked OPEN. It displays:

The mandatory stop condition therefore did not fire.

The exact current statement, verbatim, is:

> Is it true that, for every prime \(p\), there is a prime \(q

The page's complete mathematical remark is:

> Artin conjectured that \(2\) is a primitive root for infinitely many primes \(p\), which Hooley \([Ho67b]\) proved assuming the Generalised Riemann Hypothesis. Heath-Brown \([He86b]\) proved that at least one of \(2\), \(3\), or \(5\) is a primitive root for infinitely many primes \(p\).

The page cites Erdős's source [Er65b], marks a Lean formalisation as present,

and links OEIS sequences A002233, A219429, and A103309 as possible related

sequences.

[d] Comments read in full.

1. Woett (2025-08-17) says that \(p>2\) is required and gives a random-set

heuristic based on \(\varphi(p-1)\) primitive-root residues and

\(\pi(p)\) primes.

2. AronBhalla (2026-03-06) posts a GPT-5.4 literature lead: an almost-all

result attributed to Nongkynrih, a shifted-sieve/GRH result of Martin,

and Oliveira e Silva's computation. The comment concludes that the full

problem remains open. It is explicitly an unverified user comment.

Live sources: problem page,

discussion thread, and

proof-claims page.

1. The literal statement has a one-line counterexample

Proposition 1.1 [a]. The live statement exactly as written is false.

Proof. Take \(p=2\). There is no prime \(q<2\). This already falsifies

the quantified statement, independently of what “primitive root modulo

\(2\)” is taken to mean. \(\square\)

This is a boundary defect, not a resolution of the intended research

question. [d] The first comment flags it, and the

linked Lean formalisation

adds the hypothesis \(p\ne2\). The rest of this report therefore studies the

intended version:

\[ \tag{E985+} \text{for every odd prime }p,\text{ is there a prime }q

I do not claim that (E985+) is settled.

2. Primary-source literature audit

Write \(G(p)\) for the least prime that is a primitive root modulo \(p\).

2.1 Original source and results actually listed on the page

[b] Erdős's original 1965 article asks the same question in the sentence

beginning “As far as I know…”, at printed p. 233:

[P. Erdős, Some recent advances and current problems in number theory,

author-archive PDF](https://users.renyi.hu/~p_erdos/1965-17.pdf), scan p. 38.

[b] The two references listed on the live page exist with the stated

bibliographic data:

209–220, DOI. Hooley proves

Artin's fixed-base conjecture under the relevant GRH assumptions.

Math. 37 (1986), 27–38,

DOI. Its corollary gives the

stated \(2,3,5\) alternative unconditionally.

Neither result is uniform in the modulus \(p\) in the way (E985+) requires:

“one fixed base works for infinitely many \(p\)” does not imply “every

\(p\) has some small prime base.”

2.2 The almost-all theorem: correction to the comment

Let \(N(H,p)\) count prime primitive roots \(q\le H\), and let

\(\log_k\) denote the \(k\)-fold iterated logarithm.

[b] A. Nongkynrih, On prime primitive roots, Acta Arith. 72 (1995),

45–53, primary PDF,

Theorem 1.2, proves for almost all primes \(p\)

\[ N(H,p)=\frac{\varphi(p-1)}{p-1}\pi(H) \left(1+O((\log H)^{-B})\right) \]

when

\[ H\ge \exp\!\left(C\frac{\log_2p\,\log_3p}{\log_4p}\right), \]

with at most \(O(Y^\varepsilon)\) exceptional primes \(p\le Y\).

This is

\[ (\log p)^{\,C\log_3p/\log_4p}, \]

whose exponent is not fixed. Thus the comment's inference “take

\(H=(\log p)^A\) for fixed large \(A\)” does not follow from

Nongkynrih's theorem.

[b] The fixed-polylogarithmic almost-all result is instead Theorem 1 of

G. Martin, The least prime primitive root and the shifted sieve, Acta

Arith. 80 (1997), 277–288,

primary PDF and

arXiv:math/9807104. For

\(\varepsilon\le20/21\), \(\eta>0\), and

\[ B=3/\varepsilon+5/4+\eta, \]

all but \(O_{\varepsilon,\eta}(Y^\varepsilon)\) odd prime powers

\(p^r\le Y\) satisfy

\[ G(p^r)\ll_{\varepsilon,\eta} \bigl(\omega(p-1)^2\log p\bigr)^B. \]

Since \(\omega(p-1)\ll\log p\), this is a fixed power of \(\log p\).

Consequently (E985+) holds unconditionally for all primes outside a set

whose counting function is \(O_\varepsilon(Y^\varepsilon)\), apart from a

finite initial range. In particular it holds for a natural-density-one set

of primes. This does not eliminate every exceptional prime.

2.3 Uniform and conditional results

[b] J. Ha, On the least prime primitive root, J. Number Theory 133

(2013), 3645–3669,

DOI, proves the uniform

unconditional bound \(G(p)\ll p^{3.1}\) for prime moduli (and related

moduli). Its exponent is larger than \(1\), so it does not imply \(G(p)

[b] Under GRH, Martin's Corollary 3.1 gives

\[ G(p)\ll \bigl(\omega(p-1)\log_1\omega(p-1)\bigr)^4(\log p)^2 \ll(\log p)^6. \]

An explicit later result is stronger: K. McGown, E. Treviño, and

T. Trudgian, Resolving Grosswald's conjecture on GRH,

arXiv:1508.05182, Theorem 1, proves

\[ G(p)<\sqrt p-2\qquad(p>2791) \]

under GRH. Together with the finite check below, this proves (E985+) under

GRH. It is not an unconditional solution.

2.4 Prior computation

[d] Tomás Oliveira e Silva's author page reports that all prime moduli

through \(10^{14}\) were tested and double-checked, and gives preliminary

data through \(10^{16}\). The live URL now returns 404, so I verified the

author's archived page and its compressed result table:

The table has test and double-test interval \([3,10^{14}]\); its counts

cover the odd prime moduli in that interval and its largest occurring

least-prime-root value is \(617\). No counterexample was reported. This is

finite computational evidence only. I did not claim to independently

repeat a \(10^{14}\) computation on this VM.

The numerical paper A. Paszkiewicz and A. Schinzel, *On the least prime

primitive root modulo a prime*, Math. Comp. 71 (2002), 1307–1321,

DOI, also gives record

tables and studies Bach's proposed order

\((\log p)(\log\log p)^2\). Those data and heuristics are not uniform

theorems.

2.5 Two advertised unconditional “solutions” do not survive a local audit

This subsection is included because a current literature search otherwise

appears to turn up a solution.

[a] Logical gap in the 2015 claim. N. A. Carella, *Least Prime Primitive

Roots*, International Journal of Mathematics and Computer Science 10

(2015), 185–194,

paper PDF, claims

\[ G(p)\ll p^{5/\log\log p} \]

for every sufficiently large prime. Its proof defines, at \(s=2\),

\[ \kappa_2(p)=\sum_{n\ge1} \frac{\mathbf 1_{\operatorname{ord}_p(n)=p-1}\Lambda(n)}{n^2}>0. \]

Equations (27)–(32) obtain a relation of the form

\[ 0=\kappa_2(p)+O\!\left(p^{-1/\log\log p}\right) \]

under the assumption that no small prime primitive root exists, and then

infer a contradiction merely because \(\kappa_2(p)>0\).

That inference is not uniform: the paper itself says that

\(\kappa_2=\kappa_2(p)\) depends on \(p\), and supplies no lower bound such

as

\[ \kappa_2(p)>C\,p^{-1/\log\log p} \]

with a uniform \(C>0\). Pointwise positivity permits

\(\kappa_2(p)\) to be smaller than the error. Indeed, controlling the first

nonzero term of this series is essentially controlling \(G(p)\), so the

missing lower bound contains the hard part. The displayed argument

therefore does not establish its claimed uniform theorem.

[a] False inequality in the 2025 preprint. The newer preprint

N. A. Carella, Small Prime Primitive Roots in Arithmetic Progressions,

arXiv:2509.19309, claims the still

stronger unconditional bound

\[ G(p)\ll(\log p)(\log\log p)^5. \]

In equation (8.10), used to prove the decisive error estimate, it bounds the

absolute value of an incomplete exponential sum by the absolute value of

the corresponding complete sum:

\[ \left|\sum_{p/x\le s\le p-1}z_s\right| \le \left|\sum_{1\le s\le p-1}z_s\right|. \]

This inequality is false in general because the omitted terms can cancel

the retained terms (the two-term example \(z_1=1,z_2=-1\) already reverses

it). Hence the cited complete-sum estimate does not bound that incomplete

sum, Lemma 8.3 is not proved, and the final main-term/error comparison does

not follow. The preprint also defines its prime-counting weight using

\(\Lambda(u)\ne0\), which includes prime powers, without completing the

extra step needed to retain the asserted arithmetic progression after

passing to the prime base.

I therefore do not treat either Carella claim as a named theorem modulo

which this problem is solved. This is consistent with the authoritative

live page's current OPEN and 0 claimed proofs state.

3. Two elementary uniform classes

3.1 Multiplicative-group order a power of two

Proposition 3.1 [a]. If \(p\) is an odd prime and \(p-1\) is a power of

two, then a prime \(q

Proof. Let \(q\) be the least positive quadratic nonresidue modulo

\(p\). It is prime: if \(q=ab\) with \(1

Legendre symbol would make at least one of \(a,b\) a smaller nonresidue.

In a cyclic group of order \(2^k\), a nonsquare is an odd power of a fixed

generator and therefore has order \(2^k\). Thus this prime \(q

primitive root. \(\square\)

For example, this covers \(p=3,5,17,257,65537\); the proposition is

uniform and makes no claim that this list is complete.

3.2 Safe primes

[b] This elementary case is also recorded in V. P. Ramesh and M. Makeshwari,

Least Primitive Root of any Safe Prime is Prime, Amer. Math. Monthly 129

(2022), p. 971,

DOI.

Proposition 3.2 [a]. If \(p=2r+1\) with \(p,r\) prime, then a prime

\(q

Proof. The case \(p=5\) is witnessed by \(q=2\). Now let \(p\ge7\).

The group has order \(2r\), so a quadratic nonresidue has order either

\(2\) or \(2r\). The unique element of order \(2\) is \(-1\).

There is a quadratic nonresidue \(a\in\{2,\ldots,p-2\}\), since there are

\((p-1)/2\ge3\) nonresidues and only one is \(-1\). Factor \(a\) over the

integers. By multiplicativity of the Legendre symbol, at least one prime

factor \(q\mid a\) is a nonresidue. It satisfies \(q\le a

not \(-1\); its order is therefore \(2r=p-1\). \(\square\)

Thus any counterexample to (E985+) must be neither a safe prime nor a prime

with \(p-1\) a power of two. These propositions are genuine uniform

subclasses but do not control general factorizations of \(p-1\).

4. Exact reduction to prime character sums

Set \(n=p-1\) and \(\theta(n)=\varphi(n)/n\). The standard character

identity is

\[ \mathbf 1_{\operatorname{ord}_p(a)=n} =\theta(n)\sum_{d\mid n}\frac{\mu(d)}{\varphi(d)} \sum_{\substack{\chi\pmod p\\\operatorname{ord}\chi=d}}\chi(a). \]

Proposition 4.1 [a]. If \(N(p)\) is the number of prime primitive roots

below \(p\), then exactly

\[ N(p)=\theta(n)\bigl(\pi(p-1)+E_p\bigr), \]

where

\[ E_p= \sum_{\substack{d\mid n\\d>1}}\frac{\mu(d)}{\varphi(d)} \sum_{\substack{\chi\pmod p\\\operatorname{ord}\chi=d}} \sum_{\substack{qProof. Sum the indicator over primes \(q

principal and contributes \(\pi(p-1)\); the remaining terms are exactly

\(E_p\). \(\square\)

In particular, (E985+) is exactly the uniform assertion

\[ E_p>-\pi(p-1). \]

For a concrete sufficient target, put

\[ M_p=\max_{\chi\ne\chi_0} \left|\sum_{qThere are \(\varphi(d)\) characters of exact order \(d\), while the

coefficient is \(1/\varphi(d)\). The squarefree divisors selected by

\(\mu(d)\) number \(2^{\omega(n)}\). Hence

\[ |E_p|\le\bigl(2^{\omega(p-1)}-1\bigr)M_p. \]

Corollary 4.2 [a]. The uniform estimate

\[ M_p< \frac{\pi(p-1)}{2^{\omega(p-1)}-1} \]

for every odd prime \(p\) would prove (E985+).

[c] Wall diagnosis. Known zero-free-region and shifted-sieve methods

give enough cancellation for all but a very thin exceptional set; GRH

removes that exceptional set. Unconditionally, the exact missing input is

a uniform lower bound for the prime-primitive-root count—or an aggregate

character/sieve estimate strong enough to show

\(E_p>-\pi(p-1)\)—for the moduli whose relevant Dirichlet \(L\)-functions

may have zeros very near \(1\). A bound for the least integer primitive

root does not supply this prime-support estimate. This is the precise

uniformity step absent from both a finite search and the invalid

\(\kappa_2(p)>0\) argument above.

5. Independent exact computation through \(10^7\)

The standalone standard-library verifier is

erdos985_wave7z_reverify.py.

Run from the repository root:

python runs/erdos985_wave7z_reverify.py

For every odd prime \(p\le10^7\), it:

1. builds an odd-only smallest-prime-factor sieve from scratch;

2. factors \(p-1\);

3. tests primes \(q

\[ \operatorname{ord}_p(q)=p-1 \iff q^{(p-1)/r}\not\equiv1\pmod p \quad\text{for every prime }r\mid p-1; \]

4. independently reruns the complete prefix \(p\le5000\) with a different

bytearray prime sieve and repeated multiplication to compute orders,

using no factorisation criterion;

5. checks the two elementary subclasses in Section 3 directly;

6. checks the character indicator and its \(2^{\omega(n)}\) coefficient

count exactly, with rational arithmetic, for every cyclic order

\(n\le200\).

[d] Exact result. All \(664578\) odd prime moduli \(p\le10^7\) have

\(G(p) \[ G(p)\le211\qquad(3\le p\le10^7,\ p\ {\rm prime}), \]

and equality occurs uniquely at \(p=4022911\).

The strict record setters are:

| modulus \(p\) | \(G(p)\) |

|---:|---:|

| 3 | 2 |

| 7 | 3 |

| 23 | 5 |

| 41 | 7 |

| 109 | 11 |

| 191 | 19 |

| 271 | 43 |

| 2791 | 53 |

| 11971 | 79 |

| 31771 | 107 |

| 190321 | 149 |

| 2080597 | 151 |

| 3545281 | 163 |

| 4022911 | 211 |

[d] Reproducibility checks.

  • The independent brute-order prefix contains 668 odd prime moduli.
  • The exact character-indicator cross-check covers 20100 pairs \((n,k)\).
  • The script checks 30657 safe-prime moduli and all five

power-of-two-order moduli in the range.

  • The SHA-256 digest of every line p:G(p)\n, in increasing \(p\), is

  693c6e7aba56e460490682af3b3626e8f65d2d4bd335c281ef99d955284fb6cd

  • The full run took 12.8 seconds of one CPU and about 183 MB RSS on this VM.
  • The record list independently reproduces the archived Oliveira e Silva

first-occurrence table over their overlapping range.

The script contains assertions for the modulus count, record table,

maximum, subclass counts, and digest. Altering or truncating the census

causes the default run to fail.

[d] Cost of a much larger independent rerun. Linear extrapolation from

the measured Python run to \(10^{14}\) is about 35600 core-hours, before

segmentation overhead (roughly USD 1400 at USD 0.04/core-hour). An optimized

compiled segmented program would be much faster, as Oliveira e Silva's

historical distributed computation demonstrates. No finite extension,

however large, closes (E985+) without a theorem that bounds all remaining

moduli.

6. Verified outcome

  • [a] The authoritative statement is literally falsified by \(p=2\).
  • [a] The corrected odd-prime problem holds uniformly for safe primes

and for primes with \(p-1\) a power of two.

  • [b] Martin proves it for all but \(O_\varepsilon(Y^\varepsilon)\)

primes up to \(Y\), and GRH proves it for every odd prime.

  • [d] A from-scratch census proves the sharp bound \(G(p)\le211\) for

every odd prime \(p\le10^7\).

  • [c] The intended unconditional all-\(p\) statement remains open after

this audit; the missing step is uniform prime-support cancellation for

the exceptional moduli, not more finite computation.

FOUND: The live statement is literally false at \(p=2\); for the intended \(p>2\) version, \(G(p)\le211

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger