Kummer's theorem

Last updated January 19, 2025

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

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_{1}p+n_{2}p^{2}+\cdots +n_{r}p^{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 {n}{m}}={\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.^[1]

Examples

To compute the largest power of 2 dividing the binomial coefficient ${\tbinom {10}{3}}$ write $m = 3$ and $n - m = 7$ in base $p = 2$ as $3 = 11 2$ and $7 = 111 2$ . Carrying out the addition $112 + 111 2 = 1010 2$ in base 2 requires three carries:

{\begin{array}{ccccc}&_{1}&_{1}&_{1}\\&&&1&1\,_{2}\\+&&1&1&1\,_{2}\\\hline &1&0&1&0\,_{2}\end{array}}

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(n-S_{p}(n)-\sum _{i=1}^{k}\left(m_{i}-S_{p}(m_{i})\right)\right).

Related Research Articles

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In elementary algebra, the binomial theorem describes the algebraic expansion of powers of a binomial. According to the theorem, the power ⁠ $⁠$ expands into a polynomial with terms of the form ⁠ $⁠$ , where the exponents ⁠ $⁠$ and ⁠ $⁠$ are nonnegative integers satisfying ⁠ $⁠$ and the coefficient ⁠ $⁠$ of each term is a specific positive integer depending on ⁠ $⁠$ and ⁠ $⁠$ . For example, for ⁠ $⁠$ ,

In mathematics, the Bernoulli numbers $B n$ are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in the Taylor series expansions of the tangent and hyperbolic tangent functions, in Faulhaber's formula for the sum of m-th powers of the first n positive integers, in the Euler–Maclaurin formula, and in expressions for certain values of the Riemann zeta function.

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by $or, is equal to the binomial coefficient$

In mathematics, Pascal's triangle is an infinite triangular array of the binomial coefficients which play a crucial role in probability theory, combinatorics, and algebra. In much of the Western world, it is named after the French mathematician Blaise Pascal, although other mathematicians studied it centuries before him in Persia, India, China, Germany, and Italy.

In mathematics, Bertrand's postulate states that, for each $, there is a prime such that . First conjectured in 1845 by Joseph Bertrand, it was first proven by Chebyshev, and a shorter but also advanced proof was given by Ramanujan.$

In the mathematical field of numerical analysis, a Bernstein polynomial is a polynomial expressed as a linear combination of Bernstein basis polynomials. The idea is named after mathematician Sergei Natanovich Bernstein.

In mathematics, Mahler's theorem, introduced by Kurt Mahler, expresses any continuous p-adic function as an infinite series of certain special polynomials. It is the p-adic counterpart to the Stone-Weierstrass theorem for continuous real-valued functions on a closed interval.

In mathematics, the Poisson summation formula is an equation that relates the Fourier series coefficients of the periodic summation of a function to values of the function's continuous Fourier transform. Consequently, the periodic summation of a function is completely defined by discrete samples of the original function's Fourier transform. And conversely, the periodic summation of a function's Fourier transform is completely defined by discrete samples of the original function. The Poisson summation formula was discovered by Siméon Denis Poisson and is sometimes called Poisson resummation.

In mathematics, the multinomial theorem describes how to expand a power of a sum in terms of powers of the terms in that sum. It is the generalization of the binomial theorem from binomials to multinomials.

Multi-index notation is a mathematical notation that simplifies formulas used in multivariable calculus, partial differential equations and the theory of distributions, by generalising the concept of an integer index to an ordered tuple of indices.

In combinatorics, Vandermonde's identity is the following identity for binomial coefficients:

In mathematics, the Gaussian binomial coefficients are q-analogs of the binomial coefficients. The Gaussian binomial coefficient, written as $or, is a polynomial in q with integer coefficients, whose value when q is set to a prime power counts the number of subspaces of dimension k in a vector space of dimension n over, a finite field with q elements; i.e. it is the number of points in the finite Grassmannian .$

In mathematics the nth central binomial coefficient is the particular binomial coefficient

In combinatorics, the binomial transform is a sequence transformation that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to the sequence associated with its ordinary generating function.

In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient $by a prime number p in terms of the base p expansions of the integers m and n .$

In mathematics, in the field of combinatorics, the q-Vandermonde identity is a q-analogue of the Chu–Vandermonde identity. Using standard notation for q-binomial coefficients, the identity states that

In combinatorics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It can be used to solve many simple counting problems, such as how many ways there are to put $n$ indistinguishable balls into $k$ distinguishable bins. The solution to this particular problem is given by the binomial coefficient $, which is the number of subsets of size k - 1 that can be formed from a set of size n + k - 1 .$

In mathematics, Legendre's formula gives an expression for the exponent of the largest power of a prime p that divides the factorial n!. It is named after Adrien-Marie Legendre. It is also sometimes known as de Polignac's formula, after Alphonse de Polignac.

In probability theory and statistics, the Conway–Maxwell–binomial (CMB) distribution is a three parameter discrete probability distribution that generalises the binomial distribution in an analogous manner to the way that the Conway–Maxwell–Poisson distribution generalises the Poisson distribution. The CMB distribution can be used to model both positive and negative association among the Bernoulli summands,.

References

↑ Mihet, Dorel (December 2010). "Legendre's and Kummer's Theorems Again". Resonance. 15 (12): 1111–1121. doi:10.1007/s12045-010-0123-4.

Kummer, Ernst (1852). "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen". Journal für die reine und angewandte Mathematik. 1852 (44): 93–146. doi:10.1515/crll.1852.44.93.
Kummer's theorem at PlanetMath .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Mihet, Dorel (December 2010). "Legendre's and Kummer's Theorems Again". Resonance. 15 (12): 1111–1121. doi:10.1007/s12045-010-0123-4.

[1]