Erdős Problem #700

Erdős Problem 700 --- collection record

PROVENANCE AND STATUS

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

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/700.tex.

REUSED SOURCE 1

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

Erdős Problem #700

FORMAL RESTATEMENT

For an integer $n\ge 2$, define \[f(n) := \min_{2\le k\le \lfloor n/2\rfloor}\gcd\left(n,\binom{n}{k}\right). \] Let $P(n)$ denote the largest prime divisor of $n$, and let $p(n)$ denote the smallest prime divisor of $n$. Questions:

1. Characterize composite $n$ for which $f(n)=n/P(n)$.
2. Are there infinitely many composite $n$ with $f(n)>n^{1/2}$?
3. Is it true that for every composite $n$ and every $A>0$ one has $f(n)\ll_A n/(\log n)^A$?

QUICK LITERATURE/CONTEXT CHECK

The problem statement itself provides the easy inequality $f(n)\le n/P(n)$ for composite $n$ using a special choice of $k=p^a$ for the highest prime power dividing $n$, and notes known examples where equality holds. The ErdosProblems discussion page for #700 repeats these remarks and does not indicate a full characterization.

ATTACK PLAN

• Prove the displayed "easy" equality $\gcd\left(n,\binom{n}{p^a}\right)=n/p^a$ rigorously (this gives the upper bound $f(n)\le n/P(n)$).
• Prove a general lower bound $f(n)\ge p(n)$ and use explicit families (e.g. $n=p^2$) to answer $2$.
• For $1$ and $3$, do small-$n$ computation and isolate patterns, but do not claim a full characterization.

WORK

Lemma 700.1 (divisibility bound implies $f(n)\ge p(n)$). For all $n\ge 2$ and all integers $1\le k\le n-1$ we have \[\gcd\left(n,\binom{n}{k}\right)\ \ge\ \frac{n}{\gcd(n,k)}. \] In particular, if $n$ is composite then $\gcd\left(n,\binom{n}{k}\right)\ge p(n)$ for every $2\le k\le \lfloor n/2\rfloor$, hence $f(n)\ge p(n)$.

Proof. By Lemma 699.1 (applied here), $\frac{n}{\gcd(n,k)}\mid \binom{n}{k}$. Since $\frac{n}{\gcd(n,k)}$ also divides $n$, it is a common divisor of $n$ and $\binom{n}{k}$, so it is at most their gcd. This proves the first inequality. If $n$ is composite, then any divisor of $n$ exceeding $1$ is at least the smallest prime divisor $p(n)$. For $1\le k\le n-1$ we have $\gcd(n,k)<n$, so $n/\gcd(n,k)>1$, hence $n/\gcd(n,k)\ge p(n)$, giving the claimed lower bound and thus $f(n)\ge p(n)$. $\square$

Lemma 700.2 (the "easy" exact gcd computation at a prime power index). Let $n\ge 2$ be composite and let $p$ be a prime such that $p^a\mid n$ but $p^{a+1}\nmid n$ (so $p^a$ is the exact highest power of $p$ dividing $n$). Set $k:=p^a$ and write $n=p^a m$ with $p\nmid m$. Then \[\gcd\left(n,\binom{n}{k}\right)=\frac{n}{p^a}=m. \] Consequently $f(n)\le n/p^a\le n/P(n)$.

Proof. First, by Lemma 699.1 with $k=p^a$ we have \[\frac{n}{\gcd(n,k)}=\frac{p^a m}{p^a}=m\ \bigm|\ \binom{n}{k}, \] so $m$ is a common divisor of $n$ and $\binom{n}{k}$, hence $m\mid\gcd\left(n,\binom{n}{k}\right)$. It remains to show that $p\nmid \binom{n}{k}$, which will force the gcd to be exactly $m$ because $n=p^a m$ and $p\nmid m$.

Consider the binomial expansion modulo $p$. In $\mathbb{Z}/p\mathbb{Z}[x]$ we have the "freshman's dream" identity $(1+x)^{p^a}\equiv 1+x^{p^a}\pmod p$. Therefore \[(1+x)^n=(1+x)^{p^a m}=\left((1+x)^{p^a}\right)^m\equiv (1+x^{p^a})^m\pmod p. \] On the left, the coefficient of $x^{p^a}$ is $\binom{n}{p^a}$. On the right, the coefficient of $x^{p^a}$ comes only from choosing $x^{p^a}$ from exactly one of the $m$ factors, so it equals $\binom{m}{1}=m$ modulo $p$. Thus \[\binom{n}{p^a}\equiv m\pmod p. \] Since $p\nmid m$, this congruence implies $p\nmid \binom{n}{p^a}$. Hence the gcd cannot include any factor of $p$, and we conclude \[\gcd\left(p^a m,\binom{p^a m}{p^a}\right)=m=\frac{n}{p^a}. \] The final inequality $f(n)\le n/p^a\le n/P(n)$ follows by taking $k=p^a$ (noting $k\le n/2$ for composite $n$) and using $p^a\ge P(n)$ for the prime power chosen from the largest prime divisor. $\square$

