Misplaced Pages

Lucas's theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Number theory theorem For the theorem in complex analysis, see Gauss–Lucas theorem.

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} 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.

Statement

For non-negative integers m and n and a prime p, the following congruence relation holds:

( m n ) ≡ ∏ i = 0 k ( m i n i ) ( mod p ) , {\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}

where

m = m k p k + m k − 1 p k − 1 + ⋯ + m 1 p + m 0 , {\displaystyle m=m_{k}p^{k}+m_{k-1}p^{k-1}+\cdots +m_{1}p+m_{0},}

and

n = n k p k + n k − 1 p k − 1 + ⋯ + n 1 p + n 0 {\displaystyle n=n_{k}p^{k}+n_{k-1}p^{k-1}+\cdots +n_{1}p+n_{0}}

are the base p expansions of m and n respectively. This uses the convention that ( m n ) = 0 {\displaystyle {\tbinom {m}{n}}=0} if m < n.

Proofs

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 p 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 Cp 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. Thus in order to compute ( m n ) {\displaystyle {\tbinom {m}{n}}} modulo p, we only need to consider fixed points of this group action. The fixed points are those subsets N that are a union of some of the cycles. More precisely one can show by induction on k-i, that N must have exactly ni cycles of size p. Thus the number of choices for N is exactly ∏ i = 0 k ( m i n i ) ( mod p ) {\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}} .

Proof based on generating functions

This proof is due to Nathan Fine.

If p is a prime and n is an integer with 1 ≤ n ≤ p − 1, then the numerator of the binomial coefficient

( p n ) = p ⋅ ( p − 1 ) ⋯ ( p − n + 1 ) n ⋅ ( n − 1 ) ⋯ 1 {\displaystyle {\binom {p}{n}}={\frac {p\cdot (p-1)\cdots (p-n+1)}{n\cdot (n-1)\cdots 1}}}

is divisible by p but the denominator is not. Hence p divides ( p n ) {\displaystyle {\tbinom {p}{n}}} . In terms of ordinary generating functions, this means that

( 1 + X ) p ≡ 1 + X p ( mod p ) . {\displaystyle (1+X)^{p}\equiv 1+X^{p}{\pmod {p}}.}

Continuing by induction, we have for every nonnegative integer i that

( 1 + X ) p i ≡ 1 + X p i ( mod p ) . {\displaystyle (1+X)^{p^{i}}\equiv 1+X^{p^{i}}{\pmod {p}}.}

Now let m be a nonnegative integer, and let p be a prime. Write m in base p, so that m = ∑ i = 0 k m i p i {\displaystyle m=\sum _{i=0}^{k}m_{i}p^{i}} for some nonnegative integer k and integers mi with 0 ≤ mi ≤ p-1. Then

∑ n = 0 m ( m n ) X n = ( 1 + X ) m = ∏ i = 0 k ( ( 1 + X ) p i ) m i ≡ ∏ i = 0 k ( 1 + X p i ) m i = ∏ i = 0 k ( ∑ j i = 0 m i ( m i j i ) X j i p i ) = ∏ i = 0 k ( ∑ j i = 0 p − 1 ( m i j i ) X j i p i ) = ∑ n = 0 m ( ∏ i = 0 k ( m i n i ) ) X n ( mod p ) , {\displaystyle {\begin{aligned}\sum _{n=0}^{m}{\binom {m}{n}}X^{n}&=(1+X)^{m}=\prod _{i=0}^{k}\left((1+X)^{p^{i}}\right)^{m_{i}}\\&\equiv \prod _{i=0}^{k}\left(1+X^{p^{i}}\right)^{m_{i}}=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{m_{i}}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{j_{i}=0}^{p-1}{\binom {m_{i}}{j_{i}}}X^{j_{i}p^{i}}\right)\\&=\sum _{n=0}^{m}\left(\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}\right)X^{n}{\pmod {p}},\end{aligned}}}

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.

Consequences

  • A binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} 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, ( m n ) {\displaystyle {\tbinom {m}{n}}} 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 moduli

Lucas's theorem can be generalized to give an expression for the remainder when ( m n ) {\displaystyle {\tbinom {m}{n}}} is divided by a prime power p. 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.

( p a + r p b + s ) ≡ ( a b ) ( r s ) ( 1 + p a ( H r − H r − s ) + p b ( H r − s − H s ) ) ( mod p 2 ) , {\displaystyle {\binom {pa+r}{pb+s}}\equiv {\binom {a}{b}}{\binom {r}{s}}(1+pa(H_{r}-H_{r-s})+pb(H_{r-s}-H_{s})){\pmod {p^{2}}},}

where H n = 1 + 1 2 + 1 3 + ⋯ + 1 n {\displaystyle H_{n}=1+{\tfrac {1}{2}}+{\tfrac {1}{3}}+\cdots +{\tfrac {1}{n}}} is the n harmonic number.

Generalizations of Lucas's theorem for higher prime powers p are also given by Davis and Webb (1990) and Granville (1997).

Variations and generalizations

  • Kummer's theorem asserts that the largest integer k such that p divides the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} (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.

References

  2. Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly. 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500.
  3. Rowland, Eric (21 Jun 2020). "Lucas' theorem modulo p". arXiv:2006.11701 .
  4. Kenneth S. Davis, William A. Webb (1990). "Lucas' Theorem for Prime Powers". European Journal of Combinatorics. 11 (3): 229–233. doi:10.1016/S0195-6698(13)80122-9.
  5. Andrew Granville (1997). "Arithmetic Properties of Binomial Coefficients I: Binomial coefficients modulo prime powers" (PDF). Canadian Mathematical Society Conference Proceedings. 20: 253–275. MR 1483922. Archived from the original (PDF) on 2017-02-02.
  6. Désarménien, Jacques (March 1982). "Un Analogue des Congruences de Kummer pour les q-nombres d'Euler". European Journal of Combinatorics. 3 (1): 19–28. doi:10.1016/S0195-6698(82)80005-X.

External links

Category: