Lucas’ Theorem

Lucas’ Theorem: If p is a prime number, and N has base p representation (a_j,…,a₁,a₀) and k has base p representation (b_j,…,b₁,b₀), then (N CHOOSE k) is congruent [mod p] to
(a_j CHOOSE b_j)…(a₁ CHOOSE b₁)(a₀ CHOOSE b₀).

Example: Let N = 588, k = 277, p = 5. 
N = 588 has base 5 representation (4323). 
k = 277 has base 5 representation (2102). 
Thus by Lucas’ Theorem, (588 CHOOSE 277) is congruent [mod 5] to(4 CHOOSE 2) (3 CHOOSE 1) (2 CHOOSE 0) (3 CHOOSE 2)which is 54 = 4 [mod 5].

Fun Corollary: If p is prime and N has base p representation (a_j,…,a₁,a₀), then there are exactly (1+a_j)…(1+a₁)(1+a₀) values of k for which (N CHOOSE k) is NOT a multiple of p. This is the number of non-multiples of p in the N-th row of Pascal’s Triangle.

Example: Since 588 = (4323) in base 5, then (588 CHOOSE k) is a non-multiple of 5 for exactly 5*4*3*4 = 240 values of k. The 588th row of Pascal’s Triangle will have 589 – 240 = 349 multiples of 5.

A special case of this is Odd Numbers in Pascal’s Triangle.

The Math Behind the Fact:
The proof of Lucas’ Theorem is based on this observation: for p prime and r > 0, (p^r CHOOSE k) is a multiple of p for all 0 < k < p^r. To show this, note for 0 < k < N that (N CHOOSE k) = (N/k)(N-1 CHOOSE k-1). So when N = p^r, we havek*(p^r CHOOSE k) = p^r (p^r-1 CHOOSE k-1).At least r powers of p divide the right side of the equation above, whereas at most r-1 powers of p divide k. Thus p must divide (p^r CHOOSE k). (Note this argument only works when p is prime.)

When k = 0 or p^r, then (p^r CHOOSE k)=1. Otherwise (p^r CHOOSE k)=0 [mod p]. Then the binomial theorem shows that when p is prime,(1+x)^{p^r} = 1 + x^{p^r} [mod p].(This is sometimes called the “Freshman Binomial Theorem”.)

Now we show that (588 CHOOSE 277) is congruent to 54 [mod 5]. The general case is similar. In the polynomial (1+x)⁵⁸⁸, the coefficient of x²⁷⁷ will be (588 CHOOSE 277) [mod 5]. But(1+x)⁵⁸⁸ = (1+x)⁴⁽¹²⁵⁾ (1+x)³⁽²⁵⁾ (1+x)²⁽⁵⁾ (1+x)³and our observation above shows that this is congruent [mod 5] to(1+x¹²⁵)⁴ (1+x²⁵)³ (1+x⁵)² (1+x)³.Now how can we create an x²⁷⁷ term? Only by using exactly two x¹²⁵ terms, one x²⁵, no x⁵ terms, and two x¹ terms. How many ways can we do that? Exactly (4 CHOOSE 2)(3 CHOOSE 1)(2 CHOOSE 0)(3 CHOOSE 2) ways, as predicted!

How to Cite this Page: 
Su, Francis E., et al. “Lucas’ Theorem.” Math Fun Facts. <https://www.math.hmc.edu/funfacts>.

References:
R. P. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole, 1986.

Fun Fact suggested by:
Arthur Benjamin