Problem Statement
Let\[f(n)=\min_{1<k\leq n/2}\textrm{gcd}\left(n,\binom{n}{k}\right).\]
- Characterise those composite $n$ such that $f(n)=n/P(n)$, where $P(n)$ is the largest prime dividing $n$.
- Are there infinitely many composite $n$ such that $f(n)>n^{1/2}$?
- Is it true that, for every composite $n$,\[f(n) \ll_A \frac{n}{(\log n)^A}\]for every $A>0$?
Categories:
Number Theory Binomial Coefficients
Progress
A problem of Erdős and Szekeres. It is easy to see that $f(n)\leq n/P(n)$ for composite $n$, since if $j=p^k$ where $p^k\mid n$ and $p^{k+1}\nmid n$ then $\textrm{gcd}\left(n,\binom{n}{j}\right)=n/p^k$. This implies\[f(n) \leq (1+o(1))\frac{n}{\log n}.\]It is known that $f(n)=n/P(n)$ when $n$ is the product of two primes. Another example is $n=30$.For the second problem, it is easy to see that for any $n$ we have $f(n)\geq p(n)$, where $p(n)$ is the smallest prime dividing $n$, and hence there are infinitely many $n$ (those $=p^2)$ such that $f(n)\geq n^{1/2}$.
Source: erdosproblems.com/700 | Last verified: January 16, 2026