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 1852 (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 {\displaystyle {\begin{array}{ccccc}&_{1}&_{1}&_{1}\\&&&1&1\,_{2}\\+&&1&1&1\,_{2}\\\hline &1&0&1&0\,_{2}\end{array}}}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 ( ∑ i = 1 k S p ( m i ) − S p ( n ) ) . {\displaystyle \nu _{p}\!{\binom {n}{m_{1},\ldots ,m_{k}}}={\dfrac {1}{p-1}}\left(\sum _{i=1}^{k}S_{p}(m_{i})-S_{p}(n)\right).}See also
- 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.
References
Mihet, Dorel (December 2010). "Legendre's and Kummer's Theorems Again". Resonance. 15 (12): 1111–1121. doi:10.1007/s12045-010-0123-4. https://www.ias.ac.in/article/fulltext/reso/015/12/1111-1121 ↩