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

I would like to calculate

$$d=\gcd \left({2n \choose 1}, {2n \choose 3},\cdots, {2n \choose 2n-1}\right)$$

We have:

$$\sum_{k=0}^{n-1}{2n \choose 2k+1}=2^{2n-1}$$

$$d=2^k, 0\leq k\leq2n-1$$

...

Any idea?

-
Empirically, it seems that $d$ is the largest power of 2 dividing $2n$, although I have no idea how prove this, too. – Sangchul Lee Dec 23 '11 at 20:20
One might be able to use $$\mathrm{ord}_p\gcd(a,b,\dots,c)=\min\{\mathrm{ord}_pa,\,\mathrm{ord}_pb,\dots, \mathrm{ord}_p c\} \tag{1}$$ & $$\mathrm{ord}_p{2n\choose l+2}=\mathrm{ord}_p{2n\choose l}+\mathrm{ord}_p\frac{(2n-l-1)(2n-l)}{(l+1)(l+2)} \tag{2}$$ with induction to show it's $2^m\|2n$. – anon Dec 23 '11 at 20:58

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$.

-
Ah, your second part finishes up the proof I was going to write but couldn't figure out. +1. – anon Dec 23 '11 at 22:49
I must be feeling particularly dense, but didn't the OP start by proving that the $\gcd$ is a power of $2$? – André Nicolas Dec 25 '11 at 7:23

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$.

-
@Shaun: You’re right, but I think that I’ve fixed it now. It’s necessary to use the highest power of $p$ dividing $2n$; in your example that’s $3^2=9$, and $\binom{18}9=48620$, which is not divisible by $3$. – Brian M. Scott Dec 24 '11 at 1:16
@Brian: In the second line of the chain of equalities, the $p$'s should also be $p^k$. – Ted Dec 24 '11 at 2:24
@Ted: Fixed; thanks. – Brian M. Scott Dec 24 '11 at 3:47