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 formula_1 is equal to the number of carries when "m" is added to "n" − "m" in base "p". It can be proved by  writing formula_2 as formula_3 and using Legendre's formula. Examples. To compute the largest power of 2 dividing the binomial coefficient formula_4 write and in base as and . Carrying out the addition in base 2 requires three carries. And the largest power of 2 that divides formula_5 is . Multinomial coefficient generalization. Kummer's theorem can be generalized to multinomial coefficients formula_6 as follows: Write the base-formula_7 expansion of the integer formula_8 as formula_9, and define formula_10 to be the sum of the base-formula_7 digits. Then