Lucas's theorem explained

\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 ^{k\binom{m} _{i}{n} _{i}\pmod} p, wherem = m ^{k + m} _{k -1} p ^{k-1} + … + m _{1p+m} _{0,} andn = n ^{k + n} _{k -1} p ^{k-1} + … + 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.

Proofs

There are several ways to prove 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 mn 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 ab\binom rs( 1+ pa(H _{r-H} _{r-s} ) + pb(H _{r-s} - H ^{2 },} _{s))\pmod{p} where H _{n=1+\tfrac12+\tfrac13+ … +\tfrac1n} is the n^th harmonic number.^[2]

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

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.^[5]

External links

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

Notes and References

1. • Edouard Lucas . Théorie des Fonctions Numériques Simplement Périodiques. 2369308 . . 1878 . 1 . 2 . 184–196 . 10.2307/2369308. 1505161. (part 1);
   • Edouard Lucas . Théorie des Fonctions Numériques Simplement Périodiques. 2369311 . . 1878 . 1 . 3 . 197–240 . 10.2307/2369311. 1505164. (part 2);
   • Edouard Lucas . Théorie des Fonctions Numériques Simplement Périodiques. 2369373 . . 1878 . 1 . 4 . 289–321 . 10.2307/2369373. 1505176. (part 3)
2. Rowland . Eric . 21 Jun 2020 . Lucas' theorem modulo p² . 2006.11701 . math.NT.
3. Kenneth S. Davis, William A. Webb . Lucas' Theorem for Prime Powers . European Journal of Combinatorics . 11 . 3 . 1990 . 229–233 . 10.1016/S0195-6698(13)80122-9.
4. . Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers . Canadian Mathematical Society Conference Proceedings . 20 . 253–275 . 1997 . 1483922 . dead . https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf . 2017-02-02 .
5. Désarménien . Jacques . Un Analogue des Congruences de Kummer pour les q-nombres d'Euler . European Journal of Combinatorics . March 1982 . 3 . 1 . 19–28 . 10.1016/S0195-6698(82)80005-X.