Kummer's theorem

Kummer's theorem states that for given integers n ≥ m ≥ 0 and a prime number p, the p-adic valuation $\backslash nu\_p\backslash !\backslash tbinom\; n\; m$ of the binomial coefficient $\backslash 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$ expansion of the integer $n$ as $n=n\_0+n\_1p+n\_2p^2+\backslash cdots+n\_rp^r$, and define $S\_p(n):=n\_0+n\_1+\backslash cdots+n\_r$ to be the sum of the base-$p$ digits. Then

: $\backslash nu\_p\backslash !\backslash binom\; nm\; =\; \backslash dfrac\{S\_p(m)\; +\; S\_p(n-m)\; -\; S\_p(n)\}\{p-1\}.$

The theorem can be proved by writing $\backslash tbinom\{n\}\{m\}$ as $\backslash tfrac\{n!\}\{m!\; (n-m)!\}$ and using Legendre's formula.{{Cite journal|last=Mihet|first=Dorel|date=December 2010|title=Legendre's and Kummer's Theorems Again|url=https://www.ias.ac.in/article/fulltext/reso/015/12/1111-1121|journal=Resonance|volume=15|issue=12|pages=1111–1121|doi=10.1007/s12045-010-0123-4 |url-access=subscription}}

To compute the largest power of 2 dividing the binomial coefficient $\backslash tbinom\{10\}\{3\}$ write {{math| m {{=}} 3}} and {{math| n − m {{=}} 7}} in base {{math| p {{=}} 2}} as {{math|3 {{=}} 11₂}} and {{math|7 {{=}} 111₂}}. Carrying out the addition {{math| 11₂ + 111₂ {{=}} 1010₂}} in base 2 requires three carries:

: $\backslash 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 $\backslash tbinom\{10\}\{3\}\; =\; 120\; =\; 2^3\; \backslash 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

: $\backslash nu\_2\backslash !\backslash binom\; \{10\}3\; =\; \backslash dfrac\{S\_2(3)\; +\; S\_2(7)\; -\; S\_2(10)\}\{2\; -\; 1\}\; =\; \backslash dfrac\{2\; +\; 3\; -\; 2\}\{2\; -\; 1\}\; =\; 3.$

Kummer's theorem can be generalized to multinomial coefficients $\backslash tbinom\; n\; \{m\_1,\backslash ldots,m\_k\}\; =\; \backslash tfrac\{n!\}\{m\_1!\backslash cdots\; m\_k!\}$ as follows:

: $\backslash nu\_p\backslash !\backslash binom\; n\; \{m\_1,\backslash ldots,m\_k\}\; =\; \backslash dfrac\{1\}\{p-1\}\; \backslash left(\backslash left(\backslash sum\_\{i=1\}^k\; S\_p(m\_i)\; \backslash right)\; -\; S\_p(n)\; \backslash right).$

• Lucas's theorem

{{reflist}}

• {{cite journal

|last=Kummer

|first=Ernst

|title=Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen

|journal=Journal für die reine und angewandte Mathematik

|year=1852

|volume=1852

|issue=44

|pages=93–146

|doi=10.1515/crll.1852.44.93|url=https://zenodo.org/record/1448864

}}

• {{PlanetMath|urlname=KummersTheorem|title=Kummer's theorem}}

Category:Theorems in number theory