Lucas' Theorem

Lucas' theorem asserts that, for p prime, a ≥ 1 and 0 < k < pa, C(pa, k) ≡ 0 (mod p), where C(n, m) denotes the binomial coefficient "n choose m". Its particular case, where p = 2, was instrumental in establishing a relationship between Pascal's triangle and Sierpinski's gasket. We had to go to a considerable length to prove this variant of the theorem. Surprisingly, there is a short proof based on an engaging property of the binomial coefficients

(1) k·C(n, k) = n·C(n - 1, k - 1).

This identity admits an elegant combinatorial proof. Assume the task is to choose a k-member committee and its chairman out of a group of n candidates. We can approach the task in two ways:

  1. First select k members of the committee (which can be done in C(n, k) ways) and out of the selected group choose one person to head the committee. This can be done in k ways. In all, there are k·C(n, k) ways to choose a committee and its chairman.

  2. First, choose the committee's chairman out of n candidate. Next choose k - 1 committee members out of the remaining n - 1 candidates. This can be accomplished in n·C(n - 1, k - 1) ways.

(1) merely asserts that the number of ways to compose the committee is the same regardless of the manner in which it is counted.

Now, for Lucas' theorem. Let n = pa, with p prime, a ≥ 1, and 0 < k < n. (1) then becomes

(2) k·C(pa, k) = pa·C(pa - 1, k - 1),

so that the left hand side has a prime factor p. However, k < pa, which means that k, by itself, may at most be divisible by pa-1, leaving at least one factor p for C(pa, k). In other words, C(pa, k) is divisible by p:

(3) C(pa, k) ≡ 0 (mod p).

References

  1. A. T. Benjamin, J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, MAA, 2003
  2. I. Stewart, Game, Set and Math, Penguin Books, 1989

Pascal's Triangle and the Binomial Coefficients

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71945764