gpt pro 5.2 attempt on Math-908

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)$.