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 a paper, .

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

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\left( \binom nm \right) = \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:

:

Therefore the largest power of 2 that divides $\tbinom = 120 = 2^3 \cdot 15$ is .

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( \binom 3 \right) = \dfrac = \dfrac = 3.$

Multinomial coefficient generalization

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

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

See also

* Lucas's theorem

References

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

Theorems in number theory