Lucas' Theorem: If p is a prime number, and N has base p representation (a_{j},…,a_{1},a_{0}) and k has base p representation (b_{j},…,b_{1},b_{0}), then (N CHOOSE k) is congruent [mod p] to

(a_{j} CHOOSE b_{j})…(a_{1} CHOOSE b_{1})(a_{0} CHOOSE b_{0}).

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_{1},a_{0}), then there are exactly (1+a_{j})…(1+a_{1})(1+a_{0}) 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}^{r}^{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)^{588}, the coefficient of x^{277} 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)^{3}and our observation above shows that this is congruent [mod 5] to(1+x^{125})^{4} (1+x^{25})^{3} (1+x^{5})^{2} (1+x)^{3}.Now how can we create an x^{277} term? Only by using exactly two x^{125} terms, one x^{25}, no x^{5} terms, and two x^{1} 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