Erdős once conjectured that $\binom{n}{k}$ must always have a divisor in $(n-k,n]$, but this was disproved by Schinzel and Erdős [Sc58]. A counterexample is given by $n=99215$ and $k=15$. Schinzel conjectured (see problem B34 of [Gu04]) that, for all sufficiently large $k$ which are not prime powers, there exists an $n$ such that $\binom{n}{k}$ is not divisible by any integer in $(n-k,n]$.

It is easy to see that $\binom{n}{k}$ always has a divisor in $[n/k,n]$.

Faulkner [Fa66] proved that, if $p$ is the least prime $>2k$ and $n\geq p$, then $\binom{n}{k}$ has a prime divisor $\geq p$ (except $\binom{9}{2}$ and $\binom{10}{3}$).

This is discussed in problems B33 and B34 of Guy's collection [Gu04], who says that Erdős conjectured this is true for any $c<1$ (if $n$ is sufficiently large).

View the LaTeX source

This page was last edited 18 October 2025.