Erdős Problem #1094

Erdős Problem 1094 --- 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/1094.tex.

REUSED SOURCE 1

FORMAL RESTATEMENT

Let $n,k\in\mathbb{Z}$ with $1\le k\le n-1$ and $n\ge 2k\ge 2$. Let \[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\in\mathbb{Z}_{>1}. \] Define $\operatorname{lpf}(m)$ for an integer $m>1$ to be the least (smallest) prime divisor of $m$.

Claim/conjecture (as stated). There exists a finite set $E\subset\{(n,k)\in\mathbb{Z}^2: n\ge 2k\ge 2\}$ such that for all $(n,k)\notin E$, \[ \operatorname{lpf}\!\left(\binom{n}{k}\right)\le \max\left(\frac{n}{k},\,k\right). \] Equivalently: for all but finitely many $(n,k)$ with $n\ge 2k\ge 2$, there exists a prime $p\le \max(n/k,k)$ such that $p\mid\binom{n}{k}$.

QUICK LITERATURE/CONTEXT CHECK

The problem text attributes the conjecture (with a specific finite exceptional list of $14$ binomial coefficients) to Erdős--Lacampagne--Selfridge, and mentions stronger variants with $\max(n/k,\sqrt{k})$ or $\max(n/k,O(\log k))$ (again with finitely many exceptions). Per the integrity rule for this task, I do not assert any literature statements beyond what is explicitly written in the problem file.

ATTACK PLAN

• Proof track (partial). Prove the inequality in infinite families (e.g. $k\mid n$, or when $n$ has a "medium" prime factor), and prove the conjecture completely for very small $k$.
• Disproof track. Search systematically for violations $(n,k)$ with $n\ge 2k$ where every prime $\le\max(n/k,k)$ fails to divide $\binom{n}{k}$; attempt to find patterns that could generate infinitely many violations.
• Reality check. Exhaustive computation for moderate ranges of $(n,k)$ to see whether violations match the $14$ listed exceptions.

WORK

Lemma 1094.1 (a divisibility identity when $k\mid n$). If $n=mk$ for some integer $m\ge 2$, then \[ \frac{n}{k}=m\ \text{divides}\ \binom{n}{k}. \] In particular, \[ \operatorname{lpf}\!\left(\binom{n}{k}\right)\le \operatorname{lpf}(m)\le m=\frac{n}{k}\le \max\left(\frac{n}{k},k\right). \]

Proof. Use the standard identity \[ \binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}. \] If $n=mk$ then $n/k=m\in\mathbb{Z}$, so the right-hand side is $m\binom{n-1}{k-1}$. Since $\binom{n-1}{k-1}\in\mathbb{Z}$, this shows $m\mid\binom{n}{k}$. Any prime divisor of $m$ is a prime divisor of $\binom{n}{k}$, hence $\operatorname{lpf}(\binom{n}{k})\le \operatorname{lpf}(m)\le m=n/k$. $\square$

Lemma 1094.2 (a prime factor of $n$ larger than $k$ survives cancellation). Let $p$ be a prime with $p\mid n$ and $p>k$. Then $p\mid\binom{n}{k}$. Consequently, \[ \operatorname{lpf}\!\left(\binom{n}{k}\right)\le p. \]

Proof. Write \[ \binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}. \] The numerator is divisible by $p$ because $p\mid n$. The denominator $k!$ is not divisible by $p$ because $p>k$ and hence none of $1,2,\dots,k$ is a multiple of $p$. Therefore the reduced fraction still has a factor $p$; since the binomial coefficient is an integer, this means $p\mid\binom{n}{k}$. $\square$

Corollary 1094.3 (a sufficient condition for the desired inequality). If $n$ has a prime divisor $p$ with \[ k<p\le \frac{n}{k}, \] then $\operatorname{lpf}(\binom{n}{k})\le p\le n/k\le \max(n/k,k)$.

Proof. Lemma 1094.2 gives $p\mid\binom{n}{k}$, so the least prime factor is at most $p$. The displayed inequalities then give the numeric bound. $\square$

Lemma 1094.4 (complete verification for $k=2$). For every integer $n\ge 4$, \[ \operatorname{lpf}\!\left(\binom{n}{2}\right)\le \frac{n}{2} = \max\left(\frac{n}{2},2\right). \]

Proof. We have \[ \binom{n}{2}=\frac{n(n-1)}{2}. \] If $n$ is even, write $n=2m$ with $m\ge 2$. Then $\binom{n}{2}=m(n-1)$ is divisible by $m$, so $\operatorname{lpf}(\binom{n}{2})\le \operatorname{lpf}(m)\le m=n/2$.

