Kummer's theorem

Template:Short description 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, Template:Harv.

Statement

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

ν_{p} (\binom{n}{m}) = \frac{S_{p} (m) + S_{p} (n - m) - S_{p} (n)}{p - 1} .

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

Examples

To compute the largest power of 2 dividing the binomial coefficient $(\binom{10}{3})$ write Template:Math and Template:Math in base Template:Math as Template:Math and Template:Math. Carrying out the addition Template:Math in base 2 requires three carries:

\begin{matrix} _{1} & _{1} & _{1} \\ 1 & 1_{2} \\ + & 1 & 1 & 1_{2} \\ 1 & 0 & 1 & 0_{2} \end{matrix}

Therefore the largest power of 2 that divides $(\binom{10}{3}) = 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

ν_{2} (\binom{10}{3}) = \frac{S_{2} (3) + S_{2} (7) - S_{2} (10)}{2 - 1} = \frac{2 + 3 - 2}{2 - 1} = 3 .

Multinomial coefficient generalization

Kummer's theorem can be generalized to multinomial coefficients $(\binom{n}{m_{1}, \dots, m_{k}}) = \frac{n!}{m_{1}! \dots m_{k}!}$ as follows:

ν_{p} (\binom{n}{m_{1}, \dots, m_{k}}) = \frac{1}{p - 1} (\sum_{i = 1}^{k} S_{p} (m_{i}) - S_{p} (n)) .

References

Template:Reflist

↑ Template:Cite journal

[1] Template:Cite journal

[1]

Kummer's theorem

Contents

Statement

Examples

Multinomial coefficient generalization

See also

References

Navigation menu

Kummer's theorem

Statement

Examples

Multinomial coefficient generalization

See also

References

Navigation menu

Search