Lucas' Theorem: If p is a prime number, and
N has base p representation
k has base p representation
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.
(4 CHOOSE 2) (3 CHOOSE 1) (2 CHOOSE 0) (3 CHOOSE 2)
which is 54 = 4 [mod 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
Fun Corollary: If p is prime and N has base p representation
then there are exactly
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:
k*(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.)
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 have
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].
= (1+x)4(125) (1+x)3(25)
and our observation above shows that
this is congruent [mod 5] to
Now how can we create an x277 term?
Only by using exactly
two x125 terms,
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.