If $n$ is odd, write $n=2m+1$ with $m\ge 2$ (since $n\ge 5$ in this case). Then \[ \binom{n}{2}=n\cdot\frac{n-1}{2}=(2m+1)\cdot m. \] Since $m\ge 2$, $\operatorname{lpf}(\binom{n}{2})\le \operatorname{lpf}(m)\le m=(n-1)/2 < n/2$. This proves the claim for all $n\ge 4$. $\square$

FAST REALITY CHECK (exact computation for $n\le 400$).

I exhaustively checked all pairs $(n,k)$ with $2\le n\le 400$ and $1\le k\le \lfloor n/2\rfloor$. For each pair I computed $\operatorname{lpf}(\binom{n}{k})$ by checking divisibility by primes $p\le n$ using Legendre's formula for $v_p(n!)$.

Result. Exactly $14$ pairs violate $\operatorname{lpf}(\binom{n}{k})\le\max(n/k,k)$, and they are precisely the $14$ binomial coefficients listed in the problem statement. The violating pairs and their least prime factors are: \[ \begin{array}{r|r|r|r} (n,k) & \max(n/k,k) & \operatorname{lpf}(\binom{n}{k}) & \binom{n}{k} \\\hline (7,3) & 3 & 5 & 35\\ (13,4) & 4 & 5 & 715\\ (14,4) & 4 & 7 & 1001\\ (23,5) & 5 & 7 & 33649\\ (44,8) & 8 & 11 & 177232627\\ (46,10) & 10 & 11 & 4076350421\\ (47,10) & 10 & 11 & 5178066751\\ (47,11) & 11 & 13 & 17417133617\\ (62,6) & 62/6\approx 10.33 & 19 & 61474519\\ (74,10) & 10 & 11 & 718406958841\\ (94,10) & 10 & 11 & 9041256841903\\ (95,10) & 10 & 11 & 10104934117421\\ (241,16) & 16 & 17 & 3720625555021727122496771\\ (284,28) & 28 & 29 & 408428827130333363893145556340656087569 \end{array} \]

VERIFICATION

• Lemma 1094.1 uses only the exact identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ and the integrality of binomial coefficients; no hidden assumptions.
• Lemma 1094.2 checks cancellation carefully: the only way $p$ could cancel is if $p\mid k!$, which is impossible when $p>k$.
• For Lemma 1094.4, the parity split covers all $n\ge 4$; the smallest odd case is $n=5$ and is included.
• Computational check: for each $(n,k)$ the algorithm only needs primes $p\le n$, since every prime divisor of $\binom{n}{k}$ is $\le n$ (because $\binom{n}{k}\mid n!$). This makes the least-prime-factor search exhaustive.

UNRESOLVED

(i) Strongest proved partial result here. The conjectured inequality holds for all $(n,k)$ with $k\mid n$ (Lemma 1094.1), and more generally whenever $n$ has a prime factor $p$ with $k<p\le n/k$ (Corollary 1094.3). It also holds for all $n\ge 4$ when $k=2$ (Lemma 1094.4). Exhaustive computation verified that for $2\le n\le 400$ the only violations are exactly the $14$ listed exceptions.

(ii) First gap (crisp). Prove that outside a finite exceptional set of pairs $(n,k)$ with $n\ge 2k\ge 2$, there exists some prime $p\le \max(n/k,k)$ dividing $\binom{n}{k}$. Equivalently, rule out infinitely many pairs for which all primes $p\le \max(n/k,k)$ fail to divide $\binom{n}{k}$.

(iii) Top 3 next moves.

1. Use $p$-adic valuations (Legendre/Kummer/Lucas-type digit conditions) to translate "$p\nmid\binom{n}{k}$" into constraints on the base-$p$ digits of $n,k$, then try to show these constraints cannot hold simultaneously for all primes $p\le \max(n/k,k)$ except in finitely many cases.
2. Push computation further (e.g. $n$ up to several thousand) to look for any new violations beyond the known list and to search for structural patterns in near-violations.
3. Attack the regime $k\approx \sqrt{n}$, where the bound $\max(n/k,k)$ is smallest (about $\sqrt{n}$), and try to show that $\binom{n}{k}$ must have a prime factor $\le \sqrt{n}$ except in controlled exceptional configurations.

(iv) Minimal counterexample structure. An infinite counterexample family would require infinitely many pairs $(n,k)$ with $n\ge 2k$ such that $\binom{n}{k}$ is "$B$-rough" with $B:=\max(n/k,k)$, i.e. every prime $p\le B$ has $v_p\!\left(\binom{n}{k}\right)=0$. Since $B$ is minimized near $k\approx \sqrt{n}$, any infinite counterexample would most plausibly occur with $k$ comparable to $\sqrt{n}$ (rather than $k$ fixed or $k\mid n$, where Lemma 1094.1 gives the bound).

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.

