View source for Lucas's theorem

In [[Number theory|number theory]], '''Lucas's theorem''' expresses the [[Remainder|remainder]] of division of the [[Binomial coefficient|binomial coefficient]] <math>\tbinom{m}{n}</math> by a [[Prime number|prime number]] ''p'' in terms of the [[Radix|base]] ''p'' expansions of the integers ''m'' and ''n''.

Lucas's theorem first appeared in 1878 in papers by [[Biography:Édouard Lucas|Édouard Lucas]].<ref>
*{{cite journal| author=Edouard Lucas |title=Théorie des Fonctions Numériques Simplement Périodiques| jstor=2369308 |journal=[[American Journal of Mathematics]] |year=1878 |volume=1 |issue=2 |pages=184–196 |doi=10.2307/2369308| mr=1505161}} (part 1);
*{{cite journal| author=Edouard Lucas |title=Théorie des Fonctions Numériques Simplement Périodiques| jstor=2369311 |journal=[[American Journal of Mathematics]] |year=1878 |volume=1 |issue=3 |pages=197–240 |doi=10.2307/2369311| mr=1505164}} (part 2);
*{{cite journal| author=Edouard Lucas |title=Théorie des Fonctions Numériques Simplement Périodiques| jstor=2369373 |journal=[[American Journal of Mathematics]] |year=1878 |volume=1 |issue=4 |pages=289–321 |doi=10.2307/2369373| mr=1505176}} (part 3)</ref>

== Statement ==
For non-negative integers ''m'' and ''n'' and a prime ''p'', the following [[Modular arithmetic|congruence relation]] holds:
:<math>\binom{m}{n}\equiv\prod_{i=0}^k\binom{m_i}{n_i}\pmod p,</math>
where
:<math>m=m_kp^k+m_{k-1}p^{k-1}+\cdots +m_1p+m_0,</math>
and
:<math>n=n_kp^k+n_{k-1}p^{k-1}+\cdots +n_1p+n_0</math>
are the base ''p'' expansions of ''m'' and ''n'' respectively.  This uses the convention that <math>\tbinom{m}{n} = 0</math> if ''m''&nbsp;<&nbsp;''n''.

== Proofs ==

There are several ways to prove Lucas's theorem. 

{{Math proof|title=Combinatorial proof|drop=hidden|proof=
Let ''M'' be a set with ''m'' elements, and divide it into ''m<sub>i</sub>'' cycles of length ''p<sup>i</sup>'' 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<sub>p<sup>i</sup></sub>'' 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 <math>\tbinom{m}{n}</math> 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<sub>i</sub>'' cycles of size ''p<sup>i</sup>''.  Thus the number of choices for ''N'' is exactly
<math>\prod_{i=0}^k\binom{m_i}{n_i}\pmod{p}</math>.
}}

{{Math proof|title=Proof based on generating functions|drop=hidden|proof=
This proof is due to Nathan Fine.<ref>{{cite journal|last=Fine|first=Nathan|title=Binomial coefficients modulo a prime|journal=American Mathematical Monthly|year=1947|volume=54|issue=10|pages=589–592|doi=10.2307/2304500|jstor=2304500}}</ref>

If ''p'' is a prime and ''n'' is an integer with 1 ≤ ''n'' ≤ ''p'' − 1, then the numerator of the binomial coefficient
:<math> \binom p n = \frac{p \cdot (p-1) \cdots (p-n+1)}{n \cdot (n-1) \cdots 1} </math>
is divisible by ''p'' but the denominator is not.  Hence ''p'' divides <math>\tbinom{p}{n}</math>.  In terms of ordinary generating functions, this means that
:<math>(1+X)^p\equiv1+X^p\pmod{p}.</math>
Continuing by induction, we have for every nonnegative integer ''i'' that
:<math>(1+X)^{p^i}\equiv1+X^{p^i}\pmod{p}.</math>

Now let ''m'' be a nonnegative integer, and let ''p'' be a prime.  Write ''m'' in base ''p'', so that <math>m=\sum_{i=0}^{k}m_ip^i</math> for some nonnegative integer ''k'' and integers ''m''<sub>''i''</sub> with 0 ≤ ''m''<sub>''i''</sub> ≤ ''p''-1.  Then
:<math>\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}</math>
where in the final product, ''n''<sub>''i''</sub> is the ''i''th digit in the base ''p'' representation of ''n''.  This proves Lucas's theorem.
}}

== Consequences ==
* A binomial coefficient <math>\tbinom{m}{n}</math> 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, <math>\tbinom{m}{n}</math> is [[Parity (mathematics)|odd]] if and only if the binary digits ([[Bit|bit]]s) in the binary expansion of ''n'' are a subset of the bits of ''m''.

== Variations and generalizations ==

* [[Kummer's theorem]] asserts that the largest integer ''k'' such that ''p''<sup>''k''</sup> divides the binomial coefficient <math>\tbinom{m}{n}</math> (or in other words, the [[P-adic valuation|valuation]] of the binomial coefficient  with respect to the prime ''p'') is equal to the number of [[Carry (arithmetic)|carries]] that occur when ''n'' and ''m''&nbsp;−&nbsp;''n'' are added in the [[Positional notation#Base of the numeral system|base ''p'']].

* Generalizations of Lucas's theorem to the case of ''p'' being a prime power are given by Davis and Webb (1990)<ref>{{cite journal |author=Kenneth S. Davis, William A. Webb |title=Lucas' Theorem for Prime Powers |journal=European Journal of Combinatorics |volume=11 |issue=3 |year=1990 |pages=229–233 |doi=10.1016/S0195-6698(13)80122-9|doi-access= }}</ref> and Granville (1997).<ref>{{cite journal |author=[[Biography:Andrew Granville|Andrew Granville]] |title=Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers |journal=Canadian Mathematical Society Conference Proceedings |volume=20 |pages=253–275 |year=1997 |url=http://www.dms.umontreal.ca/%7Eandrew/PDF/BinCoeff.pdf |mr=1483922 |url-status=dead |archiveurl=https://web.archive.org/web/20170202003812/http://www.dms.umontreal.ca/~andrew/PDF/BinCoeff.pdf |archivedate=2017-02-02 }}</ref>

* The ''q''-Lucas theorem is a generalization for the ''q''-binomial coefficients, first proved by J. Désarménien.<ref>{{cite journal |last1=Désarménien |first1=Jacques |title=Un Analogue des Congruences de Kummer pour les q-nombres d'Euler |journal=European Journal of Combinatorics |date=March 1982 |volume=3 |issue=1 |pages=19–28 |doi=10.1016/S0195-6698(82)80005-X|doi-access= }}</ref>

==References==
{{reflist}}

==External links==
*{{PlanetMath|urlname=LucassTheorem|title=Lucas's Theorem}}
*{{cite journal |author=A. Laugier |author2=M. P. Saikia |title=A new proof of Lucas' Theorem |journal=Notes on Number Theory and Discrete Mathematics |volume=18 |year=2012 |issue=4 |pages=1–6 |arxiv=1301.4250 |url=http://nntdm.net/papers/nntdm-18/NNTDM-18-4-01-06.pdf }}
*{{cite arXiv |author=R. Meštrović |title=Lucas' theorem: its generalizations, extensions and applications (1878–2014) |year=2014 |class=math.NT |eprint=1409.3820 }}

[[Category:Articles containing proofs]]
[[Category:Theorems about prime numbers]]

{{Sourceattribution|Lucas's theorem}}