Lemma 700.3 (infinitely many $n$ with $f(n)=\sqrt{n}$). If $n=p^2$ with $p$ prime, then $f(n)=p=\sqrt{n}$. In particular, there are infinitely many composite $n$ with $f(n)\ge n^{1/2}$.

Proof. Let $n=p^2$. By Lemma 700.1, for any $2\le k\le \lfloor n/2\rfloor$ we have $\gcd\left(n,\binom{n}{k}\right)\ge p(n)=p$, so $f(n)\ge p$. Now take $k=p$. We compute \[\binom{p^2}{p}=\frac{p^2}{p}\binom{p^2-1}{p-1}=p\binom{p^2-1}{p-1}. \] Thus $p\mid \binom{p^2}{p}$. To see $p^2\nmid \binom{p^2}{p}$, it suffices to show $p\nmid \binom{p^2-1}{p-1}$. Using the product formula, \[\binom{p^2-1}{p-1}=\prod_{t=1}^{p-1}\frac{p^2-t}{t}. \] Reducing each factor modulo $p$ gives $(p^2-t)/t\equiv (-t)/t\equiv -1\pmod p$, hence \[\binom{p^2-1}{p-1}\equiv (-1)^{p-1}\equiv 1\pmod p. \] So $p\nmid \binom{p^2-1}{p-1}$ and therefore $v_p\left(\binom{p^2}{p}\right)=1$. It follows that $\gcd\left(p^2,\binom{p^2}{p}\right)=p$. Hence $f(p^2)\le p$, and with the lower bound we get $f(p^2)=p=\sqrt{n}$. $\square$

FAST REALITY CHECK (computation). For composite $4\le n\le 200$ I computed $f(n)$ exactly by minimizing $\gcd\left(n,\binom{n}{k}\right)$ over $2\le k\le \lfloor n/2\rfloor$.

• Equality $f(n)=n/P(n)$ holds for many $n$ in this range (including all semiprimes $pq$ and also $n=30$), but not for all $n$; e.g. \[f(12)=3\ne 12/P(12)=4,\qquad f(18)=2\ne 18/P(18)=6. \]
• For $n=p^2\le 200$ (i.e. $4,9,25,49,121,169$), the computation confirms $f(n)=p=\sqrt{n}$.

VERIFICATION

• Lemma 700.2: checked the modular identity $(1+x)^{p^a}\equiv 1+x^{p^a}\pmod p$ is valid because all intermediate binomial coefficients are divisible by $p$.
• Lemma 700.2: ensured the chosen $k=p^a$ satisfies $k\le n/2$ for composite $n$ (since $n=p^a m$ with $m\ge 2$ gives $k\le n/2$).
• Lemma 700.3: checked the congruence computation for $\binom{p^2-1}{p-1}$ modulo $p$; each denominator $t$ is invertible mod $p$.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial results here:
   • General lower bound $f(n)\ge p(n)$ (Lemma 700.1).
   • Exact evaluation $\gcd\left(n,\binom{n}{p^a}\right)=n/p^a$ when $p^a\|\,n$ (Lemma 700.2), yielding $f(n)\le n/P(n)$.
   • Infinite family with $f(n)=\sqrt{n}$: $n=p^2$ (Lemma 700.3), answering question $2$ affirmatively.
2. (ii) First gap: characterize exactly when the minimum over $k$ is achieved at the prime power $k=p^a$ coming from the largest prime divisor (i.e. characterize composite $n$ with $f(n)=n/P(n)$).
3. (iii) Top 3 next moves:
   1. For each prime $q\mid n$, analyze $v_q\left(\binom{n}{k}\right)$ as a function of $k$ to decide when $\gcd(n,\binom{n}{k})$ can drop below $n/P(n)$.
   2. Compute $f(n)$ for all $n\le 10^6$ and classify by prime factorization pattern (prime powers vs. squarefree vs. mixed) to guess a characterization.
   3. For question $3$, attempt to show that for typical composite $n$ there exists $k$ with $\gcd(n,\binom{n}{k})$ supported only on very small primes, e.g. by choosing $k$ with large $\gcd(n,k)$.
4. (iv) Minimal counterexample structure (to $3$): a sequence of composite $n$ for which every $k\le n/2$ forces $\gcd(n,\binom{n}{k})$ to contain a relatively large prime factor, preventing $f(n)$ from being $o(n/(\log n)^A)$.

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.

