Lucas' theorem: its generalizations, extensions and applications (1878--2014)

Abstract

In 1878 É. Lucas proved a remarkable result which provides a simple way to compute the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ modulo a prime $p$ in terms of the binomial coefficients of the base-$p$ digits of $n$ and $m$: {\it If $p$ is a prime, $n=n_0+n_{1}p+\cdots +n_s{p}^s$ and $m=m_0+m_{1}p+\cdots +m_s{p}^s$ are the $p$-adic expansions of nonnegative integers $n$ and $m$, then \begin{equation*} {n\choose m}\equiv \prod_{i=0}^{s}{n_i\choose m_i}\pmod{p}. \end{equation*}} The above congruence, the so-called {\it Lucas' theorem} (or {\it Theorem of Lucas}), plays an important role in Number Theory and Combinatorics. In this article, consisting of six sections, we provide a historical survey of Lucas type congruences, generalizations of Lucas' theorem modulo prime powers, Lucas like theorems for some generalized binomial coefficients, and some their applications. In Section 1 we present the fundamental congruences modulo a prime including the famous Lucas' theorem. In Section 2 we mention several known proofs and some consequences of Lucas' theorem. In Section 3 we present a number of extensions and variations of Lucas' theorem modulo prime powers. In Section 4 we consider the notions of the Lucas property and the double Lucas property, where we also present numerous integer sequences satisfying one of these properties or a certain Lucas type congruence. In Section 5 we collect several known Lucas type congruences for some generalized binomial coefficients. In particular, this concerns the Fibonomial coefficients, the Lucas $u$-nomial coefficients, the Gaussian $q$-nomial coefficients and their generalizations. Finally, some applications of Lucas' theorem in Number Theory and Combinatorics are given in Section 6.

51 pages; survey article on Lucas type congruences closely related to Lucas' theorem

References in corpus (10)

• Bernoulli Numbers, Wolstenholme's Theorem, and p^5 Variations of Lucas' Theorem
• Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862--2012)
• Dwork Congruences and reflexive Polytopes
• Congruences for Wolstenholme primes
• A Simple Number Theoretic Result
• The number of nonzero binomial coefficients modulo p^alpha
• Variations of Lucas' Theorem Modulo Prime Powers
• A new proof of Lucas' Theorem
• Lucas Type Theorem Modulo Prime Powers
• On divisibility of sums of Apery polynomials

Cited by in corpus (5)

• On some discrete random variables arising from recent study on statistical analysis of compressive sensing
• Several generalizations and variations of Chu-Vandermonde identity
• Algebraic independence of $G$-functions and congruences "à la Lucas"
• Congruences for Catalan-Larcombe-French numbers
• On binomial coefficients modulo squares of primes