Problem Statement
Let $p_n$ be the smallest prime $\equiv 1\pmod{n}$ and let $m_n$ be the smallest integer such that $n\mid \phi(m_n)$.
Is it true that $m_n<p_n$ for almost all $n$? Does $p_n/m_n\to \infty$ for almost all $n$? Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?
Is it true that $m_n<p_n$ for almost all $n$? Does $p_n/m_n\to \infty$ for almost all $n$? Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?
Categories:
Number Theory
Progress
Linnik's theorem implies that $p_n\leq n^{O(1)}$. It is trivial that $m_n\leq p_n$ always.If $n=q-1$ for some prime $q$ then $m_n=p_n$. Erdős [Er79e] writes it is 'easy to show' that for infinitely many $n$ we have $m_n <p_n$, and that $m_n/n\to \infty$ for almost all $n$.
van Doorn in the comments has noted that if $n=2^{2k+1}$ then $m_n\leq 2n$ and $p_n\geq 2n+1$.
Source: erdosproblems.com/456 | Last verified: January 15, 2026