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 the paper.

Statement

Kummer's theorem states that for given integers n ≥ m ≥ 0 and a prime number p, the p-adic valuation is equal to the number of carries when m is added to n − m in base p.
It can be proved by writing as and using Legendre's formula.

Examples

To compute the largest power of 2 dividing the binomial coefficient write and in base as and. Carrying out the addition in base 2 requires three carries. And the largest power of 2 that divides is.

Multinomial coefficient generalization

Kummer's theorem may be generalized to multinomial coefficients as follows: Write the base- expansion of an integer as, and define to be the sum of the base- digits. Then