Lucas's Theorem

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient $\tbinom$ 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.

Statement

For non-negative integers ''m'' and ''n'' and a prime ''p'', the following congruence relation holds:
:$\binom\equiv\prod_^k\binom\pmod p,$
where
:$m=m_kp^k+m_p^+\cdots +m_1p+m_0,$
and
:$n=n_kp^k+n_p^+\cdots +n_1p+n_0$
are the base ''p'' expansions of ''m'' and ''n'' respectively. This uses the convention that $\tbinom = 0$ if ''m'' < ''n''.

Proofs

There are several ways to prove Lucas's theorem.

Consequences

* A binomial coefficient $\tbinom$ 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$ is odd if and only if the binary digits (bits) 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''^''k'' divides the binomial coefficient $\tbinom$ (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''.

* Generalizations of Lucas's theorem to the case of ''p'' being a prime power are given by Davis and Webb (1990) and Granville (1997).

* The ''q''-Lucas theorem is a generalization for the ''q''-binomial coefficients, first proved by J. Désarménien.

References

External links

*
*
*{{cite arXiv , author=R. Meštrović , title=Lucas' theorem: its generalizations, extensions and applications (1878–2014) , year=2014 , class=math.NT , eprint=1409.3820

Articles containing proofs
Theorems about prime numbers