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).

Statement

edit

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.[1]

Examples

edit

To compute the largest power of 2 dividing the binomial coefficient   write m = 3 and nm = 7 in base p = 2 as 3 = 112 and 7 = 1112. Carrying out the addition 112 + 1112 = 10102 in base 2 requires three carries:

  1 1 1    
      1 1 2
+   1 1 1 2
  1 0 1 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. Then

 

Multinomial coefficient generalization

edit

Kummer's theorem can be generalized to multinomial coefficients   as follows:

 

See also

edit

References

edit
  1. ^ Mihet, Dorel (December 2010). "Legendre's and Kummer's Theorems Again". Resonance. 15 (12): 1111–1121.