Greatest common divisior of $2^n$ and $\binom{2n}{n}$ Find the greatest common divisior of $2^n$ and $\binom{2n}{n}$.
As I assume we have to use identities
$\sum_{k=0}^n\binom{n}{k} = 2^{n}$ and $\sum_{k=0}^{n}\binom{n}{k}^2 = \binom{2n}{n}$.
But I cannot find the connection between $\gcd((a_1+...+a_n),(a_1^2+...+a_n^2))$? Any hints how do we find such thing? 
 A: Kummer's theorem gives you the following answer. Write $n=\sum_{i=0}^kb_i2^i$ in base two, i.e. $b_i\in\{0,1\}$ for all $i$.
Then do grade school addition of $n+n$. Let the number of carries be $\ell$. Then, according to Kummer,
$$
\gcd(2^n,\binom{2n}n)=2^\ell.
$$
Kummer's theorem follows in a relatively straightforward manner from Legendre's formula mentioned by Will Jagy.

For example, when $n=13=1101_2$, you do the addition
$$
\begin{array}{r}1101\\1101\\ \hline11010\end{array}.
$$
You see that there were carries into positions $2^1,2^3$ and $2^4$. Three carries total, so we get that $\binom {26}{13}$ is divisible by $8$ but not by $16$.
A: By Legendre's formula, $v_p(k!)=\displaystyle\sum_{i=1}^{\infty} {[\frac{k}{p^i}]}.$The power of 2 in the binomial is therefore $v_2((2n)!)-2v_2(n!)=n-\displaystyle\sum_{i=1}^{\infty} {[\frac{n}{2^i}]}=A<n.$So the gcd is $2^A$ and I don't think A can be simplified.
A: If we write
$${2n\choose n}=\frac{(2n)!}{n!\cdot n!}$$
then can you work out how many factors $2$ are in ${2n\choose n}$?
Hint:

 Note that $\frac{(2n)!}{n!\cdot n!}=\frac{(n+1)\cdot (n+2)\cdots (2n)}{1\cdot 2\cdots n}$. How many factors $2$ do the numbers $1,2,\cdots,n$ have compared to $(n+1),(n+2),\cdots (2n)$?

