hosted by the Harvey Mudd College Math Department created, authored and ©1999-2010 by Francis Su
Subscribe to our RSS feed or follow us on Twitter.              The Math Fun Facts App!

List All : List Recent : List Popular
About Math Fun Facts / How to Use
Contributors / Fun Facts Home
© 1999-2010 by Francis Edward Su

From the Fun Fact files, here is a Fun Fact at the Advanced level:

# Lucas' Theorem

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 have

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.)

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)3
and 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!

Su, Francis E., et al. "Lucas' Theorem." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References:

Subjects:    combinatorics, number theory
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
3.86
current
rating
Click to rate this Fun Fact...
*   Awesome! I totally dig it!
*   Fun enough to tell a friend!
*   Mildly interesting
*   Not really noteworthy
and see the most popular Facts!
New: get the MathFeed iPhone App!

Brings you news and views on math:
showcasing its power, beauty, and humanity Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College! 