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 1852 .
Kummer's theorem states that for given integers n âÂÂ¥ m âÂÂ¥ 0 and a prime number p, the p-adic valuation 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 as , and define to be the sum of the base- digits. Then
The theorem can be proved by writing as and using Legendre's formula.
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:
Therefore the largest power of 2 that divides 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 , , and respectively. Then
Kummer's theorem can be generalized to multinomial coefficients as follows: