Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://en.wikipedia.org/wiki/Lucas'_theorem below:

Lucas's theorem - Wikipedia

From Wikipedia, the free encyclopedia

Number theory 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.^[1]

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.

There are several ways to prove Lucas's theorem.

Let M be a set with m elements, and divide it into m_i 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 C_pⁱ 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, ( m n ) {\displaystyle {\tbinom {m}{n}}} 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 n_i cycles of size pⁱ 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 ∏ i = 0 k ( m i n i ) ( mod p ) {\displaystyle \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}} .

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

( 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 m_i with 0 ≤ m_i ≤ 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, n_i is the ith digit in the base p representation of n. This proves Lucas's theorem.

One consequence of Lucas's theorem is that the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} is divisible by the prime p if and only if at least one of the digits of the base-p representation 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.

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^k. 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 nth harmonic number.^[3] Generalizations of Lucas's theorem for higher prime powers p^k are also given by Davis and Webb (1990)^[4] and Granville (1997).^[5]

Kummer's theorem asserts that the largest integer k such that p^k 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.

There is a generalization of Lucas's theorem for the q-binomial coefficients. It asserts that if a, b, r, s, k are integers, where 0 ≤ b, s < k, then [ k a + b k r + s ] q ≡ ( a r ) [ b s ] q mod Φ k , {\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}\equiv {\binom {a}{r}}{\begin{bmatrix}b\\s\end{bmatrix}}_{q}\mod {\Phi _{k}},} where ⁠ [ k a + b k r + s ] q {\displaystyle {\begin{bmatrix}ka+b\\kr+s\end{bmatrix}}_{q}} ⁠ and ⁠ [ b s ] q {\displaystyle {\begin{bmatrix}b\\s\end{bmatrix}}_{q}} ⁠ are q-binomial coefficients, ( a r ) {\displaystyle {\binom {a}{r}}} is a usual binomial coefficient, and ⁠ Φ k {\displaystyle \Phi _{k}} ⁠ is the kth cyclotomic polynomial (in the variable q).^[6]

• Lucas's Theorem at PlanetMath.
• A. Laugier; M. P. Saikia (2012). "A new proof of Lucas' Theorem" (PDF). Notes on Number Theory and Discrete Mathematics. 18 (4): 1–6. arXiv:1301.4250.
• R. Meštrović (2014). "Lucas' theorem: its generalizations, extensions and applications (1878–2014)". arXiv:1409.3820 [math.NT].

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4