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 Edouard 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
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
Entity-backed identity for the statement-form enum value this theorem already carries, resolved to a mathematics concept by an explicit value-to-entity map (phase 3 bucket conversion, docs\design_entity_backed_browse_buckets_20260928.md). The statement-form fact itself stays on the theorem unchanged.
In Branch
Source Lucas' Theorem (Wikipedia)
Proved By
Source Lucas' Theorem (Wikipedia)
Sources
1. Lucas' Theorem (Wikipedia)
Wikimedia FoundationLead paragraph, first sentence
In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient by a prime number p in terms of the base p expansions of the integers m and n.
Lead paragraph, second sentence
Lucas's theorem first appeared in 1878 in papers by Edouard Lucas.
- In Branch: Number Theory, Lead sentence
Proved By: Edouard 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.