FORMAL RESTATEMENT

Let $n,k\in\mathbb{Z}$ with $1\le k\le n-1$ and $n\ge 2k\ge 2$. Let \[ \binom{n}{k}=\frac{n!}{k!(n-k)!}\in\mathbb{Z}_{>1}. \] Define $\operatorname{lpf}(m)$ for an integer $m>1$ to be the least (smallest) prime divisor of $m$.

Claim/conjecture (as stated). There exists a finite set $E\subset\{(n,k)\in\mathbb{Z}^2: n\ge 2k\ge 2\}$ such that for all $(n,k)\notin E$, \[ \operatorname{lpf}\!\left(\binom{n}{k}\right)\le \max\left(\frac{n}{k},\,k\right). \] Equivalently: for all but finitely many $(n,k)$ with $n\ge 2k\ge 2$, there exists a prime $p\le \max(n/k,k)$ such that $p\mid\binom{n}{k}$.

QUICK LITERATURE/CONTEXT CHECK

The problem text attributes the conjecture (with a specific finite exceptional list of $14$ binomial coefficients) to Erdős--Lacampagne--Selfridge, and mentions stronger variants with $\max(n/k,\sqrt{k})$ or $\max(n/k,O(\log k))$ (again with finitely many exceptions). Per the integrity rule for this task, I do not assert any literature statements beyond what is explicitly written in the problem file.

ATTACK PLAN

• Proof track (partial). Prove the inequality in infinite families (e.g. $k\mid n$, or when $n$ has a "medium" prime factor), and prove the conjecture completely for very small $k$.
• Disproof track. Search systematically for violations $(n,k)$ with $n\ge 2k$ where every prime $\le\max(n/k,k)$ fails to divide $\binom{n}{k}$; attempt to find patterns that could generate infinitely many violations.
• Reality check. Exhaustive computation for moderate ranges of $(n,k)$ to see whether violations match the $14$ listed exceptions.

WORK

Lemma 1094.1 (a divisibility identity when $k\mid n$). If $n=mk$ for some integer $m\ge 2$, then \[ \frac{n}{k}=m\ \text{divides}\ \binom{n}{k}. \] In particular, \[ \operatorname{lpf}\!\left(\binom{n}{k}\right)\le \operatorname{lpf}(m)\le m=\frac{n}{k}\le \max\left(\frac{n}{k},k\right). \]

Proof. Use the standard identity \[ \binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}. \] If $n=mk$ then $n/k=m\in\mathbb{Z}$, so the right-hand side is $m\binom{n-1}{k-1}$. Since $\binom{n-1}{k-1}\in\mathbb{Z}$, this shows $m\mid\binom{n}{k}$. Any prime divisor of $m$ is a prime divisor of $\binom{n}{k}$, hence $\operatorname{lpf}(\binom{n}{k})\le \operatorname{lpf}(m)\le m=n/k$. $\square$

Lemma 1094.2 (a prime factor of $n$ larger than $k$ survives cancellation). Let $p$ be a prime with $p\mid n$ and $p>k$. Then $p\mid\binom{n}{k}$. Consequently, \[ \operatorname{lpf}\!\left(\binom{n}{k}\right)\le p. \]

Proof. Write \[ \binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}. \] The numerator is divisible by $p$ because $p\mid n$. The denominator $k!$ is not divisible by $p$ because $p>k$ and hence none of $1,2,\dots,k$ is a multiple of $p$. Therefore the reduced fraction still has a factor $p$; since the binomial coefficient is an integer, this means $p\mid\binom{n}{k}$. $\square$

Corollary 1094.3 (a sufficient condition for the desired inequality). If $n$ has a prime divisor $p$ with \[ k<p\le \frac{n}{k}, \] then $\operatorname{lpf}(\binom{n}{k})\le p\le n/k\le \max(n/k,k)$.

Proof. Lemma 1094.2 gives $p\mid\binom{n}{k}$, so the least prime factor is at most $p$. The displayed inequalities then give the numeric bound. $\square$

Lemma 1094.4 (complete verification for $k=2$). For every integer $n\ge 4$, \[ \operatorname{lpf}\!\left(\binom{n}{2}\right)\le \frac{n}{2} = \max\left(\frac{n}{2},2\right). \]

Proof. We have \[ \binom{n}{2}=\frac{n(n-1)}{2}. \] If $n$ is even, write $n=2m$ with $m\ge 2$. Then $\binom{n}{2}=m(n-1)$ is divisible by $m$, so $\operatorname{lpf}(\binom{n}{2})\le \operatorname{lpf}(m)\le m=n/2$.

