A question of Erdős, Graham, Ruzsa, and Straus [EGRS75].
Erdős [Er68c] proved that if a!b!∣n!$a!b!\mid n!$ then a+b≤n+O(logn)$a+b\le n+O(\log n)$.

This problem can be rephrased (taking k=a+b−n$k=a+b-n$ and N=a+b$N=a+b$) as asking for (Nk)∣(Na)$(\genfrac{}{}{0ex}{}{N}{k})\mid (\genfrac{}{}{0ex}{}{N}{a})$.

This problem is ambiguous, and there are a number of trivial solutions to the problem as written. for example, the AlphaProof team has noted that there are solutions with very large a$a$ and b$b$ - for example, a=n+w+1$a=n+w+1$ and b=(n+w+1)!n!−1$b=\frac{(n+w+1)!}{n!}-1$ for some w≥max(Clogn,ϵn)$w\ge max(C\log n,ϵn)$.

From context presumably the condition a,b≤n$a,b\le n$ was intended, but here we also have trivial solutions: for example one can take a=b=n$a=b=n$, or b=n−1$b=n-1$ and a$a$ any large divisor of n$n$. No doubt the authors had in mind some condition such as a,b≤(1−ϵ)n$a,b\le (1-ϵ)n$.

Barreto and ChatGPT-5.2 have proved that, for any 0<C1<C2$0<C_1<C_2$, there are infinitely many a,b,n$a,b,n$ with b=n/2$b=n/2$, a=n/2+O(logn)$a=n/2+O(\log n)$, andsuch thatThis appears to answer the question in the spirit it was intended.

See also [729].

View the LaTeX source

This page was last edited 06 January 2026. View history