To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Lucas's theorem

From Wikipedia, the free encyclopedia

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]

YouTube Encyclopedic

  • 1/5
    Views:
    582
    1 528
    519
    1 024
    7 866
  • Learn in 5 Minutes: Modular Combination Functions (Lucas's Theorem)
  • Number Theory: Lucas Theorem
  • How do the roots of a polynomial relate to the roots of its derivative? - Complex Analysis
  • CMU Discrete Mathematics 2/24
  • L15 : Binomial Coefficient using Modulo inverse | Number Theory Course

Transcription

Statement

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.

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 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. Thus in order to compute 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 pi. 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 ≤ np − 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 ≤ mip-1. Then

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

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

References

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

External links

This page was last edited on 18 August 2023, at 09:58
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.