Lucas's theorem

For a prime p, Lucas's theorem computes a binomial coefficient modulo p as the product of binomial coefficients of the base-p digits of its arguments.

Connect

Binomial coefficient: The number of ways to choose k objects from n distinct objects, written as C(n,k) or \(\binom{n}{k}\). The theorem computes these coefficients modulo a prime.
Sierpiński triangle: A self-similar fractal formed by repeatedly removing central triangles from an equilateral triangle. The pattern of odd entries in Pascal's triangle forms this fractal through Lucas's theorem.
Édouard Lucas: A nineteenth-century French mathematician who worked in number theory and recreational mathematics. Lucas stated the prime-modulus theorem that bears his name.
Generalized Lucas theorem: Extensions of Lucas's digitwise congruence to prime powers or broader coefficient settings. These variants address moduli beyond the prime case stated by the basic theorem.
Base-p representation: A positional numeral representation whose place values are powers of a prime p. The theorem applies the binomial operation separately to each base-p digit.
Binomial coefficient modulo a prime: The residue of a binomial coefficient after division by a prime. The theorem gives this residue directly from the base-prime digits.
Carl Friedrich Gauss: A German mathematician whose work shaped number theory, analysis, geometry, and astronomy. His work on binomial coefficients modulo primes forms part of the theorem's historical setting.
Granville's theorem: A theorem giving binomial coefficients modulo prime powers through digit data and carries. It extends digit-based computation from prime moduli to prime-power moduli.
Congruence: An equivalence relation on integers stating that two numbers have the same remainder upon division by a modulus. Its conclusion is a modular equality, not an equality of ordinary integers.
Nonzero entries in Pascal's triangle: The positions in Pascal's triangle whose binomial coefficients are not divisible by a chosen prime. Lucas's digit test identifies these positions row by row.