Kummer's theorem

Short description: 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 ${\nu }_p\left((\genfrac{}{}{0ex}{}{n}{m})\right)$ of the binomial coefficient $(\genfrac{}{}{0ex}{}{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$ expansion of the integer $n$ as $n=n_0+n_{1}p+n_2{p}^2+\cdots +n_r{p}^r$, and define $S_p(n):=n_0+n_1+\cdots +n_r$ to be the sum of the base-$p$ digits. Then

${\nu }_p\left((\genfrac{}{}{0ex}{}{n}{m})\right)=\frac{S_p(m)+S_p(n-m)-S_p(n)}{p-1}.$

The theorem can be proved by writing $(\genfrac{}{}{0ex}{}{n}{m})$ as $\frac{n!}{m!(n-m)!}$ and using Legendre's formula.

Examples

To compute the largest power of 2 dividing the binomial coefficient $(\genfrac{}{}{0ex}{}{10}{3})$ write m = 3 and n − m = 7 in base p = 2 as 3 = 11₂ and 7 = 111₂. Carrying out the addition 11₂ + 111₂ = 1010₂ 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 $(\genfrac{}{}{0ex}{}{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$, $S_2(7)=1+1+1=3$, and $S_2(10)=1+0+1+0=2$ respectively. Then

${\nu }_2\left((\genfrac{}{}{0ex}{}{10}{3})\right)=\frac{S_2(3)+S_2(7)-S_2(10)}{2-1}=\frac{2+3-2}{2-1}=3.$

Multinomial coefficient generalization

Kummer's theorem can be generalized to multinomial coefficients $(\genfrac{}{}{0ex}{}{n}{m_1,\dots ,m_k})=\frac{n!}{m_1!\cdots m_k!}$ as follows:

${\nu }_p\left((\genfrac{}{}{0ex}{}{n}{m_1,\dots ,m_k})\right)=\frac{1}{p-1}\left(\right(\sum _{i=1}^k{S}_p(m_i))-S_p(n)).$

See also

• Lucas's theorem

References

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