Problem Statement
Let $p(a,d)$ be 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\]for $\gg \phi(d)$ many values of $a$?
Categories:
Number Theory
Progress
Erdős [Er49c] could prove this is true for an infinite sequence of $d$. He also proved that, for any $\epsilon>0$,\[p(a,d)< \epsilon \phi(d)\log d\]for $\gg_\epsilon \phi(d)$ many values of $a$.Source: erdosproblems.com/971 | Last verified: January 19, 2026