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, (Kummer 1852).
Kummer's theorem states that for given integers n ≥ m ≥ 0 and a prime number p, the p-adic valuation
ν
(
)
{\displaystyle \nu _{p}\!
of the binomial coefficient
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-
expansion of the integer
, and define
to be the sum of the base-
digits.
Then The theorem can be proved by writing
{\displaystyle {\tfrac {n!}{m!(n-m)!}}}
and using Legendre's formula.
[1] To compute the largest power of 2 dividing the binomial coefficient
write m = 3 and n − m = 7 in base p = 2 as 3 = 112 and 7 = 1112.
Carrying out the addition 112 + 1112 = 10102 in base 2 requires three carries: Therefore the largest power of 2 that divides
Alternatively, the form involving sums of digits can be used.
The sums of digits of 3, 7, and 10 in base 2 are
Then Kummer's theorem can be generalized to multinomial coefficients