Erdős Problem #1073

Erdős Problem 1073 --- collection record

PROVENANCE AND STATUS

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/1073.tex.

REUSED SOURCE 1

1) FORMAL RESTATEMENT Let A(x) be the number of composite integers u < x such that u divides $n!+1$ for at least one integer n >= 1. The question asks whether A(x) <= x^{o$1$} as x -> infinity (equivalently: for every eps>0 and all sufficiently large x, A(x) <= x^eps).

2) QUICK LITERATURE/CONTEXT CHECK The problem statement lists the first few such composite u: 25, 121, 169, 437, 551, 625, ... No other external results are assumed here.

3) ATTACK PLAN A direct counting approach starts by proving strong necessary conditions on any u that divides n!+1, especially constraints on its prime factors. This yields an algorithmic reduction for computing A(x) exactly for small x.

4) WORK Lemma 1073.1 (Prime factors must exceed the witnessing factorial index). If u divides $n!+1$, then gcd(u, n!) = 1. In particular, every prime divisor q of u satisfies q > n. If in addition u is composite, and q is the smallest prime divisor of u, then n < q <= sqrt(u), hence n <= floor(sqrt(u)) - 1. Proof. If a prime q divides both u and n!, then q divides n! and also divides $n!+1$ (because q|u and u|$n!+1$), hence q divides 1, impossible. Thus gcd(u,n!)=1 and no prime factor of u can be <= n. If u is composite, let q be its smallest prime factor. Then q^2 <= u, so q <= sqrt(u). Since q>n, we get n < sqrt(u), i.e. n <= floor(sqrt(u)) - 1. QED.

Lemma 1073.2 (Finite search window for u<x). Fix x >= 4. For any composite u < x, the condition "there exists n with u | $n!+1$" is equivalent to there exists n with 1 <= n <= floor(sqrt(u)) such that n! ≡ -1 (mod u). In particular, to compute A(x) exactly for small x, it suffices to test each composite u<x against n=1,2,...,floor(sqrt(u)). Proof. The forward direction follows from Lemma 1073.1: if u is composite and u | $n!+1$, then necessarily n <= floor(sqrt(u)) - 1, so certainly n <= floor(sqrt(u)). The reverse direction is tautological: if such an n exists, then u divides n!+1 by definition. QED.

5) VERIFICATION (small cases) Using Lemma 1073.2, I computed A(x) exactly for several small x by testing each composite u<x and iterating factorial mod u up to floor(sqrt(u)). The results: - A$200$ = 3, and the composites are 25 (witness n=4), 121 $n=5$, 169 $n=6$. - A$500$ = 4, adding 437 $n=7$. - A$1000$ = 7, adding 551 $n=8$, 625 $n=4$, 841 $n=7$. - A$2000$ = 15. The composites <2000 with a witness (u, minimal n) are: $25,4$, $121,5$, $169,6$, $437,7$, $551,8$, $625,4$, $841,7$, $961,7$, $1125,4$, $1177,13$, $1375,8$, $1439,19$, $1715,4$, $1849,8$, $1919,11$. - A$5000$ = 22.

6) FINAL UNRESOLVED (i) Strongest proved partial result here: if a composite u divides n!+1 then every prime factor of u exceeds n, hence necessarily n < sqrt(u) (Lemma 1073.1), and therefore for u<x it suffices to check n up to floor(sqrt(u)) (Lemma 1073.2). (ii) First gap (crisp): Prove a nontrivial asymptotic upper bound on A(x), ideally A(x) <= x^{o$1$}. Even A(x) <= x^c for every fixed c>0 is open from the standpoint of this writeup. (iii) Top 3 next moves (concrete): 1. For each n, study the set of composite divisors u of n!+1 whose smallest prime factor exceeds n, and bound how many such u can be < x as n varies. 2. Try to show that for most u, the congruence n! ≡ -1 (mod u) has no solution with n <= sqrt(u), perhaps via multiplicative order obstructions for prime factors. 3. Push the exact computation of A(x) to larger x using Lemma 1073.2 to look for growth trends (e.g. compare A(x) with log x, (log x)^2, x^0.1, etc.). (iv) Minimal counterexample structure: To refute A(x) <= x^{o$1$}, one would need a fixed eps>0 and infinitely many x for which there are at least x^eps distinct composite u<x admitting some witness n <= sqrt(u) with n! ≡ -1 (mod u).

