Kummer's theorem

In mathematics, Kummer's theorem on binomial coeffients gives the highest power of a prime number p dividing a binomial coefficient. In particular, it asserts that given integers n ≥ m ≥ 0 and a prime number p, the maximum integer k such that p^k divides the binomial coefficient $\tbinom n m$ is equal to the number of carries when m is added to n − m in base p.

The theorem is named after Ernst Kummer, who proved it in the paper Kummer (1852). It can be proved by writing $\tbinom{n}{m}$ as $\tfrac{n!}{m! (n-m)!}$ and using Legendre's formula.

See also

• Lucas's theorem on binomial coefficients

External links

• Kummer's theorem at PlanetMath.org.

References

• Kummer, Ernst (1852). "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen". Journal für die reine und angewandte Mathematik 44: 93–146. doi:10.1515/crll.1852.44.93.