Find the smallest positive integer $m$ such that $ {2015}\choose{m} $ is an even number

Question

Find the smallest positive integer $m$ such that $$ {2015}\choose{m}$$ is an even number.

Since $$ {{2015}\choose{m}} = \frac{2015}{1} \cdot \frac{2014}{2} \cdots \frac{2016-m}{m} = \prod_{k=1}^m \frac{2016-k}{k}, $$ we only need to find the smallest $m$ such that $$ m = 2^{a_m} \cdot p_m, \, 2016-m = 2^{b_m} \cdot q_m, \, 2 \not \mid p_m, \, 2 \not \mid q_m, \, a_m < b_m.$$

In this problem, it turns out that when $m=32$, we have $$ 32=2^5, \, 2016-32=1984=2^6 \cdot 31. $$

However, we will need to try $m=2,4,6,\ldots,32$, the answer will not come out easily.

Is there any easier way to solve this problem?

Answer 1

Kummer's theorem:

for given integers $n \ge m \ge 0$ and a prime number $p$, the $p$-adic valuation $\nu _{p}\left({\tbinom {n}{m}}\right)$ is equal to the number of carries when $m$ is added to $n - m$ in base $p$

Since $2015_{10} = 11111011111_2$ it's clear that for any $m < 32$ there will be no carries, and so $\binom{2015}{m}$ will be odd. However, to subtract $32_{10} = 100000_2$ we need to borrow, and therefore adding $32$ and $2015-32$ will require a carry. QED.

Answer 2

for any natural number $n$, let $v_2(n)$ denote the order to which $2$ divides $n$.

It is not difficult to show that $$v_2(n!)=\sum_{i=1}^{\infty}\Big \lfloor \frac n{2^i} \Big \rfloor\implies v_2(2015!)=2005$$

It follows that we are asking for the least $k$ such that $$v_2(k!)+v_2((2015-k)!)<2005$$

In searching for such a $k$ it is helpful to note that $2^6\,|\,1984$ and that this is the closest integer less than $2015$ which is divisible by a large power of $2$. Thus it is reasonable to imagine that we want $k$ such that $2015-k=1983$, so $k=32$.

Note: This isn't a complete proof, just a strong heuristic to suggest that $32$ is correct. Given the above, $32$ is the first number I would try...though there is still some work involved in proving that it is minimal. The inequality shows an easy way to perform the necessary check without heavy computations.

Answer 3

$2016 = 2^5*63$

So $2016 - j_{odd}*2^k= 63*2^5- j_{odd}*2^k$ will be divisible by $2^k$ for all $k <5$ and the terms $\frac {2016-j_{odd}*2^k}{2^k}=63*2^{5-k} - j_{odd}$ will all be odd.

So for any $m < 32$ then ${2015 m} =\frac {2015*2014*2013*2012*.....(2016-m)}{1*2*3*4*.....*m}$ will have to be odd because all the even terms $2014, 2012, 2010, .......$ (which are divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2....$) are "matched up to be divided" by the even terms, $2,4,6,8,10,12,14,16,...$ which are also divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2...$. So each term in the numerator divisible by a power of $2$ is in "lockstep" with a matching power of $2$ is the denominator.

$2016 -32 = 1984$ which is divisible by $32$ but because $2016 = 63*32$ that means $2016-32 = 62*32$ and as $62$ is even we have broken the lockstep and $2016-32$ is divisble not just be $32$ but by $64$.

So ${2015 32} = \frac {2015*2014*2013*2012*2011....... *1983*1984}{1*2*3*4*5......*31 *32} = \frac {2015*1007*2013*503*2011......*1983*62}{1*1*3*1*5*.....*31*1}$ is even.

In general if $2^k|M+1$ and $2^{k+1}\not \mid M$ then $m = 2^k$ will be the least $m$ so that ${M \choose m}$ is even.

Because $M+1 = odd*2^k$ so $M+1 - even_k$ will be "matched" numerator to denominator to $even_k$ up to $M+1 - 2^k = (odd-1)*2^k$ which will be matched to $2^k$. $\frac {(odd-1)*2^k}{2^k} = odd -1$ is even so the product is even.

=====

Okay, a more formal proof.

