It is easy to see that $4\mid \binom{2n}{n}$ except when $n=2^k$, and hence it suffices to prove this when $n$ is a power of $2$.

Proved by Sárközy [Sa85] for all sufficiently large $n$, and by Granville and Ramaré [GrRa96] for all $n\geq 5$.

More generally, if $f(n)$ is the largest integer such that, for some prime $p$, we have $p^{f(n)}$ dividing $\binom{2n}{n}$, then $f(n)$ should tend to infinity with $n$. Can one even disprove that $f(n)\gg \log n$?

Sander [Sa92] proved that $f(n)\to \infty$, and later [Sa95] quantified this to $f(n) \gg (\log n)^{1/10-o(1)}$. Sander [Sa95] also proved that $f(n)\ll \log n$ for all $n$, and that $f(n) \gg \log n$ for almost all $n$. The proofs of the latter two facts are very easy using Kummer's theorem -- indeed, this immediately implies that any $p$ divides $\binom{2n}{n}$ with multiplicity $\ll \log_p n$, and that the multiplicity with which $2$ divides $\binom{2n}{n}$ is equal to the number of $1$s in the binary expansion of $n$, which is $\gg \log n$ for almost all $n$.

Erdős and Kolesnik [ErKo99] improved the lower bound for all $n$ to\[f(n) \gg (\log n)^{1/4-o(1)}.\]It remains open whether $f(n) \gg \log n$ for all $n$.

Sander [Sa92b] proved that, for all $0<\epsilon<1$, if $n$ is sufficiently large and $\lvert d\rvert\leq n^{1-\epsilon}$ then $\binom{2n+d}{n}$ is not squarefree.

The largest $n$ known for which $\binom{2n}{n}$ is not divisible by the square of an odd prime is $n=786$ (found by Levine). Guy [Gu04] reports that Erdős 'feels sure that there are no larger such $n$'.

See also [379].

This is mentioned in problem B33 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

Erdős, Graham, Ruzsa, and Straus [EGRS75] have shown that, for any two odd primes $p$ and $q$, there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $pq$.

This is equivalent (via Kummer's theorem) to whether there are infinitely many $n$ which have only digits $0,1$ in base $3$, digits $0,1,2$ in base $5$, and digits $0,1,2,3$ in base $7$.

The sequence of such $n$ is A030979 in the OEIS.

The best result in this direction is due to Bloom and Croot [BlCr25], who proved that, if $p_1,p_2,p_3$ are sufficiently large primes, then there are infinitely many $n$ such that almost all of the base $p_i$ digits are $<p_i/2$. In other words, for all $\epsilon>0$, there are infinitely many $n$ such that $\binom{2n}{n}$ is coprime to $p_1p_2p_3$, except for a factor of size $\leq n^\epsilon$.

This is mentioned in problem B33 of Guy's collection [Gu04]. It is also discussed in an article of Pomerance [Po15c].

Graham offered \$1000 for a solution to this problem (as mentioned in [Gu04] and [BeHa98]).

View the LaTeX source

This page was last edited 28 December 2025.

A question of Erdős, Graham, Ruzsa, and Straus [EGRS75], who proved that if $f(n)$ is the sum in question then\[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n) = \sum_{k=2}^\infty \frac{\log k}{2^k}=\gamma_0\]and\[\lim_{x\to \infty}\frac{1}{x}\sum_{n\leq x}f(n)^2 = \gamma_0^2,\]so that for almost all integers $f(m)=\gamma_0+o(1)$. They also prove that, for all large $n$,\[f(n) \leq c\log\log n\]for some constant $c<1$. (It is trivial from Mertens estimates that $f(n)\leq (1+o(1))\log\log n$.)

A positive answer would imply that\[\sum_{p\leq n}1_{p\mid \binom{2n}{n}}\frac{1}{p}=(1-o(1))\log\log n,\]and Erdős, Graham, Ruzsa, and Straus say there is 'no doubt' this latter claim is true.

This is mentioned in problem B33 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

Erdős and Graham state they can prove that, for $k$ fixed and large, the density of $n$ such that $\binom{n}{k}$ is squarefree is $o_k(1)$. They can also prove that there are infinitely many $n$ such that $\binom{n}{k}$ is not squarefree for $1\leq k<n$, and expect that the density of such $n$ is positive.

Aggarwal and Cambie have observed this problem is resolved by the results of Granville and Ramaré [GrRa96], who in particular show that the density of the set of those $n$ such that $\binom{n}{k}$ is squarefree for exactly $2m+2$ many values of $k$ exists. If this density is $\eta_m$, then the density in the original question is simply\[1-\sum_{0\leq m\leq \frac{r-1}{2}}\eta_m.\]This density is positive since $\eta_{r+1}>0$.

