Lucas' Theorem gives a way to compute a binomial coefficient modulo a prime number by expressing both of its arguments in base p and multiplying together the binomial coefficients of their corresponding digits, each reduced modulo p. Named for Édouard Lucas, it is a standard tool of combinatorial number theory for determining the modular behavior of binomial coefficients without computing them directly.
Facts
StatementFor non-negative integers m and n and a prime p, the binomial coefficient of m and n modulo p equals the product, over each digit position in the base p representations of m and n, of the binomial coefficient of the corresponding pair of digits, each reduced modulo p. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Lucas' Theorem (Wikipedia)
Proved By
Source Lucas' Theorem (Wikipedia)
Sources
1. Lucas' Theorem (Wikipedia)
Wikimedia FoundationLead section
Lucas's theorem first appeared in 1878 in papers by Édouard Lucas.
- In Branch: Number Theory, Lead sentence
Proved By: Édouard Lucas, Lead paragraph
In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.