Kummer's theorem

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 .

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 .

Statement

Kummer's theorem states that for given integers n ≥ m ≥ 0 and a prime number p, the p-adic valuation \nu_p\!\tbinom n m of the binomial coefficient \tbinom{n}{m} 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- p expansion of the integer n as n=n_0+n_1p+n_2p^2+\cdots+n_rp^r , and define S_p(n):=n_0+n_1+\cdots+n_r to be the sum of the base- p digits. Then \nu_p\!\binom nm = \dfrac{S_p(m) + S_p(n-m) - S_p(n)}{p-1}.

The theorem can be proved by writing \tbinom{n}{m} as \tfrac{n!}{m! (n-m)!} and using Legendre's formula. Therefore the largest power of 2 that divides \tbinom{10}{3} = 120 = 2^3 \cdot 15 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 S_2(3) = 1 + 1 = 2 , S_2(7) = 1 + 1 + 1 = 3 , and S_2(10) = 1 + 0 + 1 + 0 = 2 respectively. Then \nu_2\!\binom {10}3 = \dfrac{S_2(3) + S_2(7) - S_2(10)}{2 - 1} = \dfrac{2 + 3 - 2}{2 - 1} = 3.

Multinomial coefficient generalization

Kummer's theorem can be generalized to multinomial coefficients \tbinom n {m_1,\ldots,m_k} = \tfrac{n!}{m_1!\cdots m_k!} as follows: \nu_p\!\binom n {m_1,\ldots,m_k} = \dfrac{1}{p-1} \left(\left(\sum_{i=1}^k S_p(m_i) \right) - S_p(n) \right).

See also

Lucas's theorem

Text derived from https://en.wikipedia.org/w/index.php?oldid=1364659886 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001364659886 · captured 1784311780.0 · version history

Cite this page as: encyclopegia.org, “Kummer's theorem”, snapshot enwiki-001364659886. https://encyclopegia.org/a/kummer-s-theorem

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.