Are there $\gg\phi(d)$ residues $a$ with least prime $p(a,d)>(1+c)\phi(d)\log d$? (Erdős #971)
Statement
For $a$ coprime to $d$, let $p(a,d)$ denote the least prime congruent to $a\pmod d$. Does there exist a constant $c>0$ such that, for all large $d$, $$p(a,d)>(1+c)\phi(d)\log d$$ holds for $\gg\phi(d)$ many residues $a$ (coprime to $d$)? Here $\phi$ is Euler's totient, and $\phi(d)\log d$ is the average order of $p(a,d)$ over the admissible residues $a$.
Acceptance. FULLY RESOLVES: a proof (machine-checkable preferred, else a complete written proof) either establishing the existence of a constant $c>0$ for which $p(a,d)>(1+c)\phi(d)\log d$ holds for $\gg\phi(d)$ residues for all large $d$, or disproving it. ADVANCES (proof required): (a) prove the statement for a set of moduli $d$ of positive density, strictly improving on Erdős's 'infinite sequence of $d$'; (b) establish a quantitative lower bound tending to a positive proportion for the number of residues $a$ with $p(a,d)>(1+c)\phi(d)\log d$ for a specified class of $d$; or (c) a rigorous conditional result (e.g. under GRH), clearly flagged as such. Deliver the proof or formalization; numerical distribution tables may support but do not by themselves constitute an advance on this proof-shaped question.
Background
Posed by Erdős [Er49c] and recorded in [Er65b]; listed as open on erdosproblems.com/971 (fetched 2026-07-21, status 'open'). By the prime number theorem for arithmetic progressions, $p(a,d)$ has average $\sim\phi(d)\log d$ over the $\phi(d)$ residues coprime to $d$, so the question asks whether a positive proportion of residues have least prime bounded below by a fixed factor $(1+c)$ above this average. Erdős [Er49c] proved the statement holds for an infinite sequence of $d$, and established the companion small-side result: for every $\epsilon>0$, $p(a,d)<\epsilon\phi(d)\log d$ for $\gg_\epsilon\phi(d)$ many $a$. A formalisation of the statement exists in the DeepMind formal-conjectures library. Related data appear in OEIS A226521. Attacker's tool: large-scale tabulation of $p(a,d)$ across residue classes for many moduli $d$ to probe the empirical distribution of $p(a,d)/(\phi(d)\log d)$, informing sieve / large-sieve lower bounds and connections to Linnik's theorem on the least prime in a progression.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #971 (T. F. Bloom) | website |
| REF-02 | OEIS A226521 — least prime in the progression a mod d data | website |
| REF-03 | Lean formalisation of Erdős #971 (formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.