N is a positive integer.
Find the GCD of C(2n,1), C(2n,3), ….C(2n,2n-1)
where C(a,b) = a!/(a - b)!b!:
Lets start with a lemma:
Define positive integers x, y and positive prime z
If x,y,z satisfy the inequality z^(y+1) > x >= z^y then C(x, z^y) is coprime to z.
The border case x=z^y is trivial C(x, z^y) = 1 which is trivially coprime to z.
Otherwise expand C(x, z^y) into
x * (x-1) * ... * (z^y+2) * (z^y+1)
-----------------------------------
(x-z^y) * (x-z^y-1) * ... * 2 * 1
Then rewrite this quotient on products into a product of quotients:
x x-1 z^y+2 z^y+1
----- * ------- * ... * ----- * -----
x-z^y x-z^y-1 2 1
Each individual quotient has a numerator and denominator with difference of z^y. Let z^w is the largest power of z that divides the numerator.
w must be less then or equal to y since z^y is the largest possible power of z that is less than x.
z^w divides the numerator and z^y, then z^w divides the denominator
Then z^w must also be the largest power of z that divides the denominator.
Therefore the reduced quotient will have all factors of z cancel.
Applying this to every quotient we can conclude the product will be coprime to z
Lemma proven.
Now to the problem.
Let p be an arbitrary odd prime and let k be the power satisfying p^(k+1) < 2n <= p^k.
p^k is odd and is therefore in the set C(2n, odd). Now apply the Lemma to C(2n, p^k). This tells us p is coprime to C(2n, p^k) and therefore p is not a factor of the GCD.
So at this point the GCD is some power of 2.
Now write (2n, odd) by breaking off the largest two terms of 2n! and the largest term of each of (odd)! and (2n-odd)!
C(2n, odd) = C(2n-2, odd-1) * 2n*(2n-1)/(odd*(2n-odd))
2n-1, odd and 2n-odd are all coprime to 2 so the only part of C(2n, odd) which will affect the GCD are 2n and C(2n-2, odd-1).
Every member of C(2n, odd) will have the 2n factor so the GCD is a multiple of the largest power of 2 that divides 2n.
Let 2^j be the largest power of 2 that divides 2n-2. Now look at the member where odd=2^j+1. This will have C(2n-2, odd-1) become C(2n-2, 2^j) which by the lemma is coprime to 2.
Then that brings us to the conclusion that the GCD is exactly the largest power of 2 that divides 2n. QED
Solution
