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

Statement

Kummer's theorem states that for given integers ''n'' ≥ ''m'' ≥ 0 and a prime number ''p'', the ''p''-adic valuation $\nu_p\!\tbinom n m$ of the binomial coefficient $\tbinom$ 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+\cdots+n_rp^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\!\binom nm = \dfrac.$

The theorem can be proved by writing $\tbinom$ as $\tfrac$ and using Legendre's formula.

Examples

To compute the largest power of 2 dividing the binomial coefficient $\tbinom$ write and in base as and . Carrying out the addition in base 2 requires three carries:
: $\begin & _1 & _1 & _1 \\ & & & 1 & 1 \,_2 \\ + & & 1 & 1 & 1 \,_2 \\\hline & 1 & 0 & 1 & 0 \,_2 \end$
Therefore the largest power of 2 that divides $\tbinom = 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\!\binom 3 = \dfrac = \dfrac = 3.$

Multinomial coefficient generalization

Kummer's theorem can be generalized to multinomial coefficients $\tbinom n = \tfrac$ as follows:

: $\nu_p\!\binom n = \dfrac \left(\left(\sum_^k S_p(m_i) \right) - S_p(n) \right).$

See also

* Lucas's theorem

References

*
* {{PlanetMath, urlname=KummersTheorem, title=Kummer's theorem

Theorems in number theory