Kummer's theorem
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 [math]\displaystyle{ \nu_p\left( \tbinom n m \right) }[/math] of the binomial coefficient [math]\displaystyle{ \tbinom{n}{m} }[/math] 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-[math]\displaystyle{ p }[/math] expansion of the integer [math]\displaystyle{ n }[/math] as [math]\displaystyle{ n=n_0+n_1p+n_2p^2+\cdots+n_rp^r }[/math], and define [math]\displaystyle{ S_p(n):=n_0+n_1+\cdots+n_r }[/math] to be the sum of the base-[math]\displaystyle{ p }[/math] digits. Then
- [math]\displaystyle{ \nu_p\left( \binom nm \right) = \dfrac{S_p(m) + S_p(n-m) - S_p(n)}{p-1}. }[/math]
The theorem can be proved by writing [math]\displaystyle{ \tbinom{n}{m} }[/math] as [math]\displaystyle{ \tfrac{n!}{m! (n-m)!} }[/math] and using Legendre's formula.[1]
Examples
To compute the largest power of 2 dividing the binomial coefficient [math]\displaystyle{ \tbinom{10}{3} }[/math] 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 [math]\displaystyle{ \tbinom{10}{3} = 120 = 2^3 \cdot 15 }[/math] 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 [math]\displaystyle{ S_2(3) = 1 + 1 = 2 }[/math], [math]\displaystyle{ S_2(7) = 1 + 1 + 1 = 3 }[/math], and [math]\displaystyle{ S_2(10) = 1 + 0 + 1 + 0 = 2 }[/math] respectively. Then
- [math]\displaystyle{ \nu_2\left( \binom {10}3 \right) = \dfrac{S_2(3) + S_2(7) - S_2(10)}{2 - 1} = \dfrac{2 + 3 - 2}{2 - 1} = 3. }[/math]
Multinomial coefficient generalization
Kummer's theorem can be generalized to multinomial coefficients [math]\displaystyle{ \tbinom n {m_1,\ldots,m_k} = \tfrac{n!}{m_1!\cdots m_k!} }[/math] as follows:
- [math]\displaystyle{ \nu_p\left( \binom n {m_1,\ldots,m_k} \right) = \dfrac{1}{p-1} \left( \Bigl( \sum_{i=1}^k S_p(m_i) \Bigr) - S_p(n)\right). }[/math]
See also
References
- ↑ Mihet, Dorel (December 2010). "Legendre’s and Kummer’s Theorems Again". Resonance 15 (12): 1111-1121. https://www.ias.ac.in/article/fulltext/reso/015/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. https://zenodo.org/record/1448864.
- Kummer's theorem at PlanetMath.org.
 |  |