View the LaTeX source

This page was last edited 28 October 2025.

If $s(n)$ denotes the largest integer such that $\binom{n}{k}$ is divisible by $p^{s(n)}$ for some prime $p$ for at least one $1\leq k<n$ then it is easy to see that $s(n)\to \infty$ as $n\to \infty$ (and in fact that $s(n) \asymp \log n$).

This problem was solved in the affirmative by Cambie, Kovač, and Tao (see the comment section). A Lean formalisation of their proof is available here.

There are other simpler constructions: for example, $3^{2^k}$ for arbitrarily large $k$ (see this discussion).

See also [175].

View the LaTeX source

This page was last edited 12 January 2026.

A conjecture of Erdős and Selfridge. Proved by Ecklund [Ec69], who made the stronger conjecture that whenever $n>k^2$ the binomial coefficient $\binom{n}{k}$ is divisible by a prime $p<n/k$. They have proved the weaker inequality $p\ll n/k^c$ for some constant $c>0$.

Discussed in problem B31 and B33 of Guy's collection [Gu04] - there Guy credits Selfridge with the conjecture that if $n> 17.125k$ then $\binom{n}{k}$ has a prime factor $p\leq n/k$.

Stronger forms of this conjecture are [1094] and [1095].

View the LaTeX source

This page was last edited 28 October 2025.

Erdős and Graham write that 'a proof that this cannot happen infinitely often for $\binom{n}{2}$ seems hopeless; probably this can never happen for $\binom{n}{k}$ if $3\leq k\leq n-3$.'

Weisenberg has provided four easy examples that show Erdős and Graham were too optimistic here:\[\binom{7}{3}=5\cdot 7,\]\[\binom{10}{4}= 2\cdot 3\cdot 5\cdot 7,\]\[\binom{14}{4} = 7\cdot 11\cdot 13,\]and\[\binom{15}{6}=5\cdot 7\cdot 11\cdot 13.\]The known values of $n$ for which $\binom{n}{2}$ is the product of consecutive primes are $4,6,15,21,715$ (see A280992).

View the LaTeX source

Erdős once conjectured that $\binom{n}{k}$ must always have a divisor in $(n-k,n]$, but this was disproved by Schinzel and Erdős [Sc58]. A counterexample is given by $n=99215$ and $k=15$. Schinzel conjectured (see problem B34 of [Gu04]) that, for all sufficiently large $k$ which are not prime powers, there exists an $n$ such that $\binom{n}{k}$ is not divisible by any integer in $(n-k,n]$.

It is easy to see that $\binom{n}{k}$ always has a divisor in $[n/k,n]$.

Faulkner [Fa66] proved that, if $p$ is the least prime $>2k$ and $n\geq p$, then $\binom{n}{k}$ has a prime divisor $\geq p$ (except $\binom{9}{2}$ and $\binom{10}{3}$).

This is discussed in problems B33 and B34 of Guy's collection [Gu04], who says that Erdős conjectured this is true for any $c<1$ (if $n$ is sufficiently large).

View the LaTeX source

This page was last edited 18 October 2025.

Erdős and Graham write that $n+1$ always divides $\binom{2n}{n}$ (indeed $\frac{1}{n+1}\binom{2n}{n}$ is the $n$th Catalan number), but it is quite rare that $n$ divides $\binom{2n}{n}$.

Pomerance [Po14] has shown that for any $k\geq 0$ there are infinitely many $n$ such that $n-k\mid\binom{2n}{n}$, although the set of such $n$ has upper density $<1/3$. Pomerance also shows that the set of $n$ such that\[\prod_{1\leq i\leq k}(n+i)\mid \binom{2n}{n}\]has density $1$.

The smallest $n$ for each $k$ are listed as A375077 on the OEIS.

View the LaTeX source

Somani, using ChatGPT, has given a negative answer. In fact, for any $a\geq 2$, if $c=8a^2+8a+1$,\[\binom{2a}{a}\binom{4a+4}{2a+2}\binom{2c}{c}= \binom{2a+2}{a+1}\binom{4a}{2a}\binom{2c+2}{c+1}.\]Further families of solutions are given in the comments by SharkyKesa.

This was earlier asked about in a MathOverflow question, in response to which Elkies also gave an alternative construction which produces solutions - at the moment it is not clear whether Elkies' argument gives infinitely many solutions (although I believe it can).

View the LaTeX source

This page was last edited 12 January 2026.

