Erdős Problem #1094

declared status 'open'. Formalized: yes. For all $n\geq 2k$ the least prime factor of $\binom{n}{k}$ is $\leq \max(n/k,k)$, with only finitely many exceptions. Current best: Selfridge [Se77] further conjectured that this always happens if $n\geq k^2-1$, except $\binom{62}{6}$. More precisely, in [ELS88] they conjecture that if $n\geq 2k$ then the least prime factor of $\binom{n}{k}$ is $\leq \max(n/k,k)$ with the following $14$ exceptions:$$\binom{7}{3},\binom{13}{4},\binom{23}{5},\binom{14}{4},\binom{44}{8},\binom{46}{10},\binom{47}{10},$$$$\binom{47}{11},\binom{62}{6},\binom{74}{10},\binom{94}{10},\binom{95}{10},\binom{241}{16},\binom{284}{28}.$$They also suggest the stronger conjecture that, with a finite number of exceptions, the least prime factor is $\leq \max(n/k,\sqrt{k})$, or perhaps even $\leq \max(n/k,O(\log k))$. Discussed in problem B31 and B33 of Guy's collection [Gu04] - there Guy credits Selfridge with the conjecture that if $n> 17.125k$ then $\binom{n}{k}$ has a prime factor $p\leq n/k$. Prize: no. Tags: binomial coefficients, number theory.

Notation is rendered from the stored source. The pinned checkout remains the exact record.