Top Qs
Timeline
Chat
Perspective
Lucas's theorem
Number theory theorem From Wikipedia, the free encyclopedia
Remove ads
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.
Lucas's theorem first appeared in 1878 in papers by Édouard Lucas.[1]
Remove ads
Statement
Summarize
Perspective
For non-negative integers m and n and a prime p, the following congruence relation holds:
where
and
are the base p expansions of m and n respectively. This uses the convention that if m < n.
Remove ads
Proofs
Summarize
Perspective
There are several ways to prove Lucas's theorem.
Combinatorial proof
Let M be a set with m elements, and divide it into mi cycles of length pi for the various values of i. Then each of these cycles can be rotated separately, so that a group G which is the Cartesian product of cyclic groups Cpi acts on M. It thus also acts on subsets N of size n. Since the number of elements in G is a power of p, the same is true of any of its orbits. Hence, modulo p equals the number of sets N whose orbit is of size 1, i.e., the number of fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. This means that N must have exactly ni cycles of size pi for each i, for the same reason that the integer n has a unique representation in base p. Thus the number of choices for N is exactly .
Proof based on generating functions
This proof is due to Nathan Fine.[2]
If p is a prime and n is an integer with 1 ≤ n ≤ p − 1, then the numerator of the binomial coefficient
is divisible by p but the denominator is not. Hence p divides . In terms of ordinary generating functions, this means that
Continuing by induction, we have for every nonnegative integer i that
Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that for some nonnegative integer k and integers mi with 0 ≤ mi ≤ p − 1. Then
as the representation of n in base p is unique and in the final product, ni is the ith digit in the base p representation of n. This proves Lucas's theorem.
Remove ads
Consequences
- A binomial coefficient 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, is odd if and only if the binary digits (bits) in the binary expansion of n are a subset of the bits of m.
Non-prime modulo
Summarize
Perspective
Lucas's theorem can be generalized to give an expression for the remainder when is divided by a prime power pk. However, the formulas become more complicated.
If the modulo is the square of a prime p, the following congruence relation holds for all 0 ≤ s ≤ r ≤ p − 1, a ≥ 0, and b ≥ 0.
where is the nth harmonic number.[3]
Generalizations of Lucas's theorem for higher prime powers pk are also given by Davis and Webb (1990)[4] and Granville (1997).[5]
Remove ads
Variations and generalizations
- Kummer's theorem asserts that the largest integer k such that pk divides the binomial coefficient (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.
- The q-Lucas theorem is a generalization for the q-binomial coefficients, first proved by J. Désarménien.[6]
Remove ads
References
External links
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads