Proof of Lucas's Theorem

Lucas's Theorem

Let p be a prime number, and let r and c be written in p-ary notation

Then

We take here the standard convention that the binomial coefficient (r,c)=0 if c > r.

Proof

The proof is based on the Binomial Theorem for the expansion of (1+x)^r.

where for each value of c, the inner sum in the last sum is taken over all sets such that

and .

But there is at most one such set of coefficients, given by s_m = c_m if every c_m <= r_m (since there is a unique representation for the p-ary form of c.) If c_m > r_m for some m, then the inner sum is zero. In either case, the theorem follows by equating coefficients of x^c for each 0 <= c <= r.

Back to the mathematical behavior of Pascal's Triangle (mod 2).

1. Fine, N.J. "Binomial coefficients modulo a prime," Mathematical Association of America Monthly, December 1947, 589-592.