Kummer's theorem

In mathematics, Kummer's theorem for binomial coefficients gives the p-adic valuation of a binomial coefficient, i.e., the exponent of the highest power of a prime number p dividing this binomial coefficient. The theorem is named after Ernst Kummer, who proved it in the 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({\tbinom {n}{m}}\right)$ is equal to the number of carries when m is added to n − m in base p.

It can be proved by writing ${\tbinom {n}{m}}$ as ${\tfrac {n!}{m!(n-m)!}}$ and using Legendre's formula.

Multinomial coefficient generalization

Kummer's theorem may be generalized to multinomial coefficients ${\tbinom {n}{m_{1},\ldots ,m_{k}}}:={\tfrac {n!}{m_{1}!\cdots m_{k}!}}$ as follows: Write the base- $p$ expansion of an 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({\dbinom {n}{m_{1},\ldots ,m_{k}}}\right)={\dfrac {1}{p-1}}\left(\sum _{i=1}^{k}S_{p}(m_{i})-S_{p}(n)\right)$ .

References

Kummer, Ernst (1852). "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen". Journal für die reine und angewandte Mathematik. 44: 93–146. doi:10.1515/crll.1852.44.93.
Kummer's theorem at PlanetMath.org.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

Kummer's theorem

Statement

Multinomial coefficient generalization

See also

References