For non-negative integers m and n and a prime p, the following congruence relation holds:
are the base p expansions of m and n respectively.
- A binomial coefficient is divisible by a prime p if and only if at least one of the base p digits of n is greater than the corresponding digit of m.
There are several ways to prove Lucas's theorem; here is a combinatorial argument. Let M be a set with m elements, and divide it into mi cycles of length pi for the various values of i. Then each of these cycles can be rotated separately, so that a group G which is the Cartesian product of cyclic groups Cpi acts on M. It thus also acts on subsets N of size n. Since the number of elements in G is a power of p, the same is true of any of its orbits. Thus in order to compute modulo p, we only need to consider fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. More precisely one can show by induction on k-i, that N must have exactly ni cycles of size pi. Thus the number of choices for N is exactly
Variations and generalizations
- The largest integer k such that pk divides the binomial coefficient (or in other words, the valuation of the binomial coefficient with respect to the prime p) is equal to the number of carries that occur when n and m − n are added in the base p. (This result is known as Kummer's theorem.)
- Andrew Granville has given a generalization of Lucas's theorem to the case of p being a power of prime.
- Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics 1 (2): 184–196. doi:10.2307/2369308. JSTOR 2369308. MR 1505161. (part 1);
- Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311. MR 1505164. (part 2);
- Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics 1 (4): 289–321. doi:10.2307/2369373. JSTOR 2369373. MR 1505176. (part 3)
- Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers". Canadian Mathematical Society Conference Proceedings 20: 253–275. MR 1483922.