If $n\in \mathbb n$ and $n = a*2^k$ where $a$ is $odd$ and $k\ge 0$ then define $f(n) =a$ and $g(n) = 2^k$.

${2015 \choose m} =\frac {\prod_{i=1}^m (2016-i)}{\prod_{i=1}^m i}=$

$\frac {\prod_{i=1;i\text{ odd}}^m (2016-m)\prod_{i=1;i\text{ even}}^m (2016-i)}{\prod_{i=1;i\text{ odd}}^m i\prod_{i=1;i\text{ even}}^m i}=$

$\frac {\prod_{i=1;i\text{ odd}}^m (2016-i)\prod_{i=1;i\text{ even}}^m (2016-i)}{\prod_{i=1;i\text{ odd}}^m i\prod_{i=1;i\text{ even}}^m f(i)\prod_{i=1;i\text{ even}}^m g(i)}=$

$\frac {\prod_{i=1;i\text{ odd}}^m (2016-i)\prod_{i=1;i\text{ even}}^m (2016-m)}{\prod_{i=1;i\text{ odd}}^m i\prod_{i=1;i\text{ even}}^m f(i)}*\frac {\prod_{i=1;i\text{ even}}^m (2016-f(i)g(i))}{\prod_{i=1;i\text{ even}}^m g(i)}=$

