# Prime Numbers and Combinatoric Division

True or false, for all primes p > 2, there are an infinite number of positive integers n for which p does not divide ${2n \choose n}$.

I think the answer would be no, but I am not sure. Since n! has all numbers less than n as factors I would assume that p would be among those. Is my reasoning correct?

• Your reasoning is not complete anyways... remember that $\binom{2n}{n}=\frac{(2n)!}{(n!)(n!)}$. Even if $p$ is a factor of $n!$, it will also be a factor of the other $n!$ as well as a factor of $(2n)!$, but you have to ask the question of how many times $p$ is a factor of each to find out whether the resulting number is still divisible by $p$ or not. Some of the $p$'s will cancel from numerator and denominator, but how many is not immediately obvious. You then have to argue for or against the existence of infinitely many $n$ for which $p$ does not divide $\binom{2n}{n}$. – JMoravitz May 15 '17 at 1:47
• Note for example $\binom{10}{5}=252$ is not divisible by $5$ but is divisible by $7$. $\binom{20}{10}=184756$ again is not divisible by $5$ and is also not divisible by $7$. On the other hand $\binom{16}{8}=12870$ is divisible by $5$ but is not divisible by $7$. Other oddities occur, but the question is if for a given $p$ whether or not there are infinitely many values of $n$ such that $\binom{2n}{n}$ is not divisible by $p$. – JMoravitz May 15 '17 at 1:51
• How would I find if there are infinite or finite values? From what I understand from your post, only if the exponent of p in the prime factorization of 2n is greater than two times that of n then p divides the binomial coefficient. – shrindle May 15 '17 at 2:33
• Not quite... only if the exponent of $p$ in the prime factorization of $(2n)!$ (don't forget the factorial) is higher than two times that of $n!$ will it be... as for an answer... fractal already gave a start to a satisfactory answer below, and I don't expect there to be a cleaner solution than using legendre's formula. – JMoravitz May 15 '17 at 2:55

The answer is actually yes. For a hint, see Legendre's Formula.

Solution:

For $p$ to not divide $\binom{2n}{n}$, $v_p((2n)!)$ must be exactly $v_p(n!) + v_p(n!) = 2v_p(n!)$ (where $v_a(b)$ is defined as the largest nonnegative integer $k$ such that $a^k$ divides b).

So the question is equivalent to, given a prime $p > 2$, do there exist an infinite number of $n$ such that $v_p((2n)!) = 2v_p(n!)$? I claim the answer is yes. Consider $n = p^i$ for some positive integer $i$. Then by Legendre's Formula, $$v_p(n!) = \Bigg\lfloor\dfrac{n}{p}\Bigg\rfloor + \Bigg\lfloor\dfrac{n}{p^2}\Bigg\rfloor + \cdots + \Bigg\lfloor\dfrac{n}{p^i}\Bigg\rfloor = p^{i-1}+p^{i-2}+\cdots+1,$$$$v_p(2n) = \Bigg\lfloor\dfrac{2n}{p}\Bigg\rfloor + \Bigg\lfloor\dfrac{2n}{p^2}\Bigg\rfloor + \cdots + \Bigg\lfloor\dfrac{2n}{p^i}\Bigg\rfloor \\ = 2p^{i-1}+2p^{i-2}+\cdots+2 = 2v_p(n!),$$ as desired. Since there are infinitely many powers of $p$, the conclusion follows.

The key idea here is that there are no powers of $p$ between $p^i$ and $2p^i$. This only works when $p > 2$, and fails for $p = 2$. In fact, $2$ divides $\binom{2n}{n}$ for every positive integer $n$, which you can use $v_2$ and Legendre's formula to prove.

• what exactly is $v_p$? – shrindle May 15 '17 at 1:58
• $v_p(m)$ basically counts the exponent of $p$ in the prime factorization of $m$. For instance, $v_2(24) = 3$, $v_3(81) = 4$, and $v_5(1001) = 0$. It is very useful notation! – fractal1729 May 15 '17 at 1:59
• Can you really pull the 2 out of the floor function? Wouldn't that change the values? For example ⌊2*1.5⌋=3 while 2⌊1.5⌋=2 – shrindle May 15 '17 at 2:05
• @shrindle notice that he started with "Consider $n=p^i$ for some positive integer $i$." Ordinarily your complaint would be valid, but since $\frac{n}{p^k}=p^i/p^k=p^{i-k}$ is an integer for all values of $k\leq i$ it follows that $\lfloor \frac{2n}{p^k}\rfloor = \frac{2n}{p^k}$ since it is an integer, and for convenience, we rewrite again with floor signs $\dots = 2\lfloor \frac{n}{p^k}\rfloor$. Now... consider the case where $k>i$... each term would be less than one, thus the floor is zero and so is often omitted from the expression (note his expression ended at $p^i$) – JMoravitz May 15 '17 at 3:01
• Nice elaboration @JMoravitz, thanks. Another thing I should have noted in the solution is why it only works for $p > 2$; I will edit that in. – fractal1729 May 15 '17 at 12:14