Divisibility of central binomial coefficients

Importance: Medium ✭✭
Author(s): Graham, Ronald L.
Recomm. for undergrads: yes
Prize: $1,000 each
Posted by: maxal
on: August 5th, 2007

\begin{problem}[1] Prove that there exist infinitely many positive integers $n$ such that $$\gcd({2n\choose n}, 3\cdot 5\cdot 7) = 1.$$ \end{problem}

\begin{problem}[2] Prove that there exists only a finite number of positive integers $n$ such that $$\gcd({2n\choose n}, 3\cdot 5\cdot 7\cdot 11) = 1.$$ \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

The binomial coefficient ${2n\choose n}$ is not divisible by prime $p$ iff all the base-$p$ digits of $n$ are smaller than $\frac{p}{2}.$

It has been conjectured that 1, 2, 10, 3159, and 3160 are the only positive numbers for which $\gcd({2n\choose n}, 3\cdot 5\cdot 7\cdot 11) = 1$ holds.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

\href[P. Erdos, R.L. Graham, I.Z. Ruzsa and E.G. Straus "On the Prime Factor of $2n \choose n$." Math. Comp. 29 (1975), 83-92.]{http://www.math.ucsd.edu/~sbutler/ron/75_03_prime_factors.pdf}

\href[Sequence A030979: Numbers n such that C(2n,n) is not divisible by 3, 5 or 7.]{https://oeis.org/A030979}

\href[Andrew Granville. "The Arithmetic Properties of Binomial Coefficients."]{http://www.cecm.sfu.ca/organics/papers/granville/index.html}

* indicates original appearance(s) of problem.

It seems Problem (1) was

It seems Problem (1) was solved last year, see http://arxiv.org/abs/1010.3070

How about Problem 2?

2, 10, and 3159 are not valid for problem (2)

In the initial comment five values are stated to be not divisible by 3, 5, 7, and 11. That is true for 1 and 3160 but not for 2, 10, and 3159:

The last base-3-digit of 2 is 2. The last base-11-digit of 10 is 10. The last base-5-digit 3159 is 4.

Or check these facts:

${{2 \times 2} \choose 2} = 6 = 3 \times 2$

${{2 \times 10} \choose 10} = 184756 = 11 \times 16796$

2 and 3159 are not in the sequence A030979 (mentioned in the bibliography).

Reference for problem (2)

It appears that the right reference for question 2 should be \href[A151750]{http://oeis.org/A151750} instead.

Problem 1 solved?

Looks like Problem 1 was solved by http://arxiv.org/PS_cache/arxiv/pdf/1010/1010.3070v1.pdf

Does not look like it.

Does not look like it.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.