Math Fun Facts!
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.
Get a random Fun Fact!
or
No subject limitations
Search only in selected subjects
    Algebra
    Calculus or Analysis
    Combinatorics
    Geometry
    Number Theory
    Probability
    Topology
    Other subjects
  Select Difficulty  
Enter keywords 

  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
All rights reserved.

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!

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

Share

References:
Subjects:    combinatorics, number theory
Level:    Advanced
Fun Fact suggested by:   Arthur Benjamin
Suggestions? Use this form.
3.68
 
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!
Get the Math Fun Facts
iPhone App!

Want another Math Fun Fact?

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