Lucas' theorem

From Groupprops
Jump to: navigation, search

Statement

Suppose a and b are nonnegative integers and p is a prime number. Suppose a = a_0 + a_1p + a_2p^2 + \dots + a_rp^r and b = b_0 + b_1p + b_2p^2 + \dots + b_sp^s are the expressions of a and b in base p, so that each a_i, b_j is in the set \{ 0,1,2,\dots,p-1 \}. if r < s, define a_i = 0 for r < i \le s. Then, we have:

\binom{a}{b} \equiv \prod_{i=0}^s \binom{a_i}{b_i} \pmod p

By convention, \binom{x}{y} = 0 if x = 0 or if y > x.

In particular, we have the following: If a is a power of p and b < a, then \binom{a}{b} is relatively prime to p. For more on this special case and alternative proofs of it, see Lucas' theorem prime power case.