Erdős problem 828 — live-page audit, structural reduction, and exact checks

Date of investigation: 2026-07-28 (UTC).

Claim labels

I use the requested labels as follows.

• [a] elementary-rigorous: a complete argument is given here.
• [b] rigorous modulo the explicitly named theorem or checked primary source.
• [c] plausible/structural-unverified: not used as a theorem.
• [d] computational-only: exact finite computation, with its domain and checker stated.

Source/status observations are marked [b/source]. They report what the cited source says; they are not claims that an open conjecture is true.

0. Mandatory live-page gate

The rendered live page was fetched through the Bright Data browser on 2026-07-28. Direct HTTP was not substituted for the rendered page.

The exact displayed statement is:

Is it true that, for any \(a\in\mathbb{Z}\), there are infinitely many \(n\) such that \(\phi(n)\mid n+a\)?

[b/source] The live page showed:

• status OPEN;
• 0 comments;
• 0 claimed proofs;
• “Interested in collaborating: None”;
• “Currently working on this problem: None”;
• “Likes this problem: Quirren”;
• “This problem looks difficult: Dogmachine, Quirren”;
• “This problem looks tractable: None”;
• “The results on this problem could be formalisable: None”;
• “Formalised statement? Yes”;
• last edited 30 September 2025.

It separately showed “I am working on formalising the results on this problem: Ritvik_Nayak”. That is a formalisation marker, not the page's “Currently working on this problem” marker, which was None. Thus the requested stop condition was not triggered.

[b/source] The page calls this a conjecture of Graham, recalls Lehmer's conjecture that \(\phi(n)\mid n-1\) only for prime \(n\), states the elementary classification of \(\phi(n)\mid n\), and points to problem B37 in Guy's collection. Its two displayed references were:

• Paul Erdős and Underwood Dudley, *Some remarks and problems in number theory

related to the work of Euler*, Math. Mag. 56 (1983), 292–298, MR 720650 (primary PDF);

• Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed. (2004),

xviii+437, MR 2076335.

The original Erdős–Dudley paper says on journal page 295 that R. L. Graham conjectured the same statement. This independently confirms the sign and quantifiers in the live statement.

Throughout the rest of this report, \(n\) is positive, \(\phi(1)=1\), and \(\omega(n)\) is the number of distinct prime factors of \(n\).

1. Outcome

The full conjecture is not resolved. The verifiable progress is:

1. [a] Exact classification of bounded-\(\omega\) infinite families. For a

fixed nonzero shift \(a\), an infinite family whose \(\omega(n)\) is bounded exists if and only if \[ a=-1\quad\text{or}\quad a=-2^\alpha3^\beta \quad(\alpha\geq1,\ \beta\geq0). \] Moreover, after passage to an infinite subfamily it is necessarily the elementary family \(n=(-a)p\), with \(p\nmid a\) prime. Consequently, for every other nonzero shift—particularly every positive shift—any infinite family must have \(\omega(n)\to\infty\).

1. [b] A checked older theorem makes that reduction effective. Pomerance

proved that every non-regular solution with \(K=\omega(n)\) obeys \[ n<\max\{16|b|^3,\ |b|K^{\,2^K}\},\qquad b=-a. \] Banks–Güloğlu–Nevans later proved a stronger counting bound for all non-regular solutions.

1. [d] Exact \(a=1\) computation through seven prime factors. A new

standard-library checker independently enumerates the complete set \[ \begin{split} \{n:\phi(n)\mid n+1,\ \omega(n)\leq7\} =\{&1,2,3,15,255,65535,83623935,\\ &4294967295,6992962672132095\}. \end{split} \] In particular, any further \(a=1\) solution has at least eight distinct prime factors. The checker also detects and corrects a historical missing-factor typo.

1. [d] Exact finite table. Two independent totient sieves agree on every

solution for \(1\leq n\leq10^7\) and \(-20\leq a\leq20\), including a SHA-256 certificate of the entire ordered hit stream.

The first result is proved below without invoking the literature. The second identifies exactly how far the established machinery already goes. The third and fourth are reproducible from erdos828_wavew017_verify.py.

