Kummer's theorem

Describes the highest power of primes dividing a binomial coefficient

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, (Kummer 1852).

Statement

Kummer's theorem states that for given integers n ≥ m ≥ 0 and a prime number p, the p-adic valuation ν p ( n m ) {\displaystyle \nu _{p}\!{\tbinom {n}{m}}} of the binomial coefficient ( n m ) {\displaystyle {\tbinom {n}{m}}} is equal to the number of carries when m is added to n − m in base p.

An equivalent formation of the theorem is as follows:

Write the base- p {\displaystyle p} expansion of the integer n {\displaystyle n} as n = n 0 + n 1 p + n 2 p 2 + ⋯ + n r p r {\displaystyle n=n_{0}+n_{1}p+n_{2}p^{2}+\cdots +n_{r}p^{r}} , and define S p ( n ) := n 0 + n 1 + ⋯ + n r {\displaystyle S_{p}(n):=n_{0}+n_{1}+\cdots +n_{r}} to be the sum of the base- p {\displaystyle p} digits. Then

ν p ( n m ) = S p ( m ) + S p ( n − m ) − S p ( n ) p − 1 . {\displaystyle \nu _{p}\!{\binom {n}{m}}={\dfrac {S_{p}(m)+S_{p}(n-m)-S_{p}(n)}{p-1}}.}

The theorem can be proved by writing ( n m ) {\displaystyle {\tbinom {n}{m}}} as n ! m ! ( n − m ) ! {\displaystyle {\tfrac {n!}{m!(n-m)!}}} and using Legendre's formula.[1]

Examples

To compute the largest power of 2 dividing the binomial coefficient ( 10 3 ) {\displaystyle {\tbinom {10}{3}}} write m = 3 and n − m = 7 in base p = 2 as 3 = 112 and 7 = 1112. Carrying out the addition 112 + 1112 = 10102 in base 2 requires three carries:

  1 1 1    
      1 1 2
+   1 1 1 2
  1 0 1 0 2

Therefore the largest power of 2 that divides ( 10 3 ) = 120 = 2 3 ⋅ 15 {\displaystyle {\tbinom {10}{3}}=120=2^{3}\cdot 15} is 3.

Alternatively, the form involving sums of digits can be used. The sums of digits of 3, 7, and 10 in base 2 are S 2 ( 3 ) = 1 + 1 = 2 {\displaystyle S_{2}(3)=1+1=2} , S 2 ( 7 ) = 1 + 1 + 1 = 3 {\displaystyle S_{2}(7)=1+1+1=3} , and S 2 ( 10 ) = 1 + 0 + 1 + 0 = 2 {\displaystyle S_{2}(10)=1+0+1+0=2} respectively. Then

ν 2 ( 10 3 ) = S 2 ( 3 ) + S 2 ( 7 ) − S 2 ( 10 ) 2 − 1 = 2 + 3 − 2 2 − 1 = 3. {\displaystyle \nu _{2}\!{\binom {10}{3}}={\dfrac {S_{2}(3)+S_{2}(7)-S_{2}(10)}{2-1}}={\dfrac {2+3-2}{2-1}}=3.}

Multinomial coefficient generalization

Kummer's theorem can be generalized to multinomial coefficients ( n m 1 , … , m k ) = n ! m 1 ! ⋯ m k ! {\displaystyle {\tbinom {n}{m_{1},\ldots ,m_{k}}}={\tfrac {n!}{m_{1}!\cdots m_{k}!}}} as follows:

ν p ( n m 1 , … , m k ) = 1 p − 1 ( − S p ( n ) + ∑ i = 1 k S p ( m i ) ) . {\displaystyle \nu _{p}\!{\binom {n}{m_{1},\ldots ,m_{k}}}={\dfrac {1}{p-1}}\left(-S_{p}(n)+\sum _{i=1}^{k}S_{p}(m_{i})\right).}

See also

  • Lucas's theorem

References

  1. ^ Mihet, Dorel (December 2010). "Legendre's and Kummer's Theorems Again". Resonance. 15 (12): 1111–1121.
  • Kummer, Ernst (1852). "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen". Journal für die reine und angewandte Mathematik. 1852 (44): 93–146. doi:10.1515/crll.1852.44.93.
  • Kummer's theorem at PlanetMath.