Kummer's theorem

Last updated April 06, 2024

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:

	₁	₁	₁
			1	1 ₂
+		1	1	1 ₂
	1	0	1	0 ₂

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(-S_{p}(n)+\sum _{i=1}^{k}S_{p}(m_{i})\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 (or binomial expansion) describes the algebraic expansion of powers of a binomial. According to the theorem, it is possible to expand the polynomial $(x + y) n$ into a sum involving terms of the form $ax b y c$ , where the exponents $b$ and $c$ are nonnegative integers with $b + c = n$ , and the coefficient $a$ of each term is a specific positive integer depending on $n$ and $b$ . For example, for $n = 4$ ,

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, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

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

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In calculus, the general Leibniz rule, named after Gottfried Wilhelm Leibniz, generalizes the product rule. It states that if $and are -times differentiable functions, then the product is also -times differentiable and its th derivative is given by$

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 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 mathematics, the Schuette–Nesbitt formula is a generalization of the inclusion–exclusion principle. It is named after Donald R. Schuette and Cecil J. Nesbitt.

In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It was popularized by William Feller in his classic book on probability. 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.

<span class="texhtml mvar" style="font-style:italic;">p</span>-adic valuation

In number theory, the $p$ -adic valuation or $p$ -adic order of an integer $n$ is the exponent of the highest power of the prime number $p$ that divides $n$ . It is denoted $. Equivalently, is the exponent to which appears in the prime factorization of .$

In mathematics, the Mittag-Leffler polynomials are the polynomials g_n(x) or M_n(x) studied by Mittag-Leffler (1891).

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.

References

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

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.

[1]