2. Literature audit

2.1 Pomerance treated the exact congruence

Put

The problem's shift \(a\) corresponds to \(b=-a\).

[b] Carl Pomerance, On the congruences \(\sigma(n)\equiv a\pmod n\) and \(n\equiv a\pmod{\phi(n)}\), Acta Arith. 26 (1975), 265–272, DOI 10.4064/aa-26-3-265-272, does the following:

• records

\[ F(0)=\{1\}\cup\{2^i3^j:i>0,\ j\geq0\}; \]

• observes that if \(b\in F(0)\), then \(bp\in F(b)\) for every prime

\(p\nmid b\);

• separates these “regular” prime-multiple solutions from the remaining

solutions;

• proves that \(F(b)\) has density zero for every fixed \(b\), and that the

non-regular part is much sparser than the regular prime family;

• proves that every \(F(b)\) has at least four elements.

This paper is directly about problem 828, although it was not listed on the live page.

[b] Carl Pomerance, On composite \(n\) for which \(\phi(n)\mid n-1\), II, Pacific J. Math. 69 (1977), 177–186, DOI 10.2140/pjm.1977.69.177, defines

For fixed nonzero \(b\), its introduction and Theorem 4 give

The same paper proves

I checked the superscripts visually on journal page 178; OCR commonly mangles \(K^{2^K}\).

[b] William D. Banks, Ahmet M. Güloğlu, and C. Wesley Nevans, On the congruence \(N\equiv A\pmod{\phi(N)}\), Integers 8 (2008), Article A59 (primary PDF), improve (2.2). Their Theorem 2 states that, for every fixed \(b\in\mathbb Z\) and every fixed \(\varepsilon>0\),

where \(\Theta\) is the least positive solution of

For the problem's positive shifts \(a>0\), \(b=-a<0\), so a positive \(n\) cannot equal \(pb\); hence (2.3) bounds the entire solution set. This proves strong sparsity, not finiteness or infinitude.

2.2 The \(a=1\) computation in the primary literature

[b] D. H. Lehmer, On Euler's totient function, Bull. Amer. Math. Soc. 38 (1932), 745–751, DOI 10.1090/S0002-9904-1932-05521-5, classifies the solutions of \(2\phi(n)=n+1\) having fewer than seven distinct prime factors. On page 750 he correctly obtains

In the summary on page 751 the factor \(17\) is accidentally omitted.

That typo propagated to Erick Wong, Computations on Normal Families of Primes, M.Sc. thesis, Simon Fraser University (1997), primary PDF, printed page 26. It is an actual arithmetic error:

Restoring \(17\) gives

These equalities are also recomputed from the prime factors by the checker.

[b/source] Wong reports a complete search of 6,826 feasible five-prime prefixes and concludes that any additional \(\phi(n)\mid n+1\) solution must have at least eight distinct prime factors. The independent computation in this report reproduces both the prefix count and the empty seven-factor row; it does not trust Wong's printed list.

2.3 Very recent exact-title preprints

[c] Two ResearchGate manuscripts by Idriss Olivier Bado were uploaded on 27 May 2026:

• Partial Results on Erdős Problem 828,

DOI 10.13140/RG.2.2.10269.27360;

• Average Shift Counts for the Divisibility \(\phi(n)\mid n+a\),

DOI 10.13140/RG.2.2.29563.07202.

They are labelled as preprints and have not been peer reviewed. The first contains the elementary negative-shift construction, fixed-support obstruction, the \(a=1\) gcd obstruction, and the classification through three prime factors; it explicitly leaves every fixed positive shift open. Those parts are subsumed by the older Pomerance results and by the from-scratch arguments below. The second develops first- and second-moment formulae over varying shifts and explicitly says its conditional “many shifts” conclusion does not imply infinitude for any prescribed shift. I do not use either preprint as a theorem.

[c] OEIS A203966/A050474 currently adds an unproved computational note that no further \(a=1\) terms occur below \(10^{31}\). I did not reproduce a search to \(10^{31}\), so that assertion is deliberately excluded from the verified results.

