Lucas' theorem

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

<templatestyles src="Module:Hatnote/styles.css"></templatestyles>

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

Lucas's theorem first appeared in 1878 in papers by Édouard Lucas.[1]

Formulation

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

\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,

where

m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,

and

n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0

are the base p expansions of m and n respectively. This uses the convention that \tbinom{m}{n} = 0 if m < n.

Consequence

  • A binomial coefficient \tbinom{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 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 \tbinom{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 ni cycles of size pi. Thus the number of choices for N is exactly \prod_{i=0}^k\binom{m_i}{n_i}\pmod{p}.

Proof based on generating functions

This proof is due to Nathan Fine.[2]

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

 \binom p n = \frac{p \cdot (p-1) \cdots (p-n+1)}{n \cdot (n-1) \cdots 1}

is divisible by p but the denominator is not. Hence p divides \tbinom{p}{n}. In terms of ordinary generating functions, this means that

(1+X)^p\equiv1+X^p\pmod{p}.

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

(1+X)^{p^i}\equiv1+X^{p^i}\pmod{p}.

Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that m=\sum_{i=0}^{k}m_ip^i for some nonnegative integer k and integers mi with 0 ≤ mip-1. Then

\begin{align}
\sum_{n=0}^{m}\binom{m}{n}X^n &
=(1+X)^m=\prod_{i=0}^{k}\left((1+X)^{p^i}\right)^{m_i}\\
 & \equiv \prod_{i=0}^{k}\left(1+X^{p^i}\right)^{m_i}
=\prod_{i=0}^{k}\left(\sum_{n_i=0}^{m_i}\binom{m_i}{n_i}X^{n_ip^i}\right)\\
 & =\prod_{i=0}^{k}\left(\sum_{n_i=0}^{p-1}\binom{m_i}{n_i}X^{n_ip^i}\right)=\sum_{n=0}^{m}\left(\prod_{i=0}^{k}\binom{m_i}{n_i}\right)X^n
\pmod{p},
\end{align}

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

Variations and generalizations

  • The largest integer k such that pk divides the binomial coefficient \tbinom{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. (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.[3]

References

<templatestyles src="Reflist/styles.css" />

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />

External links

  • Lua error in package.lua at line 80: module 'strict' not found. (part 1);
  • Lua error in package.lua at line 80: module 'strict' not found. (part 2);
  • Lua error in package.lua at line 80: module 'strict' not found. (part 3)
  • Lua error in package.lua at line 80: module 'strict' not found.
  • Lua error in package.lua at line 80: module 'strict' not found.