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, . 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. 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 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: {| cellpadding=5 style="border:none" | || 1 || 1 || 1 || || || |- | || || || 1 || 1 2 |- | + || || 1 || 1 || 1 2 |- | style='border-top: 1px solid' | | style='border-top: 1px solid' | 1 | style='border-top: 1px solid' | 0 | style='border-top: 1px solid' | 1 | style='border-top: 1px solid' | 0 2 |} 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.