A theorem of Sylvester and Schur (see [Er34]) states that $P(\binom{n}{k})>k$ if $k\leq n/2$. Erdős [Er55d] proved that there exists some $c>0$ such that, whenever $k\leq n/2$,\[P\left(\binom{n}{k}\right)\gg k\log k.\]Erdős [Er79d] writes it 'seems certain' that this holds for every $c>0$, with only a finite number of exceptions (depending on $c$). Standard heuristics on prime gaps suggest that the largest prime divisor of $\binom{n}{k}$ is, for $k\leq n/2$, in fact\[>e^{c\sqrt{k}}\]for some constant $c>0$.

This is essentially equivalent to [961].

View the LaTeX source

This page was last edited 31 December 2025.

A classical theorem of Mahler states that for any $\epsilon>0$ and integers $k$ and $l$ then, writing\[(n+1)\cdots (n+k) = ab\]where the only primes dividing $a$ are $\leq l$ and the only primes dividing $b$ are $>l$, we have $a < n^{1+\epsilon}$ for all sufficiently large (depending on $\epsilon,k,l$) $n$.

Mahler's theorem implies $f(n)\to \infty$ as $n\to \infty$, but is ineffective, and so gives no bounds on the growth of $f(n)$.

One can similarly ask for estimates on the smallest integer $f(n,k)$ such that if $m$ is the factor of $\binom{n}{k}$ containing all primes $\leq f(n,k)$ then $m > n^2$.

View the LaTeX source

It is trivial that the number of prime factors is\[>\frac{\log \binom{n}{k}}{\log n},\]and this inequality becomes (asymptotic) equality if $k>n^{1-o(1)}$.

View the LaTeX source

A problem of Erdős and Szekeres, who observed that\[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \geq \frac{\binom{n}{i}}{\binom{j}{i}}\geq 2^i\](in particular the greatest common divisor is always $>1$). This inequality is sharp for $i=1$, $j=p$, and $n=2p$.

This was resolved by Bergman [Be11], who proved that for any $2\leq i<j\leq n/2$\[\textrm{gcd}\left( \binom{n}{i},\binom{n}{j}\right) \gg n^{1/2}\frac{2^i}{i^{3/2}},\]where the implied constant is absolute.

View the LaTeX source

A problem of Erdős and Szekeres. A theorem of Sylvester and Schur says that for any $1\leq i\leq n/2$ there exists some prime $p>i$ which divides $\binom{n}{i}$.

Erdős and Szekeres further conjectured that $p\geq i$ can be improved to $p>i$ except in a few special cases. In particular this fails when $i=2$ and $n$ being some particular powers of $2$. They also found some counterexamples when $i=3$, but only one counterexample when $i\geq 4$:\[\textrm{gcd}\left(\binom{28}{5},\binom{28}{14}\right)=2^3\cdot 3^3\cdot 5.\]This is mentioned in problem B31 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 30 September 2025.

A problem of Erdős and Szekeres. It is easy to see that $f(n)\leq n/P(n)$ for composite $n$, since if $j=p^k$ where $p^k\mid n$ and $p^{k+1}\nmid n$ then $\textrm{gcd}\left(n,\binom{n}{j}\right)=n/p^k$. This implies\[f(n) \leq (1+o(1))\frac{n}{\log n}.\]It is known that $f(n)=n/P(n)$ when $n$ is the product of two primes. Another example is $n=30$.

For the second problem, it is easy to see that for any $n$ we have $f(n)\geq p(n)$, where $p(n)$ is the smallest prime dividing $n$, and hence there are infinitely many $n$ (those $=p^2)$ such that $f(n)\geq n^{1/2}$.

View the LaTeX source

A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who believed there is 'no doubt' that the answer is yes.

For example $(87,88)$ and $(607,608)$. Those $n$ such that there exists some suitable $m>n$ are listed as A129515 in the OEIS.

A triple of such $n$ for which $\binom{2n}{n}$ all share the same set of prime divisors is $(10003,10004,10005)$. It is not known whether there are such pairs of the shape $(n,n+k)$ for every $k\geq 1$.

View the LaTeX source

This page was last edited 27 December 2025.

A problem of Erdős, Graham, Ruzsa, and Straus [EGRS75], who say it is 'not hard to show that', for almost all $n$, the minimal such $m$ satisfies\[m=\exp((\log n)^{1/2+o(1)}).\]

View the LaTeX source

This page was last edited 19 October 2025.

Erdős [Er96b] credits this to himself and Gordon 'many years ago', but it is more commonly known as Singmaster's conjecture. For $t=3$ one could take $a=120$, and for $t=4$ one could take $a=3003$. There are no known examples for $t\geq 5$.

Both Erdős and Singmaster believed the answer to this question is no, and in fact that there exists an absolute upper bound on the number of solutions.