No peer-reviewed source located in the exact-congruence searches above gives an infinite family for a fixed positive shift, or a counterexample shift with only finitely many solutions. This is a report of the search, not a proof that no such source exists.

3. Elementary structure

3.1 Three unavoidable divisibility constraints

Suppose \(a\neq0\) and \(\phi(n)\mid n+a\).

[a] Gcd obstruction.

Indeed, the gcd divides both \(n\) and \(n+a\).

[a] Exponent obstruction. If \(p^e\Vert n\), then

Both \(n\) and \(\phi(n)\) are divisible by \(p^{e-1}\), so (3.1) applies. In particular, every prime \(p\nmid a\) occurs to exponent one.

[a] Support obstruction. If distinct primes \(p,q\mid n\) satisfy \(p\mid q-1\), then

Here \(p\mid n\), while \(q-1\mid\phi(n)\), so \(p\mid\gcd(n,\phi(n))\).

For \(a=1\), (3.2) makes \(n\) squarefree and (3.3) says that its prime support is normal: no prime in the support divides another prime minus one. If such an \(n\) is even and \(n>2\), any odd \(q\mid n\) violates normality because \(2\mid q-1\). Thus every \(a=1\) solution other than \(2\) is odd.

3.2 Classifying \(\phi(m)\mid m\)

[a]

Proof. If \(P\) is the set of distinct prime divisors of \(m\), then

For this to be an integer, \(\prod_{p\in P}(p-1)\) must divide \(\prod_{p\in P}p\). Each odd \(p\in P\) supplies a factor \(2\) to the denominator, while the squarefree numerator has only one factor \(2\). Thus \(P\) contains at most one odd prime. If it contains an odd prime \(q\), then \(2\in P\), and \(q-1\mid2q\). Since \(\gcd(q-1,q)=1\), \(q-1\mid2\), so \(q=3\). Exponents do not affect \(m/\phi(m)\), proving (3.4).

3.3 The regular infinite families

Let \(m\) satisfy (3.4), and let \(p\nmid m\) be prime. Then

[a] Therefore the shifts

all have infinitely many solutions \(n=(-a)p\). For \(a=0\), (3.4) itself is the complete infinite solution set.

3.4 Exact bounded-\(\omega\) dichotomy

Proposition [a]. Fix \(a\neq0\) and \(R\geq0\). If there are infinitely many solutions of

then \(a=-m\) for an \(m\) in (3.4), and an infinite subfamily is exactly \(n=mp\) with \(p\nmid m\) prime. Conversely, every such \(a=-m\) has this infinite family.

Proof. Pass to an infinite subsequence with a fixed number of ordered prime factors. By (3.2), the exponent of every bounded prime is bounded; after another subsequence all bounded primes and their exponents form a fixed integer \(m\). Every other prime tends to infinity and has exponent one. Thus

There must be at least one varying prime, since the \(n_j\) are distinct.

Put

For large \(j\), \(k_j>0\), and

An integer sequence that converges is eventually constant. Hence \(m/\phi(m)=K\in\mathbb Z\), and eventually \(k_j=K\). Equation (3.7) is then the exact identity

so

If \(s\geq2\), then

contradicting fixed \(a\). Thus \(s=1\), in which case \(Q_j-\phi(Q_j)=q_j-(q_j-1)=1\), and (3.10) gives \(a=-m\). Classification (3.4) and construction (3.5) finish both directions.

Consequence [a]. For every non-regular nonzero shift, and in particular for every \(a>0\), an infinite solution set can exist only by using unboundedly many distinct primes. Pomerance's bound (2.1) is an explicit quantitative version of the finiteness for each fixed \(R\).

4. Exact \(a=1\) classification through \(\omega(n)=7\)

4.1 Reduction to one equation

Let \(n>2\), \(\phi(n)\mid n+1\), and \(r=\omega(n)\leq7\). Section 3.1 shows that \(n\) is odd and squarefree. Write its primes increasingly as \(p_1<\cdots<p_r\), and let \(q_1,\ldots,q_r\) be the first \(r\) odd primes \(3,5,7,11,13,17,19\).

