# primes dividing binomial coefficients

Dear All,

I am considering maximal subgroups of odd index in Alternating and Symmetric groups, and this leeds me to some questions on binomial coefficients that I presently do not know and that I need some hints and suggestions :

1. Assume that $ab=2^t$ with $a>1, b>1,t\geq 3$. Which values of $a$ and $b$ such that $$\frac{(2^t)!}{(a!)^b.b!}$$ is odd and smallest.

2. Let $n\geq 9$ be an odd integer (not prime) and $p$ the largest prime less than $n$. Is there always an integer $r\geq 1$ such that $\binom{n}{r}$ is odd and divisible by $p$. Note that this is not true for the case $n=9$. Is it also true for $n$ even?

Thanks you very much in advance for comments and advice.

• Use Lucas's theorem: http://en.wikipedia.org/wiki/Lucas'_theorem – Chris Godsil Jun 23 '12 at 15:23
• For (1), the quotients are all odd, and I think the smallest occur when $b=2$. I think this can be proved with Stirling's formula, but perhaps there is a nice inductive argument. – Douglas Zare Jun 23 '12 at 17:12
• @Chris Godsil : Thanks for your indicating me to use Lucas's theorem that I did not know before. @Douglas Zare : Thanks. I also think that the smallest occurs when $b=2$ but I am still on the way to prove that. – Ben Jun 25 '12 at 7:24

Hi! I have a proposed answer for 2).

You can construct an infinite series of counter examples. Erdos proved that there are primes between $n$ and $2n$. Now consider $2n=2^k$ for some $k>2$.

We can observe that the binomial number $\binom{2n+1}{r}, 1< r < n+1$ is always even. The upper product have powers of 2 as the following sequence: $\lbrace k,1,2,1,3,\dots,s \rbrace$
while the bottom product have powers of 2 of the form: $\lbrace 1,2,1,3,\dots,s,k-1\rbrace$.
This can be reflected for cases $\binom {2n+1}{r}, n < r < 2n$.

The difference of the sum of these 2 sequences is at least 1. As a result, the binomial number may be divisible by $p$ but it will not be even.

(Edit) Exception: When the binomial number is $\binom{2n+1}{1}$ or $\binom{2n+1}{2n}$ you have either no powers of 2 or same powers of 2. But in this case it will not be divisible by $p$.

• More generally, using Lucas' Theorem, take q to be the smallest prime greater than 2^t with q not a Mersenne prime, then any number m between 2^t and q should serve: When n is large enough for m choose n to be divisible by the preceding prime p, the binary expansion of n will start with 1 in a place where m's expansion has a 0. One can also do this starting with b times 2^t for small odd numbers b, providing b2^t+1 is not prime. Gerhard "Ask Me About Systtem Design" Paseman, 2012.06.23 – Gerhard Paseman Jun 23 '12 at 18:26
• Oops. For b=3 it will not work. This may lead to characterizing which m ha e the desired property. Gerhard "Ask Me About System Design" Paseman, 2012.06.23 – Gerhard Paseman Jun 23 '12 at 20:06
• Thanks for your answer and comments. In fact, Nagura proved that for $n\geq 25$, there exists a prime between $n$ and $\frac{6}{5}n$. And if we take any $n$ in the interval $[2^t+[2^t/6]+1,2^{t+1}-1]$ and $r=n-2^t$ then $\binom{n}{r}$ should do the job. – Ben Jun 26 '12 at 20:27
• Chebyshev was the first who proved this, not Erdos:) – Fedor Petrov Sep 8 '16 at 7:33

About the question (1), I quoted here the result from this paper of Attila Maróti

First, We may assume that $a\geq b$ since if $b>a$ then $$b!^{a-1}=a!^{a-1}(a+1)^{a-1}\cdots b^{a-1}>a!^{a-1}a^{(b-a)(a-1)}$$ In addition, we have that $a^{a-1}>1.2.\cdots.a=a!$ and so $$b!^{a-1}>a!^{a-1}a!^{b-a}=a!^{b-1}$$ which implies that $$b!^a.a!>a!^b.b!\Rightarrow \frac{m!}{a!^b.b!} > \frac{m!}{b!^a.a!}$$

Assume now that $m=a_1b_1=a_2b_2$ with $b_1\leq a_1, b_2\leq a_2$. If $b_1\leq b_2$ and $a_1\geq a_2$ then

$$a_1!^{b_1}.b_1! \geq a_2!^{b_1}(a_2+1)^{b_1}\cdots a_1^{b_1}b_1! \geq a_2!^{b_1}a_2^{(a_1-a_2)b_1}b_1! \quad (\rm{since ~ a_1\geq a_2})$$

$$= a_2!^{b_1}b_1! (a_2^{a_2})^{\frac{b_1}{a_2}(a_1-a_2)} = a_2!^{b_1}b_1! (a_2^{a_2-1}a_2)^{\frac{b_1}{a_2}(a_1-a_2)}$$

$$\geq a_2!^{b_1}b_1! (a_2!b_2)^{\frac{b_1}{a_2}(a_1-a_2)} = a_2!^{b_1}b_1! (a_2!b_2)^{b_2-b_1} \quad (\rm{since ~ a_2\geq b_2 ~ and ~ a_1b_1=a_2b_2})$$

$$\geq a_2!^{b_2}b_1!(b_1+1)\cdots b_2 = a_2!^{b_2}b_2! \quad (\rm{since ~ b_2\geq b_1})$$ and hence $$\frac{m!}{a_1!^{b_1}.b_1!}\leq \frac{m!}{a_2!^{b_2}.b_2!}$$

Your first problem has a simple solution. Suppose $p$ is a prime and $(n!)_p$ is the $p$-part of $n!$. Dirichlet proved $(n!)_p=p^k$ where $k = (n-s_p(n))/(p-1)$ and $s_p(n)$ is the sum of the base-$p$ digits of $n$. Let $a=2^\alpha$ and $b=2^\beta$. Then $(a!)_2 = 2^{a-1}$, $(b!)_2 = 2^{b-1}$ and $((ab)!)_2 = 2^{ab-1}$. The index of the imprimitive group $S_a\wr S_b$ in $S_{ab}$ is $(ab)!/((a!)^b\,b!)$ and this odd for all $\alpha,\beta\geqslant0$.

Proof: $((a!)^b\,b!)_2 = (2^{a-1})^b\,2^{b-1}=2^{ab-1}=((ab)!)_2$. Thus a Sylow 2-subgroup of $S_a\wr S_b$ has order $2^{ab-1}$ as does a Sylow 2-subgroup of $S_{ab}$, and so $(ab)!/((a!)^b\,b!)$ is odd. QED