Lucas’ Theorem: If p is a prime number, and N has base p representation (aj,…,a1,a0) and k has base p representation (bj,…,b1,b0), then (N CHOOSE k) is congruent [mod p] to
(aj CHOOSE bj)…(a1 CHOOSE b1)(a0 CHOOSE b0).
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 (aj,…,a1,a0), then there are exactly (1+aj)…(1+a1)(1+a0) 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, (pr CHOOSE k) is a multiple of p for all 0 < k < pr. To show this, note for 0 < k < N that (N CHOOSE k) = (N/k)(N-1 CHOOSE k-1). So when N = pr, we havek*(pr CHOOSE k) = pr (pr-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 (pr CHOOSE k). (Note this argument only works when p is prime.)
When k = 0 or pr, then (pr CHOOSE k)=1. Otherwise (pr CHOOSE k)=0 [mod p]. Then the binomial theorem shows that when p is prime,(1+x)p^r = 1 + xp^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)588, the coefficient of x277 will be (588 CHOOSE 277) [mod 5]. But(1+x)588 = (1+x)4(125) (1+x)3(25) (1+x)2(5) (1+x)3and our observation above shows that this is congruent [mod 5] to(1+x125)4 (1+x25)3 (1+x5)2 (1+x)3.Now how can we create an x277 term? Only by using exactly two x125 terms, one x25, no x5 terms, and two x1 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>.
R. P. Stanley, Enumerative Combinatorics, Wadsworth & Brooks/Cole, 1986.
Fun Fact suggested by: