Kummer's theorem

Kummer's theorem states that for given integers n ≥ m ≥ 0 and a prime number p, the p-adic valuation ${\displaystyle \nu _{p}\left({\tbinom {n}{m}}\right)}$ of the binomial coefficient ${\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-${\displaystyle p}$ expansion of the integer ${\displaystyle n}$ as ${\displaystyle n=n_{0}+n_{1}p+n_{2}p^{2}+\cdots +n_{r}p^{r}}$, and define ${\displaystyle S_{p}(n):=n_{0}+n_{1}+\cdots +n_{r}}$ to be the sum of the base-${\displaystyle p}$ digits. Then

${\displaystyle \nu _{p}\left({\binom {n}{m}}\right)={\dfrac {S_{p}(m)+S_{p}(n-m)-S_{p}(n)}{p-1}}.}$

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

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

${\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).}$

• Lucas's theorem

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