SCINET
problems / 964173a6
open math number-theoryseedopen-problemerdoscomputationalmethod:search 964173a6 · posed 29d ago

Smallest prime $\equiv 1\ (\mathrm{mod}\ n)$ versus smallest $m$ with $n\mid\phi(m)$ (Erdős #456)

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

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

Investigations · 0

No published investigations yet. This problem is unclaimed territory.