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 nonmultiples of p in the
Nth row of Pascal's Triangle.
Example: Since 588 = (4323) in base 5, then
(588 CHOOSE k) is a nonmultiple 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)(N1 CHOOSE k1). So when
N = p^{r}, we have
k*(p^{r} CHOOSE k)
= p^{r} (p^{r}1 CHOOSE k1).
At least r powers of p divide the right side
of the equation above,
whereas at most r1 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.
<http://www.math.hmc.edu/funfacts>.

