$C(n,p)$: even or odd?

Can we determine if a binomial coefficient $C(n,p)$ is even or odd, without calculating its value? ($p\lt n$, $p$ and $n$ are positive integers)

Solution 1:

There is a beautiful result of Kummer that says that if $q$ is a prime, then the largest power of $q$ that divides $\binom{m+n}{n}$, $m$ and $n$ nonnegative, is the number of carries when $m$ and $n$ are added in base $q$.

As a corollary, we get the Theorem of Lucas mentioned by Michael Lugo: we get a carry in the addition if and only if there is a $k$ such that the $k$th digit of $m+n$ in base $q$ is smaller than the $k$th digit in the base $q$ expansion of $n$, so $\binom{m+n}{n}$ is divisible by $q$ if and only if there is a $k$ such that the $k$th digit of the base $q$ expansion of $m+n$ is smaller than the $k$th digit of the base $q$ expansion of $n$.

Thus, to determine if $\binom{n}{p}$ is odd, you just need to know whether there is at least one carry when adding $p$ and $n-p$ in base $2$; you get a carry exactly when the $k$th binary digit of both $n-p$ and $p$ is $1$.

So just write $p$ and $n-p$ in binary, one digit at a time (from least significant to most significant digit), until you get that both are $1$; or write $p$ and $n$ one binary digit at a time, until you get a $1$ in $p$ and a $0$ in $n$. If this happens, $\binom{n}{p}$ is even; otherwise, it is odd.

Andrew Granville's paper Arithmetic properties of binomial coefficients is chock full of interesting stuff about binomial coefficients and their divisibility. The proof of Kummer's Theorem can be found there. There are also other formats available.

Solution 2:

Yes.

We only need to know how many powers of two appear in the prime factorization of C(n,p). The number of powers of two that appear in the prime factorization of $n!$ is $\lfloor n/2 \rfloor + \lfloor n/4 \rfloor + \lfloor n/8 \rfloor + \cdots$ -- count all the multiples of two, of four, of eight, and so on. This turns out to be $n$ minus the number of ones in the binary expansion of $n$.

It turns out that this reduces to the following: C(n,p) is odd if and only if every bit of the binary expansion of $p$ is less than or equal to the corresponding bit of the binary expansion of $n$. This is due to Lucas.