Matomäki, Radziwill, Shao, Tao, and Teräväinen [MRSTT22] have proved that there are always at most two solutions if we restrict $k$ to\[k\geq \exp((\log n)^{2/3+\epsilon}),\]assuming $a$ is sufficiently large depending on $\epsilon>0$.

View the LaTeX source

A problem of Erdős, Lacampagne, and Selfridge [ELS88], that was also asked in the 1986 problem session of West Coast Number Theory (as reported here).

In [ELS93] they prove that if the deficiency exists and is $\geq 1$ then $n\ll 2^k\sqrt{k}$.

The following examples are either from [ELS88] or here. The following have deficiency $1$ (there are $58$ examples with $n\leq 10^5$):\[\binom{7}{3},\binom{13}{4},\binom{14}{4},\binom{23}{5},\binom{62}{6},\binom{94}{10},\binom{95}{10}.\]The examples which follow are the only known examples with deficiency $>1$. The following have deficiency $2$:\[\binom{44}{8},\binom{74}{10},\binom{174}{12},\binom{239}{14},\binom{5179}{27},\binom{8413}{28},\binom{8414}{28},\binom{96622}{42}.\]The following have deficiency $3$:\[\binom{46}{10},\binom{47}{10},\binom{241}{16},\binom{2105}{25},\binom{1119}{27},\binom{6459}{33}.\]The following has deficiency $4$:\[\binom{47}{11}.\]The following has deficiency $9$:\[\binom{284}{28}.\]See also [384] and [1094].

Barreto in the comments has given a positive answer to the second question, conditional on two (strong) conjectures.

View the LaTeX source

This page was last edited 27 December 2025.

A stronger form of [384] that appears in a paper of Erdős, Lacampagne, and Selfridge [ELS88]. Erdős observed that the least prime factor is always $\leq n/k$ provided $n$ is sufficiently large depending on $k$. Selfridge [Se77] further conjectured that this always happens if $n\geq k^2-1$, except $\binom{62}{6}$.

The threshold $g(k)$ below which $\binom{n}{k}$ is guaranteed to be divisible by a prime $\leq k$ is the subject of [1095].

More precisely, in [ELS88] they conjecture that if $n\geq 2k$ then the least prime factor of $\binom{n}{k}$ is $\leq \max(n/k,k)$ with the following $14$ exceptions:\[\binom{7}{3},\binom{13}{4},\binom{23}{5},\binom{14}{4},\binom{44}{8},\binom{46}{10},\binom{47}{10},\]\[\binom{47}{11},\binom{62}{6},\binom{74}{10},\binom{94}{10},\binom{95}{10},\binom{241}{16},\binom{284}{28}.\]They also suggest the stronger conjecture that, with a finite number of exceptions, the least prime factor is $\leq \max(n/k,\sqrt{k})$, or perhaps even $\leq \max(n/k,O(\log k))$. Indeed, in [ELS93] they provide some further computational evidence, and point out it is consistent with what they know that in fact this holds with $\leq \max(n/k,13)$, with only $12$ exceptions.

Discussed in problem B31 and B33 of Guy's collection [Gu04] - there Guy credits Selfridge with the conjecture that if $n> 17.125k$ then $\binom{n}{k}$ has a prime factor $p\leq n/k$.

This is related to [1093], in that the only counterexamples to this conjecture can occur from $\binom{n}{k}$ with deficiency $\geq 1$.

There is an interesting discussion about this problem on MathOverflow.

View the LaTeX source

This page was last edited 24 October 2025.

A question of Ecklund, Erdős, and Selfridge [EES74], who proved\[k^{1+c}<g(k)\leq \exp((1+o(1))k)\]for some constant $c>0$, and conjectured $g(k)<L_k=[1,\ldots,k]$, the least common multiple of all integers $\leq k$, for all large $k$. In [EES74] they further conjecture that\[\limsup \frac{g(k+1)}{g(k)}=\infty\]and\[\liminf \frac{g(k+1)}{g(k)}=0.\]The lower bound was improved by Erdős, Lacampagne, and Selfridge [ELS93] and Granville and Ramaré [GrRa96]. The current record is\[g(k) \gg \exp(c(\log k)^2)\]for some $c>0$, due to Konyagin [Ko99b].

Erdős, Lacampagne, and Selfridge [ELS93] write 'it is clear to every right-thinking person' that $g(k)\geq\exp(c\frac{k}{\log k})$ for some constant $c>0$.

Sorenson, Sorenson, and Webster [SSW20] give heuristic evidence that\[\log g(k) \asymp \frac{k}{\log k}.\]See also [1094].

View the LaTeX source

This page was last edited 12 January 2026.