COMPLETION ESTIMATE

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

1) FORMAL RESTATEMENT Let A(x) be the number of composite integers u < x such that u divides $n!+1$ for at least one integer n >= 1. The question asks whether A(x) <= x^{o$1$} as x -> infinity (equivalently: for every eps>0 and all sufficiently large x, A(x) <= x^eps).

2) QUICK LITERATURE/CONTEXT CHECK The problem statement lists the first few such composite u: 25, 121, 169, 437, 551, 625, ... No other external results are assumed here.

3) ATTACK PLAN A direct counting approach starts by proving strong necessary conditions on any u that divides n!+1, especially constraints on its prime factors. This yields an algorithmic reduction for computing A(x) exactly for small x.

4) WORK Lemma 1073.1 (Prime factors must exceed the witnessing factorial index). If u divides $n!+1$, then gcd(u, n!) = 1. In particular, every prime divisor q of u satisfies q > n. If in addition u is composite, and q is the smallest prime divisor of u, then n < q <= sqrt(u), hence n <= floor(sqrt(u)) - 1. Proof. If a prime q divides both u and n!, then q divides n! and also divides $n!+1$ (because q|u and u|$n!+1$), hence q divides 1, impossible. Thus gcd(u,n!)=1 and no prime factor of u can be <= n. If u is composite, let q be its smallest prime factor. Then q^2 <= u, so q <= sqrt(u). Since q>n, we get n < sqrt(u), i.e. n <= floor(sqrt(u)) - 1. QED.

Lemma 1073.2 (Finite search window for u<x). Fix x >= 4. For any composite u < x, the condition "there exists n with u | $n!+1$" is equivalent to there exists n with 1 <= n <= floor(sqrt(u)) such that n! ≡ -1 (mod u). In particular, to compute A(x) exactly for small x, it suffices to test each composite u<x against n=1,2,...,floor(sqrt(u)). Proof. The forward direction follows from Lemma 1073.1: if u is composite and u | $n!+1$, then necessarily n <= floor(sqrt(u)) - 1, so certainly n <= floor(sqrt(u)). The reverse direction is tautological: if such an n exists, then u divides n!+1 by definition. QED.

5) VERIFICATION (small cases) Using Lemma 1073.2, I computed A(x) exactly for several small x by testing each composite u<x and iterating factorial mod u up to floor(sqrt(u)). The results: - A$200$ = 3, and the composites are 25 (witness n=4), 121 $n=5$, 169 $n=6$. - A$500$ = 4, adding 437 $n=7$. - A$1000$ = 7, adding 551 $n=8$, 625 $n=4$, 841 $n=7$. - A$2000$ = 15. The composites <2000 with a witness (u, minimal n) are: $25,4$, $121,5$, $169,6$, $437,7$, $551,8$, $625,4$, $841,7$, $961,7$, $1125,4$, $1177,13$, $1375,8$, $1439,19$, $1715,4$, $1849,8$, $1919,11$. - A$5000$ = 22.

6) FINAL UNRESOLVED (i) Strongest proved partial result here: if a composite u divides n!+1 then every prime factor of u exceeds n, hence necessarily n < sqrt(u) (Lemma 1073.1), and therefore for u<x it suffices to check n up to floor(sqrt(u)) (Lemma 1073.2). (ii) First gap (crisp): Prove a nontrivial asymptotic upper bound on A(x), ideally A(x) <= x^{o$1$}. Even A(x) <= x^c for every fixed c>0 is open from the standpoint of this writeup. (iii) Top 3 next moves (concrete): 1. For each n, study the set of composite divisors u of n!+1 whose smallest prime factor exceeds n, and bound how many such u can be < x as n varies. 2. Try to show that for most u, the congruence n! ≡ -1 (mod u) has no solution with n <= sqrt(u), perhaps via multiplicative order obstructions for prime factors. 3. Push the exact computation of A(x) to larger x using Lemma 1073.2 to look for growth trends (e.g. compare A(x) with log x, (log x)^2, x^0.1, etc.). (iv) Minimal counterexample structure: To refute A(x) <= x^{o$1$}, one would need a fixed eps>0 and infinitely many x for which there are at least x^eps distinct composite u<x admitting some witness n <= sqrt(u) with n! ≡ -1 (mod u).