Lucas's 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]

Statement

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.

Proofs

There are several ways to prove Lucas's theorem.

Combinatorial proof

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}}$ .

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 ≤ n ≤ p − 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}\equiv 1+X^{p}{\pmod {p}}.

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

(1+X)^{p^{i}}\equiv 1+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_{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 _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}

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

Consequences

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.
In particular, ${\tbinom {m}{n}}$ is odd if and only if the binary digits (bits) in the binary expansion of n are a subset of the bits of m.

Non-prime moduli

Lucas's theorem can be generalized to give an expression for the remainder when ${\tbinom {m}{n}}$ is divided by a prime power p^k. However, the formulas become more complicated.

If the modulo is the square of a prime p, the following congruence relation holds for all 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, and b ≥ 0.

{\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{r-s})+pb(H_{r-s}-H_{s})){\pmod {p^{2}}},

where $H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}$ is the n^th harmonic number.^[3]

Generalizations of Lucas's theorem for higher prime powers p^k are also given by Davis and Webb (1990)^[4] and Granville (1997).^[5]

Variations and generalizations

Kummer's theorem asserts that 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.

The q-Lucas theorem is a generalization for the q-binomial coefficients, first proved by J. Désarménien.^[6]

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 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500.
^ Rowland, Eric (21 Jun 2020). "Lucas' theorem modulo p²". arXiv:2006.11701 [math.NT].
^ Kenneth S. Davis, William A. Webb (1990). "Lucas' Theorem for Prime Powers". European Journal of Combinatorics. 11 (3): 229–233. doi:10.1016/S0195-6698(13)80122-9.
^ Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers" (PDF). Canadian Mathematical Society Conference Proceedings. 20: 253–275. MR 1483922. Archived from the original (PDF) on 2017-02-02.
^ Désarménien, Jacques (March 1982). "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler". European Journal of Combinatorics. 3 (1): 19–28. doi:10.1016/S0195-6698(82)80005-X.

External links

Lucas's Theorem at PlanetMath.
A. Laugier; M. P. Saikia (2012). "A new proof of Lucas' Theorem" (PDF). Notes on Number Theory and Discrete Mathematics. 18 (4): 1–6. arXiv:1301.4250.
R. Meštrović (2014). "Lucas' theorem: its generalizations, extensions and applications (1878–2014)". arXiv:1409.3820 [math.NT].

[1] 
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)

[2] 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);

[3] 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);

[4] 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)

[2] Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly. 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500.

[3] Rowland, Eric (21 Jun 2020). "Lucas' theorem modulo p²". arXiv:2006.11701 [math.NT].

[4] Kenneth S. Davis, William A. Webb (1990). "Lucas' Theorem for Prime Powers". European Journal of Combinatorics. 11 (3): 229–233. doi:10.1016/S0195-6698(13)80122-9.

[5] Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers" (PDF). Canadian Mathematical Society Conference Proceedings. 20: 253–275. MR 1483922. Archived from the original (PDF) on 2017-02-02.

[6] Désarménien, Jacques (March 1982). "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler". European Journal of Combinatorics. 3 (1): 19–28. doi:10.1016/S0195-6698(82)80005-X.

[1]

[2]

[3]

[4]

[5]

[6]