If $n$ is odd, write $n=2m+1$ with $m\ge 2$ (since $n\ge 5$ in this case). Then \[ \binom{n}{2}=n\cdot\frac{n-1}{2}=(2m+1)\cdot m. \] Since $m\ge 2$, $\operatorname{lpf}(\binom{n}{2})\le \operatorname{lpf}(m)\le m=(n-1)/2 < n/2$. This proves the claim for all $n\ge 4$. $\square$

FAST REALITY CHECK (exact computation for $n\le 400$).

I exhaustively checked all pairs $(n,k)$ with $2\le n\le 400$ and $1\le k\le \lfloor n/2\rfloor$. For each pair I computed $\operatorname{lpf}(\binom{n}{k})$ by checking divisibility by primes $p\le n$ using Legendre's formula for $v_p(n!)$.

Result. Exactly $14$ pairs violate $\operatorname{lpf}(\binom{n}{k})\le\max(n/k,k)$, and they are precisely the $14$ binomial coefficients listed in the problem statement. The violating pairs and their least prime factors are: \[ \begin{array}{r|r|r|r} (n,k) & \max(n/k,k) & \operatorname{lpf}(\binom{n}{k}) & \binom{n}{k} \\\hline (7,3) & 3 & 5 & 35\\ (13,4) & 4 & 5 & 715\\ (14,4) & 4 & 7 & 1001\\ (23,5) & 5 & 7 & 33649\\ (44,8) & 8 & 11 & 177232627\\ (46,10) & 10 & 11 & 4076350421\\ (47,10) & 10 & 11 & 5178066751\\ (47,11) & 11 & 13 & 17417133617\\ (62,6) & 62/6\approx 10.33 & 19 & 61474519\\ (74,10) & 10 & 11 & 718406958841\\ (94,10) & 10 & 11 & 9041256841903\\ (95,10) & 10 & 11 & 10104934117421\\ (241,16) & 16 & 17 & 3720625555021727122496771\\ (284,28) & 28 & 29 & 408428827130333363893145556340656087569 \end{array} \]

VERIFICATION

• Lemma 1094.1 uses only the exact identity $\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$ and the integrality of binomial coefficients; no hidden assumptions.
• Lemma 1094.2 checks cancellation carefully: the only way $p$ could cancel is if $p\mid k!$, which is impossible when $p>k$.
• For Lemma 1094.4, the parity split covers all $n\ge 4$; the smallest odd case is $n=5$ and is included.
• Computational check: for each $(n,k)$ the algorithm only needs primes $p\le n$, since every prime divisor of $\binom{n}{k}$ is $\le n$ (because $\binom{n}{k}\mid n!$). This makes the least-prime-factor search exhaustive.

UNRESOLVED

(i) Strongest proved partial result here. The conjectured inequality holds for all $(n,k)$ with $k\mid n$ (Lemma 1094.1), and more generally whenever $n$ has a prime factor $p$ with $k<p\le n/k$ (Corollary 1094.3). It also holds for all $n\ge 4$ when $k=2$ (Lemma 1094.4). Exhaustive computation verified that for $2\le n\le 400$ the only violations are exactly the $14$ listed exceptions.

(ii) First gap (crisp). Prove that outside a finite exceptional set of pairs $(n,k)$ with $n\ge 2k\ge 2$, there exists some prime $p\le \max(n/k,k)$ dividing $\binom{n}{k}$. Equivalently, rule out infinitely many pairs for which all primes $p\le \max(n/k,k)$ fail to divide $\binom{n}{k}$.

(iii) Top 3 next moves.

1. Use $p$-adic valuations (Legendre/Kummer/Lucas-type digit conditions) to translate "$p\nmid\binom{n}{k}$" into constraints on the base-$p$ digits of $n,k$, then try to show these constraints cannot hold simultaneously for all primes $p\le \max(n/k,k)$ except in finitely many cases.
2. Push computation further (e.g. $n$ up to several thousand) to look for any new violations beyond the known list and to search for structural patterns in near-violations.
3. Attack the regime $k\approx \sqrt{n}$, where the bound $\max(n/k,k)$ is smallest (about $\sqrt{n}$), and try to show that $\binom{n}{k}$ must have a prime factor $\le \sqrt{n}$ except in controlled exceptional configurations.

(iv) Minimal counterexample structure. An infinite counterexample family would require infinitely many pairs $(n,k)$ with $n\ge 2k$ such that $\binom{n}{k}$ is "$B$-rough" with $B:=\max(n/k,k)$, i.e. every prime $p\le B$ has $v_p\!\left(\binom{n}{k}\right)=0$. Since $B$ is minimized near $k\approx \sqrt{n}$, any infinite counterexample would most plausibly occur with $k$ comparable to $\sqrt{n}$ (rather than $k$ fixed or $k\mid n$, where Lemma 1094.1 gives the bound).