Smallest prime $\equiv 1\ (\mathrm{mod}\ n)$ versus smallest $m$ with $n\mid\phi(m)$ (Erdős #456)
Statement
For a positive integer $n$, let $p_n$ be the smallest prime $\equiv 1\pmod{n}$, and let $m_n$ be the smallest positive integer with $n\mid\phi(m_n)$, where $\phi$ is Euler's totient function. Since $\phi(p_n)=p_n-1$ is divisible by $n$, one always has $m_n\leq p_n$. Three questions of Erdős: (i) Is $m_n<p_n$ for almost all $n$? (ii) Does $p_n/m_n\to\infty$ for almost all $n$? (iii) Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?
Acceptance. FULLY RESOLVES (proof-shaped): a complete proof — machine-checkable (Lean/Coq) preferred, else fully written — settling any one of the three questions: that $\{n:m_n<p_n\}$ has density $1$ (or that it fails on a positive-density set); that $p_n/m_n\to\infty$ on a density-$1$ set (or its negation); or that infinitely many (or only finitely many) primes $p$ have $p-1$ as the unique $n$ with $m_n=p$. ADVANCES: an unconditional density lower bound for $\{n:m_n<p_n\}$ strictly improving whatever explicit density is recorded in the background; a proof of (i), (ii) or (iii) under a clearly stated hypothesis (e.g. GRH); or a reproducible computation of $p_n$ and $m_n$ over an extended range giving certified counts of the exceptional sets and, for (iii), an extended table of the primes $p$ for which $p-1$ is the unique $n$ with $m_n=p$ — with the program and a certificate. Deliver the proof, or the search code plus certified statistics.
Background
Posed by Erdős [Er79e, p.80] and reiterated by Erdős–Graham [ErGr80, p.91]; listed as open on erdosproblems.com/456 (fetched 2026-07-21, status 'open'). Linnik's theorem gives $p_n\leq n^{O(1)}$, and trivially $m_n\leq p_n$. When $n=q-1$ for a prime $q$ one has $m_n=p_n$. Erdős [Er79e] states it is 'easy to show' both that $m_n<p_n$ for infinitely many $n$ and that $m_n/n\to\infty$ for almost all $n$. In the site comments, van Doorn observes that if $n=2^{2k+1}$ then $m_n\leq 2n$ while $p_n\geq 2n+1$, so $m_n<p_n$ for those $n$. Relevant OEIS sequences are A034694 (least prime $\equiv 1\bmod n$) and A061026 (least $m$ with $n\mid\phi(m)$). The problem is formalized in Lean; a neighbouring SciNet problem concerns totient values whose smallest preimages grow superlinearly (Erdős #51). No prize. Attacker's tool: analytic number theory for primes in arithmetic progressions (Linnik, Bombieri–Vinogradov) toward the density statements (i)–(ii), together with large-scale computation of $p_n$ and $m_n$ to gather statistics and to search for the primes required in (iii).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #456 (T. F. Bloom) | website |
| REF-02 | OEIS A034694 — least prime ≡ 1 (mod n) | website |
| REF-03 | OEIS A061026 — least m such that n divides phi(m) | website |
| REF-04 | Lean formalisation of Erdős #456 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.