Lucas's theorem

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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]

Statement[edit]

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.

Consequence[edit]

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

Variations and generalizations[edit]

  • 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.
  • Andrew Granville has given a generalization of Lucas's theorem to the case of p being a power of prime.[3]

References[edit]

  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: 589–592. doi:10.2307/2304500.
  3. ^ 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.

External links[edit]