f n = min_{1 < k ≤ n/2} gcd(n, C(n,k)). (The infimum is 0 when the range is empty, i.e. n < 4.)

P n is the largest prime factor of n (and 0 if n ≤ 1).

The set whose infimum defines f.

f n unfolds to the infimum of fSet n.

Each gcd(n, C(n,k)) with 1 < k ≤ n/2 belongs to fSet n.

f n is a lower bound: f n ≤ gcd(n, C(n,k)) for every 1 < k ≤ n/2.

Let $f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})$ and let $P(n)$ be the largest prime dividing $n$.

(a) Characterise those composite $n$ such that $f(n) = n/P(n)$.

Erdős–Szekeres [ErSz78] note that $f(n) = n/P(n)$ when $n$ is a product of two primes (erdos_700.variants.prime_mul), with $n = 30$ a further example. The characterisation itself is open; we state it as the (unknown) predicate that is equivalent to being such an n.

Let $f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})$.

(b) Are there infinitely many composite $n$ such that $f(n) > n^{1/2}$?

Erdős–Szekeres [ErSz78] could not prove this. (Since $f(n) \ge p(n)$, the least prime factor of $n$, there are infinitely many $n$ — those of the form $p^2$ — with $f(n) \ge n^{1/2}$; the question asks for the strict inequality.) Here $f(n) > n^{1/2}$ is written as (f n) ^ 2 > n.

Let $f(n) = \min_{1 < k \le n/2} \gcd(n, \binom{n}{k})$.

(c) Is it true that, for every composite $n$, $f(n) \ll_A n/(\log n)^A$ for every $A > 0$?

Erdős–Szekeres [ErSz78] prove the weaker bound $f(n) \le (1 + o(1)) n/\log n$ (the case $A = 1$). Here $f(n) \ll_A n/(\log n)^A$ is spelled out as: for every A > 0 there is a constant C (depending on A) with f(n) ≤ C · n/(log n)^A for every composite n.

Lucas (one step): for prime P ∣ n, if P ∤ C(n,k) then P ∣ k.

f(p^a) = p for a prime p and a ≥ 2 (recorded by Erdős–Szekeres [ErSz78]). In particular, since (p^a) / P(p^a) = p^{a-1}, the prime power p^a is a "hit" (f(n) = n / P(n)) if and only if a = 2.