Reused writeup on Math-5661 (gpt pro 5.2)

Erdős Problem 456 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/456

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/456.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/456.tex.

FORMAL RESTATEMENT

For each integer $n\ge 1$ let

• $p_n$ be the smallest prime congruent to $1\pmod n$;
• $m_n$ be the smallest positive integer $m$ such that $n\mid \phi(m)$, where $\phi$ is Euler's totient.

Questions:

1. Is $m_n<p_n$ for almost all $n$?
2. Does $p_n/m_n\to\infty$ for almost all $n$?
3. Are there infinitely many primes $p$ such that $p-1$ is the only $n$ for which $m_n=p$?

QUICK LITERATURE/CONTEXT CHECK

Only what is stated in the problem text is used: Linnik's theorem implies $p_n\le n^{O(1)}$; trivially $m_n\le p_n$; if $n=q-1$ for a prime $q$ then $m_n=p_n$; Erdős claims it is easy to show infinitely many $n$ with $m_n<p_n$, and that $m_n/n\to\infty$ for almost all $n$; van Doorn notes that for $n=2^{2k+1}$ one has $m_n\le 2n$ and $p_n\ge 2n+1$. No additional external results are imported here.

ATTACK PLAN

• Prove the basic inequality $m_n\le p_n$ and characterize the equality case $n=q-1$.
• Prove van Doorn's explicit infinite family $n=2^{2k+1}$ giving strict inequality $m_n<p_n$.
• FAST REALITY CHECK: compute $(p_n,m_n)$ for small $n$.

WORK

Fast reality check (exact computation for small $n$). By brute force for $2\le n\le 100$ (exact primality and totient), there are $14$ values with $m_n<p_n$; the first few are: \[ (n,p_n,m_n,p_n/m_n)=(8,17,15,1.133\dots),\ (20,41,25,1.64),\ (24,73,35,2.085\dots),\ (32,97,51,1.901\dots),\ (55,331,121,2.735\dots). \] Many $n$ (including all $n=q-1$ with prime $q\le 101$) have $m_n=p_n$ in this range.

Lemma 456.1 (trivial upper bound $m_n\le p_n$). For every $n\ge 1$, $m_n\le p_n$.

Proof. By definition, $p_n$ is a prime with $p_n\equiv 1\pmod n$, so $n\mid (p_n-1)$. Since $\phi(p_n)=p_n-1$, we have $n\mid \phi(p_n)$, so $p_n$ is an admissible candidate in the defining minimum for $m_n$. Therefore $m_n\le p_n$. $\square$

Lemma 456.2 (the equality case $n=q-1$). If $n=q-1$ for some prime $q$, then $m_n=p_n=q$.

Proof. If $n=q-1$, then $q\equiv 1\pmod n$, so $p_n\le q$. On the other hand, any prime $p\equiv 1\pmod n$ has the form $p=1+tn$ with $t\ge 1$, hence $p\ge 1+n=q$. Thus $p_n=q$.

For $m_n$, note that $m=q$ satisfies $n\mid \phi(q)=q-1=n$, so $m_n\le q$. Conversely, if $m<q$ then $\phi(m)\le m-1<q-1=n$, so $\phi(m)$ cannot be divisible by $n$. Thus no $m<q$ works, and $m_n\ge q$. Therefore $m_n=q=p_n$. $\square$

Lemma 456.3 (van Doorn family $n=2^{2k+1}$ gives strict inequality). Let $k\ge 1$ and $n:=2^{2k+1}$. Then \[ m_n\le 2n\qquad\text{and}\qquad p_n\ge 2n+1. \] In particular $m_n<p_n$ for all such $n$, so there are infinitely many $n$ with $m_n<p_n$.

Proof. First, take $m:=2n=2^{2k+2}$. Then \[ \phi(m)=\phi(2^{2k+2})=2^{2k+1}=n, \] so $n\mid\phi(m)$. Hence $m$ is admissible and $m_n\le m=2n$.

Second, any prime $p\equiv 1\pmod n$ has the form $p=1+tn$ for some integer $t\ge 1$. If $t=1$ then $p=n+1=2^{2k+1}+1$. Since $2\equiv -1\pmod 3$, we have $2^{2k+1}\equiv (-1)^{2k+1}\equiv -1\pmod 3$, hence $2^{2k+1}+1\equiv 0\pmod 3$. For $k\ge 1$, $n+1>3$, so $n+1$ is composite and cannot equal $p_n$. Therefore $t\ge 2$, giving $p_n\ge 1+2n=2n+1$. Combining with $m_n\le 2n$ yields $m_n<p_n$. $\square$

VERIFICATION

• Lemma 456.1 uses only $\phi(p)=p-1$ for prime $p$.
• Lemma 456.2's lower bound $m_n\ge q$ uses $\phi(m)\le m-1$ for $m\ge 2$; this is elementary and correct.
• Lemma 456.3 checks the congruence modulo $3$ carefully and requires $k\ge 1$ so that $n+1>3$.
• The computed data agrees with Lemma 456.3 for $n=8,32,128$ (in the computed range $n=8,32$): $m_8=15\le 16<p_8=17$ and $m_{32}=51\le 64<p_{32}=97$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. Always $m_n\le p_n$ (Lemma 456.1). Equality holds for $n=q-1$ with prime $q$ (Lemma 456.2). There are infinitely many $n$ with strict inequality $m_n<p_n$, e.g. $n=2^{2k+1}$ with $k\ge 1$ (Lemma 456.3).

(ii) First gap (crisp). Prove (or disprove) that $m_n<p_n$ for almost all $n$, i.e. that the equality family $n=q-1$ (and any other possible equality families) has density $0$ among the integers.

(iii) Top 3 next moves.

1. Classify all $n$ for which $m_n=p_n$ can occur: determine necessary/sufficient structural conditions on $n$ that force the minimal $m$ with $n\mid\phi(m)$ to be prime.
2. For typical $n$, attempt to upper bound $m_n$ by constructing small $m$ with $\phi(m)$ highly divisible (e.g. $m$ with many small prime factors), and compare with available upper bounds on $p_n$.
3. Computation: tabulate $p_n/m_n$ for $n$ up to, say, $10^5$ (with optimized totient/divisibility search) to test whether $p_n/m_n$ appears to grow on a density-$1$ set.

(iv) Minimal counterexample structure. A minimal counterexample to "$m_n<p_n$ for almost all $n$" would require a positive-density set of $n$ such that the smallest $m$ with $n\mid\phi(m)$ is itself prime and is also the smallest prime $\equiv 1\pmod n$; such $n$ would likely force unusually large constraints on $\phi(m)$ for all $m<p_n$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.