While skimming the book Concrete Mathematics, (edit: first edition) I came across the following problem, which is listed there as a Research Problem: (Chapter 5, Exercise 96)

Is ${2n \choose n}$ divisible by the square of a prime for all $n > 4$.

This problem looked to me much simpler than a divisibility problem that I found on MO (look here), but then again, I guess in number theory, the simpler the problems looks, the harder it usually is!

The nice form of this problem has made me very curious to find out more about it. But because I do not have more than a fleeting acquaintance with number theory, I don't know what search keywords would be useful to gain more information about this problem.

Thus, could somebody please tell me more about this problem and its current status?

  • 1
    $\begingroup$ Try searching "central binomial coefficient" or "middle binomial coefficient". $\endgroup$ – Mark Grant Nov 13 '10 at 14:51
  • $\begingroup$ In the second edition of Concrete Math, this seems to be Exercise 112, and it reads "Is $2n\choose n$ divisible either by 4 or 9, for all $n>4$ except for $n=64$ and $n=256$?" $\endgroup$ – Sidney Raffer Nov 13 '10 at 15:44
  • $\begingroup$ I must mention that as usual, I am impressed at the speed with which one often obtains great answers on MO! $\endgroup$ – Suvrit Nov 13 '10 at 17:25
  • 2
    $\begingroup$ This might also interest you: Robert J Betts, Lack of divisibility of C(2N,N) by three fixed odd primes infinitely often, ... [1010.3070] at arXiv. $\endgroup$ – Bruce Arnold Nov 13 '10 at 21:47

This is/was known as the Erdős square-free conjecture, and seems to now be solved. See the bottom of this page.

| cite | improve this answer | |
  • 6
    $\begingroup$ Yes, it was proved in 1980 by S´ark¨ozy, A. (On divisors of binomial coefficients. I. J. Number Theory 20 (1985), no. 1, 70–80.) that this conjecture holds for sufficiently large values of $n$, and by A. Granville and O. Ramar´e (Explicit bounds on exponential sums and the scarcity of squarefree binomial coefficients. Mathematika 43 (1996), no. 1, 73–107.) for all $n>4$. $\endgroup$ – Fedor Petrov Nov 13 '10 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.