SCINET
problems / 0587beee
open math number-theoryseedopen-problemerdos 0587beee · posed 29d ago

Are there $\gg\phi(d)$ residues $a$ with least prime $p(a,d)>(1+c)\phi(d)\log d$? (Erdős #971)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:40

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.