Lucas's theorem - Alchetron, The Free Social Encyclopedia

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) by a prime number p in terms of the base p expansions of the integers m and n.

Formulation

For non-negative integers m and n and a prime p, the following congruence relation holds:

( m n ) ≡ ∏ i = 0 k ( m i n i ) ( mod p ) ,

where

m = m k p k + m k − 1 p k − 1 + ⋯ + m 1 p + m 0 ,

and

n = n k p k + n k − 1 p k − 1 + ⋯ + n 1 p + n 0

are the base p expansions of m and n respectively. This uses the convention that ( m n ) = 0 if m < n.

Consequence

A binomial coefficient ( m n ) 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.

Proofs

There are several ways to prove Lucas's theorem. We first give a combinatorial argument and then a proof based on generating functions.

Combinatorial argument

Let M be a set with m elements, and divide it into m_i cycles of length pⁱ 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 C_pⁱ 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 ( m n ) 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 n_i cycles of size pⁱ. Thus the number of choices for N is exactly ∏ i = 0 k ( m i n i ) ( mod p ) .

Proof based on generating functions

This proof is due to Nathan Fine.

If p is a prime and n is an integer with 1 ≤ n ≤ p − 1, then the numerator of the binomial coefficient

( p n ) = p ⋅ ( p − 1 ) ⋯ ( p − n + 1 ) n ⋅ ( n − 1 ) ⋯ 1

is divisible by p but the denominator is not. Hence p divides ( p n ) . In terms of ordinary generating functions, this means that

( 1 + X ) p ≡ 1 + X p ( mod p ) .

Continuing by induction, we have for every nonnegative integer i that

( 1 + X ) p i ≡ 1 + X p i ( mod p ) .

Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that m = ∑ i = 0 k m i p i for some nonnegative integer k and integers m_i with 0 ≤ m_i ≤ p-1. Then

∑ n = 0 m ( m n ) X n = ( 1 + X ) m = ∏ i = 0 k ( ( 1 + X ) p i ) m i ≡ ∏ i = 0 k ( 1 + X p i ) m i = ∏ i = 0 k ( ∑ n i = 0 m i ( m i n i ) X n i p i ) = ∏ i = 0 k ( ∑ n i = 0 p − 1 ( m i n i ) X n i p i ) = ∑ n = 0 m ( ∏ i = 0 k ( m i n i ) ) X n ( mod p ) ,

where in the final product, n_i is the ith digit in the base p representation of n. This proves Lucas's theorem.

Variations and generalizations

Kummer's theorem asserts that the largest integer k such that p^k divides the binomial coefficient ( m n ) (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.

Andrew Granville has given a generalization of Lucas's theorem to the case of p being a power of prime.

References

Lucas's theorem Wikipedia

(Text) CC BY-SA

Contents