Reused writeup on Math-5829 (gpt pro 5.2)

Erdős Problem 699 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/699

Saved collaborative-database status: falsifiable. 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/699.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/699.tex.

Erdős Problem #699

FORMAL RESTATEMENT

For each integer $n\ge 2$, consider all pairs of integers $(i,j)$ with $1\le i<j\le \lfloor n/2\rfloor$. The question asks whether for every such pair there exists a prime $p\ge i$ such that \[p\mid \gcd\left(\binom{n}{i},\binom{n}{j}\right). \] Equivalently: for every $i<j\le n/2$, the integer $\gcd\left(\binom{n}{i},\binom{n}{j}\right)$ has at least one prime divisor $\ge i$.

QUICK LITERATURE/CONTEXT CHECK

The statement notes Sylvester--Schur: for each $1\le i\le n/2$ there exists a prime $p>i$ dividing $\binom{n}{i}$, but the present question requires a common prime divisor for two coefficients. The ErdosProblems discussion page (late 2025) lists the same known counterexample landscape as in the problem text and does not indicate a full resolution.

ATTACK PLAN

• Proof track: derive mandatory divisibility constraints on $\binom{n}{k}$ from $n$ and $k$ (e.g. $n/\gcd(n,k)\mid \binom{n}{k}$), then try to force a large prime into the intersection of the prime sets of the two coefficients.
• Disproof track: brute-force search for small counterexamples; if none appear, attempt to engineer $n$ with many small prime factors so that all common prime factors of the two coefficients are forced to be small.

WORK

Lemma 699.1 (a guaranteed large divisor of $\binom{n}{k}$ coming from $n$ and $k$). For integers $n\ge 1$ and $1\le k\le n$, let $g:=\gcd(n,k)$. Then \[\frac{n}{g}\ \bigm|\ \binom{n}{k}. \]

Proof. Use the identity \[k\binom{n}{k}=n\binom{n-1}{k-1}. \] Write $n=gn_1$ and $k=gk_1$ with $\gcd(n_1,k_1)=1$. The identity becomes \[gk_1\binom{n}{k}=gn_1\binom{n-1}{k-1},\] so after canceling $g$ we obtain \[k_1\binom{n}{k}=n_1\binom{n-1}{k-1}. \] The right-hand side is divisible by $n_1$. Since $\gcd(n_1,k_1)=1$, the divisibility $n_1\mid k_1\binom{n}{k}$ implies $n_1\mid \binom{n}{k}$. But $n_1=n/g$, proving the claim. $\square$

Lemma 699.2 (prime $n$ case of the conjecture). If $n$ is prime, then for every $1\le i<j\le \lfloor n/2\rfloor$ the conjectured property holds with $p=n$.

Proof. Let $n=p$ be prime. By the binomial theorem, \[(1+x)^p = 1 + \sum_{k=1}^{p-1}\binom{p}{k}x^k + x^p. \] Over $\mathbb{Z}/p\mathbb{Z}$, Fermat's little theorem gives $(1+x)^p\equiv 1+x^p\pmod p$. Comparing coefficients, $p\mid \binom{p}{k}$ for all $1\le k\le p-1$. In particular, $p\mid \binom{p}{i}$ and $p\mid \binom{p}{j}$, hence $p\mid \gcd\left(\binom{p}{i},\binom{p}{j}\right)$. Finally $p=n\ge i$. $\square$

FAST REALITY CHECK (computation). I checked the conjecture by brute force for all integers $4\le n\le 300$ and all pairs $1\le i<j\le \lfloor n/2\rfloor$:

• No counterexample was found for $n\le 300$.
• In particular, for each tested $(n,i,j)$ the integer $\gcd\left(\binom{n}{i},\binom{n}{j}\right)$ had some prime factor $\ge i$.

(The check factors the gcd for each pair, so it is an exact verification in that range.)

VERIFICATION

• Lemma 699.1: verified the coprimality step $\gcd(n_1,k_1)=1$ and used the standard divisibility fact "if $a\mid bc$ and $\gcd(a,b)=1$ then $a\mid c$."
• Lemma 699.2: checked coefficient comparison mod $p$ and ensured $i,j\le p-1$.
• Computational check: ensured loops cover all pairs $i<j\le\lfloor n/2\rfloor$ and that prime factor condition is implemented as "there exists a prime divisor $\ge i$."

FINAL

UNRESOLVED.

1. (i) Strongest proved partial results here:
   • For all $n,k$, $\frac{n}{\gcd(n,k)}\mid \binom{n}{k}$ (Lemma 699.1).
   • For prime $n$, the property holds for all pairs $(i,j)$ with witness prime $p=n$ (Lemma 699.2).
   • Exhaustive computation found no counterexample for $4\le n\le 300$.
2. (ii) First gap: for general composite $n$, given $1\le i<j\le n/2$, force the existence of a prime $p\ge i$ dividing both $\binom{n}{i}$ and $\binom{n}{j}$.
3. (iii) Top 3 next moves:
   1. Use $p$-adic valuation formulas (e.g. via carries/base-$p$ expansions) to understand when a prime $p\ge i$ divides both coefficients; target primes in $[i,2i]$.
   2. For each fixed $i$, attempt to show that the set of $j$ for which all primes $\ge i$ fail to divide the gcd is empty by a covering argument on prime intervals.
   3. Extend computation to larger $n$ but with pruning: for each $(n,i)$ test the "worst" $j$ (empirically near $n/2$) and cache gcd factorizations.
4. (iv) Minimal counterexample structure: a smallest counterexample would be a composite $n$ with some $i\ge 4$ and $j\in(i,n/2]$ such that every prime divisor of $\gcd\left(\binom{n}{i},\binom{n}{j}\right)$ is $<i$; computationally one should expect $n$ to have many small prime factors so that $\binom{n}{i}$ and $\binom{n}{j}$ have large common parts supported only on small primes.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.