Since \(p_i\geq q_i\),

The exact lower margins

are all greater than \(1\). Therefore \(3\phi(n)-n>1\), hence

The quotient is an integer, so it equals \(2\):

The exceptional \(n=2\) has quotient \(3\).

This reduction and all constants in (4.1) are [a] and are rechecked by the program.

4.2 Complete exact-search algorithm

For a fixed \(r\), equation (4.2) for squarefree \(n=p_1\cdots p_r\) is

The checker enumerates only increasing normal prime tuples, but its bounds are exhaustive.

For a prefix with

and \(t=r-j\) primes still to choose, the next prime \(p\) must satisfy

Because all \(t\) remaining primes are at least \(p\), it must also satisfy

This bound is used only while at least three primes remain; their strict ordering makes the inequality strict. After division by \(p^t\), the left-minus-right expression is strictly increasing, so exact integer binary search gives a finite upper bound for \(p\). No floating point arithmetic is used.

At a prefix of length \(r-2\), put

The final two primes \(p<q\) obey

or equivalently

The program completely factors the right side, enumerates every positive divisor pair, reconstructs \(p,q\), and checks primality, ordering, normality, and (4.3).

Primality testing uses the first twelve prime Miller–Rabin bases. Sorenson and Webster, Strong Pseudoprimes to Twelve Prime Bases, arXiv:1509.00864, determine the first composite passing all twelve tests as

The checker asserts every primality input is below this threshold; the largest actual input was

Pollard–Brent supplies factors, after which their primality and reconstructed product are checked. Thus the enumeration is deterministic in the stated range, not a probable-prime search.

4.3 Results

[d] The exact output was:

| \(\omega(n)\) | solutions of \(2\phi(n)=n+1\) | terminal prefixes | |---:|:---|---:| | 0 | \(1\) | 1 | | 1 | \(3\) | 1 | | 2 | \(15\) | 1 | | 3 | \(255\) | 1 | | 4 | \(65535\) | 1 | | 5 | \(83623935,\ 4294967295\) | 3 | | 6 | \(6992962672132095\) | 44 | | 7 | none | 6,826 |

Combining this with the isolated \(n=2\) and the elementary quotient reduction gives the claimed complete set for \(\omega(n)\leq7\). All nine displayed integers are separately refactored and their totients recomputed in the checker; no printed list is trusted.

This is a finite/computational theorem, not evidence that the list is globally complete.

5. Exhaustive finite table for nearby shifts

Define

[d] For \(X=10^7\), the exact counts are:

| \(a\) | \(R_a(10^7)\) | |---:|---:| | -20 | 14 | | -19 | 8 | | -18 | 45,750 | | -17 | 9 | | -16 | 50,995 | | -15 | 11 | | -14 | 11 | | -13 | 8 | | -12 | 66,429 | | -11 | 6 | | -10 | 10 | | -9 | 10 | | -8 | 96,476 | | -7 | 6 | | -6 | 125,802 | | -5 | 7 | | -4 | 183,076 | | -3 | 6 | | -2 | 348,515 | | -1 | 664,580 | | 0 | 176 | | 1 | 6 | | 2 | 11 | | 3 | 11 | | 4 | 14 | | 5 | 7 | | 6 | 12 | | 7 | 7 | | 8 | 16 | | 9 | 15 | | 10 | 20 | | 11 | 6 | | 12 | 15 | | 13 | 7 | | 14 | 14 | | 15 | 19 | | 16 | 20 | | 17 | 8 | | 18 | 18 | | 19 | 7 | | 20 | 23 |

The large growing rows at \(a=-1,-2,-4,-6,-8,-12,-16,-18\) are explained by the regular families in (3.6). Small counts in the other rows are not a finiteness claim.

Verification details:

• Algorithm A is the Euler-product sieve: initialize \(\phi(n)=n\) and apply

\(\phi(n)\leftarrow\phi(n)-\phi(n)/p\) at every prime divisor.

• Algorithm B is Euler's linear sieve using least prime factors and its

prime-power recurrence.

