binomial
The binomial coefficient is the number of ways, if you have n things, of choosing r of them; equivalently, the number of n-digit strings, all digits 0 or 1, with r 1s and the rest 0s; equivalently, the coefficient of xr when you expand out (1+x)n.
There’s a nice (and well known) theorem that says: this is odd precisely when subtracting r from n in binary requires no borrowing. (So, e.g., if n is a power of 2, then this happens only when r=0 or r=n.) There’s a very pretty generalization of this which isn’t so well known. (So far as I can remember, I found it myself, but others got there long before me.) Here it is:
Theorem: Suppose you are interested in modulo p, a prime number. (That is, you don’t care if your answer is wrong by a multiple of p.) Then you can compute it as follows. Write down n and r in base p. If r’s base-p representation is shorter than n’s, pad it on the left with zeros to make it the same length. Then
In other words: compute one binomial coefficient for each corresponding pair of digits, and multiply them all together.
You’ll get 0 – i.e., a multiple of p – if and only if one of the factors is a multiple of p, which (it turns out to be easy to prove) happens if and only if for some j, rj>nj. In the case p=2 this (it turns out to be easy to prove) is the same as the condition I mentioned earlier about subtracting r from n.
Proof: it’s enough to show that (mod p) since that lets us split off the last base-p digit, and we can then repeat until we’ve done all the digits. So, consider (1+x)mp+n. This equals ((1+x)p)m(1+x)n. and modulo p this equals (for reasons I’ll explain in a moment) (1+xp)m(1+x)n. Now to get a term containing xrp+s we need the xs term from the second factor, and therefore the xrp=(xp)r term from the first. These come with factors of and , respectively, attached. And we’re done ...
... except that I promised to explain why ((1+x)p)m and (1+xp)m are equal modulo p. Clearly it’s enough if (1+x)p and 1+xp are equal modulo p. Well, when you expand out the former, the coefficient in front of each xr is (by definition) . The coefficients of x0 and xp are both 1, obviously. What about the others? We need to prove that they’re all multiples of p.
Well, remember another definition of : the number of p-bit strings of 0s and 1s containing r 1s. If 0<r<p then a “rotation” of such a string (e.g., 01100 gives 00110, 00011, 10001, 11000) still contains exactly r 1s, and all the p different rotations are different (why?). Hence the number of such strings is a multiple of p, as I claimed.
(You can also prove the theorem more “directly” via a combinatorial argument involving counting the ways of selecting rp+s things from mp+n, and actually that’s how I first proved it. It’s also the proof sketched on the theorem’s Wikipedia page. Maybe there’s an even simpler proof?)