Erdős Problem #700

FORMAL RESTATEMENT

For an integer $n\ge 2$, define \[f(n) := \min_{2\le k\le \lfloor n/2\rfloor}\gcd\left(n,\binom{n}{k}\right). \] Let $P(n)$ denote the largest prime divisor of $n$, and let $p(n)$ denote the smallest prime divisor of $n$. Questions:

1. Characterize composite $n$ for which $f(n)=n/P(n)$.
2. Are there infinitely many composite $n$ with $f(n)>n^{1/2}$?
3. Is it true that for every composite $n$ and every $A>0$ one has $f(n)\ll_A n/(\log n)^A$?

QUICK LITERATURE/CONTEXT CHECK

The problem statement itself provides the easy inequality $f(n)\le n/P(n)$ for composite $n$ using a special choice of $k=p^a$ for the highest prime power dividing $n$, and notes known examples where equality holds. The ErdosProblems discussion page for #700 repeats these remarks and does not indicate a full characterization.

ATTACK PLAN

• Prove the displayed "easy" equality $\gcd\left(n,\binom{n}{p^a}\right)=n/p^a$ rigorously (this gives the upper bound $f(n)\le n/P(n)$).
• Prove a general lower bound $f(n)\ge p(n)$ and use explicit families (e.g. $n=p^2$) to answer $2$.
• For $1$ and $3$, do small-$n$ computation and isolate patterns, but do not claim a full characterization.

WORK

Lemma 700.1 (divisibility bound implies $f(n)\ge p(n)$). For all $n\ge 2$ and all integers $1\le k\le n-1$ we have \[\gcd\left(n,\binom{n}{k}\right)\ \ge\ \frac{n}{\gcd(n,k)}. \] In particular, if $n$ is composite then $\gcd\left(n,\binom{n}{k}\right)\ge p(n)$ for every $2\le k\le \lfloor n/2\rfloor$, hence $f(n)\ge p(n)$.

Proof. By Lemma 699.1 (applied here), $\frac{n}{\gcd(n,k)}\mid \binom{n}{k}$. Since $\frac{n}{\gcd(n,k)}$ also divides $n$, it is a common divisor of $n$ and $\binom{n}{k}$, so it is at most their gcd. This proves the first inequality. If $n$ is composite, then any divisor of $n$ exceeding $1$ is at least the smallest prime divisor $p(n)$. For $1\le k\le n-1$ we have $\gcd(n,k)<n$, so $n/\gcd(n,k)>1$, hence $n/\gcd(n,k)\ge p(n)$, giving the claimed lower bound and thus $f(n)\ge p(n)$. $\square$

Lemma 700.2 (the "easy" exact gcd computation at a prime power index). Let $n\ge 2$ be composite and let $p$ be a prime such that $p^a\mid n$ but $p^{a+1}\nmid n$ (so $p^a$ is the exact highest power of $p$ dividing $n$). Set $k:=p^a$ and write $n=p^a m$ with $p\nmid m$. Then \[\gcd\left(n,\binom{n}{k}\right)=\frac{n}{p^a}=m. \] Consequently $f(n)\le n/p^a\le n/P(n)$.

Proof. First, by Lemma 699.1 with $k=p^a$ we have \[\frac{n}{\gcd(n,k)}=\frac{p^a m}{p^a}=m\ \bigm|\ \binom{n}{k}, \] so $m$ is a common divisor of $n$ and $\binom{n}{k}$, hence $m\mid\gcd\left(n,\binom{n}{k}\right)$. It remains to show that $p\nmid \binom{n}{k}$, which will force the gcd to be exactly $m$ because $n=p^a m$ and $p\nmid m$.

Consider the binomial expansion modulo $p$. In $\mathbb{Z}/p\mathbb{Z}[x]$ we have the "freshman's dream" identity $(1+x)^{p^a}\equiv 1+x^{p^a}\pmod p$. Therefore \[(1+x)^n=(1+x)^{p^a m}=\left((1+x)^{p^a}\right)^m\equiv (1+x^{p^a})^m\pmod p. \] On the left, the coefficient of $x^{p^a}$ is $\binom{n}{p^a}$. On the right, the coefficient of $x^{p^a}$ comes only from choosing $x^{p^a}$ from exactly one of the $m$ factors, so it equals $\binom{m}{1}=m$ modulo $p$. Thus \[\binom{n}{p^a}\equiv m\pmod p. \] Since $p\nmid m$, this congruence implies $p\nmid \binom{n}{p^a}$. Hence the gcd cannot include any factor of $p$, and we conclude \[\gcd\left(p^a m,\binom{p^a m}{p^a}\right)=m=\frac{n}{p^a}. \] The final inequality $f(n)\le n/p^a\le n/P(n)$ follows by taking $k=p^a$ (noting $k\le n/2$ for composite $n$) and using $p^a\ge P(n)$ for the prime power chosen from the largest prime divisor. $\square$