• Both independently scan all \(n\), and their count vectors, first/last

hits, total hit count, and ordered SHA-256 stream must agree.

• The full ordered stream of records \((a,n,\phi(n))\) had 1,582,161 records

and SHA-256 d74aaca99ac7cfe09e5817158fcab49bcc987d0acf4e6df008cde7558ea82296.

• Every hit was then factored with the independent least-prime-factor array

and checked against (3.1)–(3.3).

• The finite classification (3.4) was checked for every \(n\leq10^7\), as

were 1,824,955 regular products \(mp\) in the box.

The exact first eight and last three hits for every row are printed by the standalone program.

6. Reproduction

Run:

python runs/erdos828_wavew017_verify.py

The program is standard-library-only. Its SHA-256 is 5aded2d4815ebd8bcba1b81b9ddc06f22ae61437203ccf76cceeb4ff32486a66. The final run used Python 3.12.3 on one Intel Xeon Platinum 8259CL core and took 44.13 wall-clock seconds with a maximum resident set of 124,080 KiB. The two \(10^7\) sieves and scans took about 18.4 seconds, structural checks about 12 seconds, and the exact \(\omega\leq7\) enumeration about 13.8 seconds. It ended with ALL CHECKS PASSED.

For source audit reproducibility, the primary PDFs read in this investigation had these SHA-256 hashes:

3d9c5252272fe3d5b8289ac220997f8019708fda393e11dde91a50b8af7a8ce6  Erdős–Dudley 1983
16a2eb440ddc9d156453411239ba78f400ff12d4bfcb86c78de4e1c06ed7edd3  Pomerance 1975
e5f32a8857f534e80841ca389d29b7fc70a1109ae539285b182e7390a8725ea9  Pomerance 1977
0b533b3e5b32c76b7c0ace52f1df41e1c66ab9615c1ccc015faf4c9da12537c7  Banks–Güloğlu–Nevans 2008
2df8d6977d2a025b09cef992fd38756ff379097ce28dbe938cd6c503a88748fb  Lehmer 1932
6b44419c3dcc2f469123fb5cd43120cf941175de223a672a6eaad96eec88b77e  Wong 1997

7. Exact remaining wall

[a+b] The problem is now cleanly divided:

• \(a=0\) is completely handled by (3.4).
• The regular negative shifts (3.6) have explicit infinite families.
• For every other shift, every infinite family must have

\(\omega(n)\to\infty\), while (2.1) makes each fixed-\(\omega\) slice finite and (2.3) makes the whole set very sparse.

For \(a>0\), write \(n=\prod p^{e_p}\). Apart from the bounded exponents at primes dividing \(a\), the unresolved core is to construct unbounded prime supports satisfying the exact near-integer identity

For \(a=1\), the support is squarefree and normal, and any new example has at least eight primes. The missing lemma is not merely “find many primes with \(p-1\) smooth”. One must make the full product \(\prod(p-1)=\phi(n)\) divide the single number \(n+a\), with the exact numerator \(a\) in (7.1). Carmichael-number machinery controls local conditions \(p-1\mid n-1\), hence an lcm; it does not control the much larger product \(\prod(p-1)\). This product-versus-lcm gap is the precise point at which the standard construction machinery stalls.

[c] Cost of the next finite computation. Extending only the \(a=1\), \(2\phi(n)=n+1\) search from seven to eight factors would still not settle infinitude. Wong estimates more than 216 million six-prime prefixes. At the measured seven-factor throughput, even the unrealistic assumption that the larger discriminants cost no more gives a floor of about 120 single-core hours. The eight-factor discriminants are substantially larger and require harder complete factorizations, so a responsible implementation would need a parallel C/ECM pilot before quoting a tighter estimate; a full run is outside the permitted few CPU-minutes here. More importantly, checking any finite number of \(\omega\)-rows cannot supply the uniform unbounded-\(\omega\) construction required by the conjecture.

PARTIAL: classified all possible bounded-\(\omega\) infinite families, reproduced the exact \(a=1\) list through seven prime factors, and isolated the unresolved unbounded-prime-support product-divisibility lemma.