Lucas' theorem

From Wikipedia, the free encyclopedia

For the theorem in complex analysis, see Gauss–Lucas theorem.

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_{k}p^{k}+m_{{k-1}}p^{{k-1}}+\cdots +m_{1}p+m_{0},$

and

$n=n_{k}p^{k}+n_{{k-1}}p^{{k-1}}+\cdots +n_{1}p+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.

Proof

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

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 ${\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 n_i cycles of size pⁱ. Thus the number of choices for N is exactly $\prod _{{i=0}}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}$ .

Here is a proof based on generating functions, due to Nathan Fine.^[2]

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

${\binom pn}={\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}\equiv 1+X^{p}{\text{ mod }}p.$

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

$(1+X)^{{p^{i}}}\equiv 1+X^{{p^{i}}}{\text{ mod }}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_{i}p^{i}$ for some nonnegative integer k and integers m_i with 0 ≤ m_i ≤ p-1. Then

${\begin{aligned}\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_{i}p^{i}}}\right)\\&=\sum _{{n=0}}^{{m}}\left(\prod _{{i=0}}^{{k}}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\text{ mod }}p,\end{aligned}}$

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

Variations and generalizations

The largest integer k such that p^k 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

↑
- 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)
↑ Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly 54: 589–592.
↑ Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers". Canadian Mathematical Society Conference Proceedings 20: 253–275. MR 1483922.

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.