Lemma 700.3 (infinitely many $n$ with $f(n)=\sqrt{n}$). If $n=p^2$ with $p$ prime, then $f(n)=p=\sqrt{n}$. In particular, there are infinitely many composite $n$ with $f(n)\ge n^{1/2}$.

Proof. Let $n=p^2$. By Lemma 700.1, for any $2\le k\le \lfloor n/2\rfloor$ we have $\gcd\left(n,\binom{n}{k}\right)\ge p(n)=p$, so $f(n)\ge p$. Now take $k=p$. We compute \[\binom{p^2}{p}=\frac{p^2}{p}\binom{p^2-1}{p-1}=p\binom{p^2-1}{p-1}. \] Thus $p\mid \binom{p^2}{p}$. To see $p^2\nmid \binom{p^2}{p}$, it suffices to show $p\nmid \binom{p^2-1}{p-1}$. Using the product formula, \[\binom{p^2-1}{p-1}=\prod_{t=1}^{p-1}\frac{p^2-t}{t}. \] Reducing each factor modulo $p$ gives $(p^2-t)/t\equiv (-t)/t\equiv -1\pmod p$, hence \[\binom{p^2-1}{p-1}\equiv (-1)^{p-1}\equiv 1\pmod p. \] So $p\nmid \binom{p^2-1}{p-1}$ and therefore $v_p\left(\binom{p^2}{p}\right)=1$. It follows that $\gcd\left(p^2,\binom{p^2}{p}\right)=p$. Hence $f(p^2)\le p$, and with the lower bound we get $f(p^2)=p=\sqrt{n}$. $\square$

FAST REALITY CHECK (computation). For composite $4\le n\le 200$ I computed $f(n)$ exactly by minimizing $\gcd\left(n,\binom{n}{k}\right)$ over $2\le k\le \lfloor n/2\rfloor$.

• Equality $f(n)=n/P(n)$ holds for many $n$ in this range (including all semiprimes $pq$ and also $n=30$), but not for all $n$; e.g. \[f(12)=3\ne 12/P(12)=4,\qquad f(18)=2\ne 18/P(18)=6. \]
• For $n=p^2\le 200$ (i.e. $4,9,25,49,121,169$), the computation confirms $f(n)=p=\sqrt{n}$.

VERIFICATION

• Lemma 700.2: checked the modular identity $(1+x)^{p^a}\equiv 1+x^{p^a}\pmod p$ is valid because all intermediate binomial coefficients are divisible by $p$.
• Lemma 700.2: ensured the chosen $k=p^a$ satisfies $k\le n/2$ for composite $n$ (since $n=p^a m$ with $m\ge 2$ gives $k\le n/2$).
• Lemma 700.3: checked the congruence computation for $\binom{p^2-1}{p-1}$ modulo $p$; each denominator $t$ is invertible mod $p$.

FINAL

UNRESOLVED.

1. (i) Strongest proved partial results here:
   • General lower bound $f(n)\ge p(n)$ (Lemma 700.1).
   • Exact evaluation $\gcd\left(n,\binom{n}{p^a}\right)=n/p^a$ when $p^a\|\,n$ (Lemma 700.2), yielding $f(n)\le n/P(n)$.
   • Infinite family with $f(n)=\sqrt{n}$: $n=p^2$ (Lemma 700.3), answering question $2$ affirmatively.
2. (ii) First gap: characterize exactly when the minimum over $k$ is achieved at the prime power $k=p^a$ coming from the largest prime divisor (i.e. characterize composite $n$ with $f(n)=n/P(n)$).
3. (iii) Top 3 next moves:
   1. For each prime $q\mid n$, analyze $v_q\left(\binom{n}{k}\right)$ as a function of $k$ to decide when $\gcd(n,\binom{n}{k})$ can drop below $n/P(n)$.
   2. Compute $f(n)$ for all $n\le 10^6$ and classify by prime factorization pattern (prime powers vs. squarefree vs. mixed) to guess a characterization.
   3. For question $3$, attempt to show that for typical composite $n$ there exists $k$ with $\gcd(n,\binom{n}{k})$ supported only on very small primes, e.g. by choosing $k$ with large $\gcd(n,k)$.
4. (iv) Minimal counterexample structure (to $3$): a sequence of composite $n$ for which every $k\le n/2$ forces $\gcd(n,\binom{n}{k})$ to contain a relatively large prime factor, preventing $f(n)$ from being $o(n/(\log n)^A)$.