Computing the Greatest Common Divisor of Binomial Coefficients $\left(\genfrac{}{}{0ex}{}{mn}{mk}\right)$

Abstract

The greatest common divisor (GCD) of $\left(\genfrac{}{}{0ex}{}{2n}{2k}\right)$ for $1\le k<n$ is known to be some power of 2 times the product of all odd primes p such that $2n=p^i+p^j$. We complete the analysis of this GCD by showing that this power of 2 is either 1 or 0 and relates it to Mersenne primes. We also show how to efficiently compute $GCD\{(\genfrac{}{}{0ex}{}{mn}{mk}):1\le k<n\}$ when n and m satisfy certain conditions.

6 pages