$\frac {\prod_{i=1;i\text{ odd}}^m (2016-i)\prod_{i=1;i\text{ even}}^m (2016-m)}{\prod_{i=1;i\text{ odd}}^m i\prod_{i=1;i\text{ even}}^m f(i)}* \prod_{i=1;i\text{ even}}^m (63*\frac{32}{\min(32,g(i))}-f(i)$

Which will be odd if and only if all the $(63*\frac{32}{\min(32,g(i))}-f(i))$ terms are odd for all even $i$.

If $g(i) < 32$ then $(63*\frac{32}{\min(32,g(i))}-f(i))= 63\frac {32}{g(i)} - f(i)$ is odd. If $g(i) \ge 32$ then $(63*\frac{32}{\min(32,g(i))}-f(i))= 63 - f(i)$ is even.

So ${2015 \choose m}$ is odd if and only if $g(i) < 32$ for all $i \le m$ if and only if $m < 32$.

Answer 4

for the curious, 32 is correct. Wrote a command for Legendre's rule. Now that I think about it, this leads to a method for doing this by hand, based on a proof of Legendre by induction that I once posted: http://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n/228351#228351 Give me a few minutes. In brief, $$ \nu_p((n+1)!) = \nu_p(n!) + \nu_p(n+1) \; . $$ Yes. As some of the other answers have already indicated, we are searching for integer $j$ with $$ \nu_2(j+1) < \nu_2(2015-j) \; , $$ after which the answer is $m=j+1.$ Then $$ 5 = \nu_2(31+1) < \nu_2(2015 - 31) = \nu_2(1984) = \nu_2 (64 \cdot 31)=6 $$

========================================================

Sat Aug  4 11:40:24 PDT 2018
1 j+1 2  2 order:   1    2015 - j 2014 order: 1
2 j+1 3  2 order:   0    2015 - j 2013 order: 0
3 j+1 4  2 order:   2    2015 - j 2012 order: 2
4 j+1 5  2 order:   0    2015 - j 2011 order: 0
5 j+1 6  2 order:   1    2015 - j 2010 order: 1
6 j+1 7  2 order:   0    2015 - j 2009 order: 0
7 j+1 8  2 order:   3    2015 - j 2008 order: 3
8 j+1 9  2 order:   0    2015 - j 2007 order: 0
9 j+1 10  2 order:   1    2015 - j 2006 order: 1
10 j+1 11  2 order:   0    2015 - j 2005 order: 0
11 j+1 12  2 order:   2    2015 - j 2004 order: 2
12 j+1 13  2 order:   0    2015 - j 2003 order: 0
13 j+1 14  2 order:   1    2015 - j 2002 order: 1
14 j+1 15  2 order:   0    2015 - j 2001 order: 0
15 j+1 16  2 order:   4    2015 - j 2000 order: 4
16 j+1 17  2 order:   0    2015 - j 1999 order: 0
17 j+1 18  2 order:   1    2015 - j 1998 order: 1
18 j+1 19  2 order:   0    2015 - j 1997 order: 0
19 j+1 20  2 order:   2    2015 - j 1996 order: 2
20 j+1 21  2 order:   0    2015 - j 1995 order: 0
21 j+1 22  2 order:   1    2015 - j 1994 order: 1
22 j+1 23  2 order:   0    2015 - j 1993 order: 0
23 j+1 24  2 order:   3    2015 - j 1992 order: 3
24 j+1 25  2 order:   0    2015 - j 1991 order: 0
25 j+1 26  2 order:   1    2015 - j 1990 order: 1
26 j+1 27  2 order:   0    2015 - j 1989 order: 0
27 j+1 28  2 order:   2    2015 - j 1988 order: 2
28 j+1 29  2 order:   0    2015 - j 1987 order: 0
29 j+1 30  2 order:   1    2015 - j 1986 order: 1
30 j+1 31  2 order:   0    2015 - j 1985 order: 0
31 j+1 32  2 order:   5    2015 - j 1984 order: 6  WOW  
32 j+1 33  2 order:   0    2015 - j 1983 order: 0
33 j+1 34  2 order:   1    2015 - j 1982 order: 1
34 j+1 35  2 order:   0    2015 - j 1981 order: 0
35 j+1 36  2 order:   2    2015 - j 1980 order: 2
Sat Aug  4 11:40:24 PDT 2018

=============================================================

Sat Aug  4 10:57:09 PDT 2018
2015 two order: 2005

1 order: 0     2014 order: 2005 sum    2005
2 order: 1     2013 order: 2004 sum    2005
3 order: 1     2012 order: 2004 sum    2005
4 order: 3     2011 order: 2002 sum    2005
5 order: 3     2010 order: 2002 sum    2005
6 order: 4     2009 order: 2001 sum    2005
7 order: 4     2008 order: 2001 sum    2005
8 order: 7     2007 order: 1998 sum    2005
9 order: 7     2006 order: 1998 sum    2005
10 order: 8     2005 order: 1997 sum    2005
11 order: 8     2004 order: 1997 sum    2005
12 order: 10     2003 order: 1995 sum    2005
13 order: 10     2002 order: 1995 sum    2005
14 order: 11     2001 order: 1994 sum    2005
15 order: 11     2000 order: 1994 sum    2005
16 order: 15     1999 order: 1990 sum    2005
17 order: 15     1998 order: 1990 sum    2005
18 order: 16     1997 order: 1989 sum    2005
19 order: 16     1996 order: 1989 sum    2005
20 order: 18     1995 order: 1987 sum    2005
21 order: 18     1994 order: 1987 sum    2005
22 order: 19     1993 order: 1986 sum    2005
23 order: 19     1992 order: 1986 sum    2005
24 order: 22     1991 order: 1983 sum    2005
25 order: 22     1990 order: 1983 sum    2005
26 order: 23     1989 order: 1982 sum    2005
27 order: 23     1988 order: 1982 sum    2005
28 order: 25     1987 order: 1980 sum    2005
29 order: 25     1986 order: 1980 sum    2005
30 order: 26     1985 order: 1979 sum    2005
31 order: 26     1984 order: 1979 sum    2005
32 order: 31     1983 order: 1973 sum    2004 WOW 
33 order: 31     1982 order: 1973 sum    2004 WOW 
34 order: 32     1981 order: 1972 sum    2004 WOW 
35 order: 32     1980 order: 1972 sum    2004 WOW 
Sat Aug  4 10:57:09 PDT 2018

Answer 5

$n = 2015_{10} = 11111011111_2$ and from Luca's theorem:

$${2015 \choose m} = \prod_{i=0}^{10} {n_i \choose m_i} \pmod 2$$

where all factors are always $1$ except for ${0 \choose m_5}$ which is $0$ if and only if $m_5 = 1$.

The smallest number having $m_5 = 1$ is $32$.

Generally speaking ${n \choose m}$ is odd if and only if $m \land n = m$, and even otherwise, where $\land$ is meant here as a bitwise operation on binary digits. In other words ${n \choose m}$ is odd if and only if all $1$s in $m$ are $1$ also in $n$.