Lucas's theorem

Last updated January 30, 2023

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ${\tbinom {m}{n}}$ by a prime number p in terms of the base p expansions of the integers m and n.

Statement

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

{\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}+\cdots +m_{1}p+m_{0},

and

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 ${\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 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. Thus in order to compute ${\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 n_i cycles of size pⁱ. Thus the number of choices for N is exactly $\prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}}$ .

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

{\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 ${\tbinom {p}{n}}$ . In terms of ordinary generating functions, this means that

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

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

(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=\sum _{i=0}^{k}m_{i}p^{i}$ for some nonnegative integer k and integers m_i with 0 ≤ m_i ≤ p-1. Then

{\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 _{n_{i}=0}^{m_{i}}{\binom {m_{i}}{n_{i}}}X^{n_{i}p^{i}}\right)\\&=\prod _{i=0}^{k}\left(\sum _{n_{i}=0}^{p-1}{\binom {m_{i}}{n_{i}}}X^{n_{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}}

where in the final product, n_i is the ith digit in the base p representation of n. This proves Lucas's theorem.

Consequences

A binomial coefficient ${\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, ${\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.

Variations and generalizations

Kummer's theorem asserts that the largest integer k such that p^k divides the binomial coefficient ${\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.

Generalizations of Lucas's theorem to the case of p being a prime power are given by Davis and Webb (1990)^[3] and Granville (1997).^[4]

The q-Lucas theorem is a generalization for the q-binomial coefficients, first proved by J. Désarménien.^[5]

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In elementary algebra, the binomial theorem (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial $(x + y) n$ into a sum involving terms of the form $ax b y c$ , where the exponents $b$ and $c$ are nonnegative integers with $b + c = n$ , and the coefficient $a$ of each term is a specific positive integer depending on $n$ and $b$ . For example, for $n = 4$ ,

In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

In mathematics, Pascal's triangle is a triangular array of the binomial coefficients that arises in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in India, Persia, China, Germany, and Italy.

In number theory, Euler's theorem states that, if $n$ and $a$ are coprime positive integers, and $is Euler's totient function, then a raised to the power is congruent to 1 modulo n; that is$

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is a factorization of the integer $15$ , and $(x - 2)(x + 2)$ is a factorization of the polynomial $x 2 - 4$ .

This article collects together a variety of proofs of Fermat's little theorem, which states that

In algebra and number theory, Wilson's theorem states that a natural number n > 1 is a prime number if and only if the product of all the positive integers less than n is one less than a multiple of n. That is, the factorial $satisfies$

In mathematics, the falling factorial is defined as the polynomial

In mathematics, Bertrand's postulate states that for each $there is a prime such that . It was first proven by Chebyshev, and a short but advanced proof was given by Ramanujan.$

In mathematics, the Lucas–Lehmer test (LLT) is a primality test for Mersenne numbers. The test was originally developed by Édouard Lucas in 1876 and subsequently improved by Derrick Henry Lehmer in the 1930s.

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known. It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve.

In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.

In mathematics, the binomial series is a generalization of the polynomial that comes from a binomial formula expression like $for a nonnegative integer . Specifically, the binomial series is the Taylor series for the function centered at, where and . Explicitly,$

In mathematics, Wolstenholme's theorem states that for a prime number $, the congruence$

<span class="mw-page-title-main">Carmichael function</span> Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function $λ (n)$ of a positive integer $n$ is the smallest positive integer $m$ such that

In additive number theory, Fermat's theorem on sums of two squares states that an odd prime p can be expressed as:

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles.

Coppersmith's attack describes a class of cryptographic attacks on the public-key cryptosystem RSA based on the Coppersmith method. Particular applications of the Coppersmith method for attacking RSA include cases when the public exponent e is small or when partial knowledge of a prime factor of the secret key is available.

In mathematics, Kummer's theorem is a formula for the exponent of the highest power of a prime number p that divides a given binomial coefficient. In other words, it gives the p-adic valuation of a binomial coefficient. The theorem is named after Ernst Kummer, who proved it in a paper,.

References

↑
- Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (2): 184–196. doi:10.2307/2369308. JSTOR 2369308. MR 1505161. (part 1);
- Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311. MR 1505164. (part 2);
- Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (4): 289–321. doi:10.2307/2369373. JSTOR 2369373. MR 1505176. (part 3)
↑ Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly. 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500.
↑ 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 .
↑ 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.
↑ 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

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].

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] 
Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (2): 184–196. doi:10.2307/2369308. JSTOR 2369308. MR 1505161. (part 1);
Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311. MR 1505164. (part 2);
Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (4): 289–321. doi:10.2307/2369373. JSTOR 2369373. MR 1505176. (part 3)

[mwbg] Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (2): 184–196. doi:10.2307/2369308. JSTOR 2369308. MR 1505161. (part 1);

[mwfA] Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311. MR 1505164. (part 2);

[mwiw] Edouard Lucas (1878). "Théorie des Fonctions Numériques Simplement Périodiques". American Journal of Mathematics . 1 (4): 289–321. doi:10.2307/2369373. JSTOR 2369373. MR 1505176. (part 3)

[2] Fine, Nathan (1947). "Binomial coefficients modulo a prime". American Mathematical Monthly. 54 (10): 589–592. doi:10.2307/2304500. JSTOR 2304500.

[3] 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 .

[4] 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.

[5] 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 .

[1]

[2]

[3]

[4]

[5]