On computing: $ \gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right)$

Solution 1:

Let $q = 2^i$ where $2^i | 2n$ and $2^{i+1} \not|2n$. Claim: $d=q$.

First we'll show that each term ${2n \choose 2k+1}$, for $0 \leq k \leq n-1$ has $q$ as a factor. Consider,

$$\begin{align*} {2n \choose 2k+1} &= \frac{(2n)(2n-1)(2n-2) \cdots (2n- [2k+1] + 1)}{(2k+1)(2k)(2k-1)\cdots(1)}\\ &= \frac{2n}{2k+1} \cdot {2n-1 \choose 2k}\\ &= \frac{2n{2n-1 \choose 2k}}{2k+1} \end{align*}$$

Since $k \leq n-1$, $2k < 2n-1$, and the number ${2n-1 \choose 2k}$ is a nonzero integer. Now since ${2n \choose 2k+1}$ is an integer, we know that $2k+1$ divides the numerator. There are no factors of $2$ in $2k+1$, therefore, $q$ must survive to be a factor of ${2n \choose 2k+1}$.

Second we show that $d \leq q$. We know at least that $q$ and $d$ share the same highest power of 2, since one of the terms is ${2n \choose 1} = 2n$. Now as Andre points out in the comments, this means we're done at this point. Since OP proved that $d$ is a power of 2, we have $d=q$.

Solution 2:

Here’s a short argument for the second part of Shaun’s proof.

Suppose that $p$ is an odd prime dividing $2n$, say $2n = mp^k$, where $p\nmid m$. Then I claim that

$$\begin{align*} \binom{2n}{p^k}&=\frac{(2n)!}{p^k!(2n-p^k)!}\\ &=\frac{(mp^k)!}{p^k!((m-1)p^k)!}\\ &=\frac1{p^k!}\prod_{i=0}^{p^k-1}(mp^k-i)\\ &=m\prod_{i=1}^{p^k-1}\frac{(m-1)p^k+i}i \end{align*}$$

is not divisible by $p$. Clearly $p\nmid m$. If $1\le i\le p^k-1$, let $p^s$ be the highest power of $p$ dividing $(m-1)p^k+i$. Then $s<k$ and $p^s\mid i$, so the factor $$\frac{(m-1)p^k+i}i$$ contributes no factor of $p$ to $\dbinom{2n}{p^k}$. Thus, $p\nmid d$.

On the other hand, $d\mid 2n$, so any prime factor of $d$ must divide $2n$. It follows that $d$ has no odd prime factors and hence (by the first part of Shaun’s proof) that $d$ is the highest power of $2$ dividing $2n$.