Fact-checked by Grok 2 weeks ago

Kummer's theorem

Kummer's theorem is a fundamental result in number theory that determines the exact exponent of a prime p in the prime factorization of a binomial coefficient \binom{n}{k}, where n and k are nonnegative integers with k \leq n. Formulated by Ernst Kummer in 1852, the theorem states that this exponent, denoted v_p\left( \binom{n}{k} \right), equals the number of carries required when adding the base-p digits of k and n - k to obtain the base-p digits of n.^[1] Ernst Eduard Kummer (1810–1893), a prominent German mathematician, introduced this theorem in his paper "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen," published in the Journal für die reine und angewandte Mathematik. The result emerged as part of Kummer's broader investigations into higher reciprocity laws and the arithmetic properties of cyclotomic fields, where binomial coefficients play a key role in expansions related to units and ideals. Although the theorem was originally embedded within discussions of generalized reciprocity, it has since been recognized as a standalone combinatorial tool for p-adic valuations.^[1] The theorem's significance lies in its elegant connection between arithmetic (p-adic orders) and combinatorics (base-p addition), providing a carry-counting criterion that avoids direct computation of factorials, which is computationally intensive for large n. It generalizes de Polignac's formula (also known as Legendre's formula) for the p-adic valuation of factorials and serves as a cornerstone for more advanced results, such as Lucas' theorem on binomial coefficients modulo a prime, which determines whether \binom{n}{k} \equiv 0 \pmod{p} by checking digit-wise inequalities in base p.^[2]^[3] Applications of Kummer's theorem extend across number theory, algebra, and combinatorics. In analytic number theory, it aids in estimating the distribution of prime powers dividing binomial coefficients, as seen in studies of the nonzero entries in Pascal's triangle modulo p^k. Combinatorially, it underpins proofs of identities involving sums of binomial coefficients and has been generalized to q-binomial coefficients and other hypergeometric structures. Furthermore, it finds use in algorithmic contexts, such as efficient computation of binomial coefficients modulo prime powers in computer algebra systems, and in proving divisibility properties for Catalan numbers and other combinatorial sequences derived from central binomial coefficients.^[4]^[3]^[5]

Background Concepts

Binomial Coefficients

Binomial coefficients, often denoted \binom{n}{k} or C(n, k), arise in combinatorics as fundamental quantities for counting selections. For non-negative integers n \geq k \geq 0, the binomial coefficient \binom{n}{k} is defined as the number of ways to choose k distinct items from a set of n distinct items without regard to the order of selection.^[6]^[7] This combinatorial interpretation positions binomial coefficients as the core of subset enumeration, where \binom{n}{k} equals the size of the collection of all k-element subsets of an n-element set.^[6]^[7] Algebraically, binomial coefficients are expressed using factorial notation, where the factorial n! denotes the product of all positive integers up to n, with $0! = 1 by convention. Thus, \binom{n}{k} = \frac{n!}{k!(n-k)!}.^[6]^[7] This formula provides a direct computational method, though direct evaluation of large factorials can be inefficient due to rapid growth; for instance, \binom{10}{5} = 252, while \binom{20}{10} = 184756, illustrating the exponential increase as n grows.^[6]^[7] Several basic properties facilitate manipulation and computation of binomial coefficients. The symmetry property states that \binom{n}{k} = \binom{n}{n-k}, reflecting the equivalence of choosing k items to leave out versus choosing the n-k to include.^[6]^[7] Pascal's identity provides a recursive relation: \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}, which corresponds to partitioning selections based on whether a particular item is included or excluded.^[6]^[7] Additionally, the generating function for the sequence \binom{n}{k} (for fixed n and varying k) is (1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k, encoding the coefficients in the expansion of this polynomial.^[6]^[7] These properties underpin the binomial theorem, where binomial coefficients appear as the multipliers in the expansion of (a + b)^n.^[6]^[7] To illustrate growth and computation, consider small values for n = 3: \binom{3}{0} = 1, \binom{3}{1} = 3, \binom{3}{2} = 3, \binom{3}{3} = 1, computed via the factorial formula or Pascal's identity starting from \binom{0}{0} = 1.^[7] For n = 4, the values are \binom{4}{0} = 1, \binom{4}{1} = 4, \binom{4}{2} = 6, \binom{4}{3} = 4, \binom{4}{4} = 1, showing the symmetric triangular pattern and rapid rise toward the center.^[6]^[7] Such examples highlight how binomial coefficients quantify combinatorial growth, essential for applications in probability, algebra, and beyond.^[6]^[7]

p-adic Valuations

The p-adic valuation, denoted v_p(m) for a prime p and nonzero integer m, is defined as the highest power of p that divides m, or equivalently, the exponent of p in the prime factorization of m; by convention, v_p(0) = \infty.^[8] This function quantifies the divisibility of integers by powers of p, providing a fundamental tool in number theory for analyzing prime factors.^[8] The p-adic valuation extends naturally to the rational numbers \mathbb{Q}: for integers a and b with b \neq 0, v_p(a/b) = v_p(a) - v_p(b).^[8] This extension preserves the additive property under multiplication, making it a valuation on the field of rationals.^[8] A key application arises in computing the p-adic valuation of factorials, given by de Polignac's formula (also known as Legendre's formula):

v_p(n!) = \sum_{i=1}^\infty \left\lfloor \frac{n}{p^i} \right\rfloor

for a positive integer n.^[9] This infinite sum terminates after finitely many terms since p^i > n for sufficiently large i. The formula derives from counting the contributions of the prime p in the product n! = 1 \cdot 2 \cdot \dots \cdot n: the term \left\lfloor n / p \right\rfloor counts the multiples of p up to n, \left\lfloor n / p^2 \right\rfloor counts the additional multiples of p^2 (each contributing an extra factor of p), and higher powers account for further overlaps in the same manner.^[10] For example, consider n = 10 and p = 2:

v_2(10!) = \left\lfloor \frac{10}{2} \right\rfloor + \left\lfloor \frac{10}{4} \right\rfloor + \left\lfloor \frac{10}{8} \right\rfloor + \left\lfloor \frac{10}{16} \right\rfloor + \cdots = 5 + 2 + 1 + 0 + \cdots = 8.

Similarly, for p = 5:

v_5(10!) = \left\lfloor \frac{10}{5} \right\rfloor + \left\lfloor \frac{10}{25} \right\rfloor + \cdots = 2 + 0 + \cdots = 2.

These computations confirm that $2^8 and $5^2 divide $10!.^[9] This valuation applies to binomial coefficients through the relation v_p \binom{n}{k} = v_p(n!) - v_p(k!) - v_p((n-k)!).^[9]

Historical Development

Kummer's Contributions

Ernst Eduard Kummer (1810–1893) was a prominent German mathematician known for his foundational contributions to algebraic number theory.^[11] Born in Sorau (now Żary, Poland), he initially worked as a schoolteacher before advancing to academic positions, ultimately serving as a professor of mathematics at the University of Berlin from 1855 until his retirement.^[11] Kummer's research focused on the arithmetic of cyclotomic fields and the development of ideal numbers to address unique factorization failures in these domains.^[12] Kummer's theorem on the p-adic valuation of binomial coefficients first appeared in his 1852 paper titled "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen," published in the Journal für die reine und angewandte Mathematik.^[1] This work formed part of his broader investigations into reciprocity laws and their supplements in number theory.^[1] Within the paper, Kummer derived the theorem as a tool to analyze the divisibility properties of binomial coefficients by primes, providing an exact formula for the exponent of a prime p dividing \binom{n}{k}.^[13] The theorem emerged amid Kummer's intensive efforts to prove cases of Fermat's Last Theorem, where he employed cyclotomic fields generated by roots of unity to factor expressions like x^n + y^n.^[12] In this context, binomial coefficients naturally arose in the expansions and factorizations within these fields, necessitating precise control over their prime divisibility to ensure unique factorization via ideal numbers.^[12] Kummer's approach highlighted the role of cyclotomic integers in resolving arithmetic issues tied to Fermat's equation for regular primes.^[14] A key innovation in Kummer's work was his recognition that the p-adic valuation of a binomial coefficient corresponds to the number of carries when adding the base-p digits of k and n-k to obtain those of n, thereby extending earlier formulas like Legendre's for the valuation of factorials.^[13] This base-p carry criterion offered a combinatorial interpretation that simplified computations and deepened insights into modular arithmetic structures.^[15] One of the foundational results in the study of prime powers dividing factorials was Adrien-Marie Legendre's formula from the early 1800s, which provides the exact exponent of a prime p in n!. Specifically, the p-adic valuation v_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac{n}{p^k} \right\rfloor, derived via inclusion-exclusion by counting multiples of increasing powers of p up to n. This formula is equivalent to v_p(n!) = \frac{n - s_p(n)}{p-1}, where s_p(n) denotes the sum of the digits of n in its base-p expansion.^[16]^[17] For binomial coefficients, early investigations focused on divisibility by the prime itself rather than higher powers. In 1736, Leonhard Euler demonstrated, as part of his proof of Fermat's Little Theorem, that for a prime p and $1 \leq k \leq p-1, the binomial coefficient \binom{p}{k} \equiv 0 \pmod{p}, establishing basic p-divisibility through the binomial expansion of (1+1)^p \equiv 2 \pmod{p}. However, extending this to higher powers of p relied on cruder bounds, such as v_p\left(\binom{n}{k}\right) \leq v_p(n!), which lacked precision for general n and k without subtracting the factorial valuations explicitly. These approaches, while useful for specific cases, did not account for the structural interactions like carries in base-p addition.^[18] A notable precursor involving higher powers appeared in Charles Babbage's 1819 work, where he proved that for primes p \geq 3, \binom{2p-1}{p-1} \equiv 1 \pmod{p^2}, implying limited p-divisibility for this central binomial coefficient. This congruence highlighted patterns in modulo p^2 but was specific rather than general. Relatedly, Joseph Wolstenholme's 1862 theorem extended such ideas, showing that for primes p > 3, the harmonic number H_{p-1} \equiv 0 \pmod{p^2} and certain binomial coefficients like \binom{2p}{p} \equiv 2 \pmod{p^3}, connecting to valuations via harmonic sums modulo prime powers.^[19] Pre-Kummer methods, primarily based on inclusion-exclusion for factorial valuations, enabled exact computation of v_p\left(\binom{n}{k}\right) as the difference v_p(n!) - v_p(k!) - v_p((n-k)!), yet they struggled to capture the exact interplay of base-p digits leading to carries in binomial settings, leaving a gap for more insightful structural interpretations. These developments, especially the base-p digit formulation, informed subsequent advancements in analyzing prime powers through expansions.^[17]

Statement of the Theorem

Precise Formulation

Kummer's theorem provides a precise criterion for determining the highest power of a prime p dividing the binomial coefficient \binom{n}{k}. Specifically, for a prime p and non-negative integers n \geq k \geq 0, the p-adic valuation v_p\left( \binom{n}{k} \right) equals the number of carries that occur when adding k and n-k in base p.^[20] To formalize this, express the base-p expansions as k = \sum_{i=0}^\infty k_i p^i, n-k = \sum_{i=0}^\infty m_i p^i, and n = \sum_{i=0}^\infty a_i p^i, where $0 \leq k_i, m_i, a_i < p for each i. A carry occurs at the i-th digit position if k_i + m_i \geq p; the theorem states that v_p\left( \binom{n}{k} \right) is the total number of such carries across all positions i.^[21] An equivalent formulation uses the sum of base-p digits, denoted s_p(\cdot): the number of carries is \frac{s_p(k) + s_p(n-k) - s_p(n)}{p-1}, so v_p\left( \binom{n}{k} \right) = \frac{s_p(k) + s_p(n-k) - s_p(n)}{p-1}.^[22] This equivalence follows from the fact that each carry effectively reduces the digit sum by p-1.^[21] This result relates to Legendre's formula for the p-adic valuation of factorials, v_p(n!) = \frac{n - s_p(n)}{p-1}, via the identity v_p\left( \binom{n}{k} \right) = v_p(n!) - v_p(k!) - v_p((n-k)!).^[22]

Basic Examples

To illustrate Kummer's theorem, consider the prime p = 2, n = 5, and k = 2. The binomial coefficient is \binom{5}{2} = 10, and its 2-adic valuation is v_2(10) = 1 since $10 = 2 \times 5. In base 2, k = 2 = 10_2 and n - k = 3 = 11_2. Adding these gives:

\begin{array}{r} 10_2 \\ + 11_2 \\ \hline 101_2 \end{array}

The units place sums to $0 + 1 = 1 with no carry, while the twos place sums to $1 + 1 = 2 = 10_2 (write 0, carry 1), and the fours place is $0 + 0 + 1 = 1. Thus, there is exactly one carry, matching v_2(10) = 1.^[23] For p = 3, n = 7, and k = 2, we have \binom{7}{2} = 21 and v_3(21) = 1 since $21 = 3 \times 7. In base 3, k = 2 = 02_3 and n - k = 5 = 12_3. Adding yields:

\begin{array}{r} 02_3 \\ + 12_3 \\ \hline 21_3 \end{array}

The units place sums to $2 + 2 = 4 = 1 \cdot 3 + 1 (write 1, carry 1), and the threes place sums to $0 + 1 + 1 = 2 with no further carry. One carry occurs, aligning with v_3(21) = 1.^[24] Now take p = 5, n = 10, and k = 5. Here, \binom{10}{5} = 252 and v_5(252) = 0 as 5 does not divide 252. In base 5, k = 5 = 10_5 and n - k = 5 = 10_5. Adding gives:

\begin{array}{r} 10_5 \\ + 10_5 \\ \hline 20_5 \end{array}

The units place is $0 + 0 = 0 with no carry, and the fives place is $1 + 1 = 2 with no carry. Zero carries confirm v_5(252) = 0.^[23] These examples demonstrate how the carries in base-p addition directly count the excess powers of p in \binom{n}{k}, visualizing the "borrowing" process implicit in de Polignac's (Legendre's) formula for the p-adic valuation of factorials, where v_p(n!) = (n - s_p(n))/(p-1) and s_p is the sum of base-p digits; the carries capture the discrepancy s_p(k) + s_p(n-k) - s_p(n).^[24]

Proof Techniques

Base-p Expansion Method

The base-p expansion method provides an algebraic proof of Kummer's theorem by leveraging the p-adic valuation of factorials via Legendre's formula and analyzing the addition of base-p digits of k and n-k. Legendre's formula states that the p-adic valuation of n! is given by v_p(n!) = \frac{n - s_p(n)}{p-1}, where s_p(n) denotes the sum of the digits of n in its base-p expansion.^[23] Applying this to the binomial coefficient \binom{n}{k} = \frac{n!}{k! (n-k)!}, the valuation becomes

v_p\left( \binom{n}{k} \right) = v_p(n!) - v_p(k!) - v_p((n-k)!) = \frac{s_p(k) + s_p(n-k) - s_p(n)}{p-1},

since the n terms cancel out, leaving the difference in digit sums scaled by \frac{1}{p-1}. This equivalence holds because s_p(m) \equiv m \pmod{p-1} for any integer m, ensuring the formula aligns with the additive properties of the valuation.^[23] To connect this to the number of carries, consider the base-p expansions: let n = \sum_{i=0}^t n_i p^i, k = \sum_{i=0}^t k_i p^i, and n-k = \sum_{i=0}^t m_i p^i, with each digit satisfying $0 \leq k_i, m_i, n_i < p. When adding the digits of k and n-k in base p to recover n, the process involves carries: at each position i, the sum k_i + m_i + c_i = n_i + c_{i+1} p, where c_i is the carry-in from the previous digit (with c_0 = 0), and c_{i+1} is the carry-out, taking values 0 or 1 for p > 2 since the maximum digit sum is 2(p-1).^[25] Rearranging gives k_i + m_i + c_i - n_i = c_{i+1} p, and summing over all digits yields

\sum_i (k_i + m_i - n_i) + \sum_i c_i = p \sum_i c_{i+1}.

The left side simplifies to s_p(k) + s_p(n-k) - s_p(n) + \sum_i c_i, while the right side is p times the total number of carries (shifted by one position, but equivalent in count). Each carry effectively reduces the total digit sum by p-1, as the carry-out subtracts p from the current position's contribution but adds 1 to the next, netting a (p-1) decrease when aggregated.^[23] Thus, the difference s_p(k) + s_p(n-k) - s_p(n) = (p-1) \times (total number of carries), confirming that v_p\left( \binom{n}{k} \right) equals the number of carries, as the factor \frac{1}{p-1} scales it precisely. This derivation verifies the theorem algebraically, independent of the specific digits, since the valuation is additive across the base-p places.^[23]

Combinatorial Proofs

Combinatorial proofs of Kummer's theorem provide bijective and counting-based arguments that interpret the number of carries in the base-p addition of k and n-k as structural features of combinatorial objects, such as subsets or permutations, offering intuitive insights into the p-adic valuation beyond algebraic methods. These proofs emphasize the theorem's connection to counting principles, where the valuation v_p(\binom{n}{k}) represents the number of "p-adic obstructions" encountered when selecting k-subsets from the set = {1, 2, ..., n], corresponding to overlaps or conflicts in residue classes along arithmetic progressions modulo powers of p. Equivalently, this exponent measures the extent to which subset choices violate independence in p-group structures, with each carry signifying a necessary adjustment in the counting process to account for modular dependencies.^[26] For the case p=2, a combinatorial proof uses permutations of binary vectors to establish the result, where the number of carries corresponds to features in the permutation structure acting on binary representations of the numbers involved.^[26] This approach has been extended to arbitrary primes in cases with no carries. Such proofs are case-specific and less common than algebraic ones. The advantages of these combinatorial proofs lie in their extensibility to generating functions, such as q-analogs of binomial coefficients where the parameter q enumerates or tracks the number of carries, enabling refined counts of subsets weighted by their p-adic complexity. For example, the q-binomial coefficient \qbin{n}{k}_q can be deformed to incorporate a carry-tracking variable, yielding polynomials whose degrees relate to maximal carry sequences and providing tools for enumerative combinatorics beyond the classical case. This framework supports applications in partition theory and symmetric function analogs of Kummer's result.^[27]

Generalizations

Multinomial Coefficients

Kummer's theorem extends naturally to multinomial coefficients. For a prime p and non-negative integers k_1, \dots, k_m with sum n = k_1 + \dots + k_m, the p-adic valuation v_p\left( \binom{n}{k_1, \dots, k_m} \right) of the multinomial coefficient \binom{n}{k_1, \dots, k_m} = \frac{n!}{k_1! \cdots k_m!} equals the total number of carries occurring when adding k_1 + \dots + k_m in base p. In this multi-addition, the numbers k_1, \dots, k_m are expressed in base p, and their digits are summed position by position, starting from the least significant digit. At each digit position j, the sum of the j-th digits of the k_i plus any incoming carry from position j-1 is computed; if this total s \geq p, then the digit written is s \mod p and a carry of \lfloor s / p \rfloor (typically 1 or more) is propagated to position j+1. The total valuation is the sum of all such carries generated across every position, independent of the order of addition or parenthesization. Equivalently, the valuation admits a closed-form expression using digit sums:

v_p\left( \binom{n}{k_1, \dots, k_m} \right) = \frac{1}{p-1} \left( \sum_{i=1}^m s_p(k_i) - s_p(n) \right),

where s_p(x) denotes the sum of the digits of x in base p. This follows from applying the formula for the p-adic valuation of factorials, v_p(\ell!) = \frac{\ell - s_p(\ell)}{p-1}, to the numerator and denominator of the multinomial coefficient. For instance, take p=2, n=4, and (k_1, k_2, k_3) = (1,1,2). The multinomial coefficient is \frac{4!}{1! \, 1! \, 2!} = 12, so v_2(12) = 2. In base 2, $1 = 1_2, $1 = 1_2, $2 = 10_2. Adding the units digits gives $1 + 1 + 0 = 2 \geq 2, yielding digit 0 and carry 1. For the next position, $0 + 0 + 1 + 1 = 2 \geq 2, yielding digit 0 and carry 1, which becomes the leading 1 in $4 = 100_2, confirming two carries. Alternatively, s_2(1) + s_2(1) + s_2(2) = 1 + 1 + 1 = 3 and s_2(4) = 1, so \frac{3-1}{2-1} = 2. This multinomial version specializes to the original binomial theorem when m=2.

Further Extensions

One prominent extension of Kummer's theorem involves q-analogs, where the classical p-adic valuation of binomial coefficients is generalized to Gaussian binomial coefficients \binom{n}{k}_q in the context of cyclotomic polynomials. Specifically, for a positive integer r, the exact power of the r-th cyclotomic polynomial \Phi_r(q) dividing \binom{n}{m}_q equals the number of carries when adding the base-r representations of m and n - m.^[28] This formulation replaces the prime p with the base r and adapts the carry mechanism to polynomial valuations, providing a q-deformed analogue that applies to basic hypergeometric series and partition identities.^[28] Kummer's theorem also facilitates the study of congruences in hypergeometric series modulo primes by determining the p-adic valuations of individual binomial terms within the expansion. For instance, in analyzing truncated _2F_1 series, the theorem allows computation of the valuation of terms like \binom{pr/2}{k} to establish supercongruences modulo p^{2r}, where the series reduces p-adically to a Gamma function quotient via Kummer's evaluation at specific arguments.^[29] Such applications reveal when the sum of the series is congruent to a dominant term modulo higher powers of p, extending classical congruences like those of Wolstenholme.^[29] In relation to Lucas' theorem, which computes binomial coefficients modulo p via digit-wise products in base p, Kummer's theorem complements it by quantifying the exact p-adic exponent, enabling full determination of the coefficient modulo arbitrary powers of p. Together, they provide complete p-adic information: Lucas for the unit part and Kummer for the valuation, with applications in algebraic number theory and coding theory. Further generalizations appear in dominance orders on compositions or partitions, where generalized binomial coefficients count intervals in the poset, and their p-adic valuations are governed by carries in a base-p addition analogous to Kummer's original setup. In the b-dominance poset, the rank function aligns with base-b digits, so the number of carries when "adding" lower and upper bounds in this order equals the exponent of a prime dividing the generalized coefficient, linking combinatorial chain structures to arithmetic properties.^[30] Recent work post-2000 has produced combinatorial proofs of Kummer's theorem in restricted settings, such as when n < p^2, where base-p representations have at most two digits and carries are limited. For p=2, the proof interprets the valuation as the minimal number of transpositions mixing binary vectors corresponding to the subsets, while for general p and zero carries, it uses permutation statistics on vectors over finite fields to count non-carrying additions directly.^[26] These approaches avoid p-adic analysis, offering bijective insights into the carry process for small n.^[26]

Applications

Number Theory Contexts

Kummer's theorem plays a pivotal role in algebraic number theory, particularly in Ernst Kummer's investigations into Fermat's Last Theorem within cyclotomic fields. For an odd prime p, Kummer considered the cyclotomic field \mathbb{Q}(\zeta_p), where \zeta_p is a primitive p-th root of unity, and the ring of integers \mathbb{Z}[\zeta_p]. He introduced the concept of regular primes, defined as those odd primes p for which p does not divide the class number h of \mathbb{Q}(\zeta_p), ensuring that the ideal class group has no p-torsion and allowing for unique factorization of ideals into principal ideals under certain conditions. Using properties of binomial coefficients in cyclotomic fields, Kummer demonstrated that Fermat's Last Theorem holds for all regular primes, meaning there are no nontrivial integer solutions to x^p + y^p = z^p with p \nmid xyz. This result covers infinitely many primes, as the density of regular primes is positive, though Kummer himself computed that the first irregular prime is 37.^[14] In analytic number theory, Kummer's theorem extends Wolstenholme's theorem by providing bounds on the p-adic valuation of harmonic numbers through representations involving binomial sums. Wolstenholme's theorem states that for a prime p \geq 5, the numerator of the harmonic number H_{p-1} = \sum_{k=1}^{p-1} 1/k is divisible by p^2, or equivalently, v_p(H_{p-1}) \geq 2. Harmonic numbers can be expressed using binomial coefficients via identities such as the integral representation or partial fraction decompositions, allowing the p-adic valuation v_p(H_n) to be analyzed through the valuations of these binomials. Applying Kummer's theorem, the number of carries in base-p additions determines v_p(\binom{n}{k}) in such sums, yielding precise bounds on v_p(H_n) and extensions to higher powers for Wolstenholme primes (where the congruence holds modulo p^3). These bounds facilitate studies of the distribution of v_p(H_n) and connections to irregular primes.^[31] Kummer's theorem also supports p-adic interpolation techniques in the analysis of binomial coefficients and related functions, notably Morita's p-adic gamma function \Gamma_p. Defined as \Gamma_p(n+1) = (-1)^{n+1} \prod_{\substack{1 \leq k \leq n \\ p \nmid k}} k for positive integers n, Morita's \Gamma_p extends factorials to p-adic integers and interpolates binomial coefficients via relations like \binom{n}{k}_p = \frac{\Gamma_p(n+1)}{\Gamma_p(k+1) \Gamma_p(n-k+1)} in the p-adic sense. The theorem's carry criterion determines the exact p-adic valuation of these interpolated binomials, enabling the study of p-adic continuity and convergence of series involving binomials in p-adic analysis. This framework aids in constructing p-adic L-functions and zeta functions, where the valuation control ensures analytic properties over the p-adic disk. The theorem directly implies key congruences for binomial coefficients modulo prime powers, stating that \binom{n}{k} \equiv 0 \pmod{p^r} if and only if adding the base-p expansions of k and n-k requires at least r carries. This criterion provides a combinatorial test for higher-order divisibility by p^r, linking to prime power conditions in number theory. For instance, it characterizes cases where binomials are divisible by high powers of p, relevant to criteria for special primes like Wieferich primes, which satisfy $2^{p-1} \equiv 1 \pmod{p^2} and arise in analyses of binomial expansions modulo p^2 via Fermat's Little Theorem extensions. Such congruences underpin studies of pseudoprimes and anomalous prime behaviors in modular arithmetic.^[15] A representative example is the divisibility of the central binomial coefficient \binom{2n}{n} by powers of 2, which connects to Catalan numbers C_n = \frac{1}{n+1} \binom{2n}{n}. For p=2, Kummer's theorem yields v_2\left(\binom{2n}{n}\right) as the number of carries when adding n + n in base 2, equivalent to the number of 1's in the binary expansion of n (the binary weight, or popcount). Thus, v_2\left(\binom{2n}{n}\right) = s_2(n), where s_2(n) counts the 1-bits in n. For Catalan numbers, v_2(C_n) = s_2(n) - v_2(n+1), illustrating how the theorem quantifies 2-adic properties in combinatorial sequences and their generating functions.^[32]

Combinatorial Uses

Kummer's theorem provides a combinatorial lens for counting lattice paths by linking the p-adic valuation of binomial coefficients to carry operations in base p, thereby interpreting divisibility properties in path enumerations. Specifically, since \binom{n}{k} counts the number of lattice paths from (0,0) to (k, n-k) using unit right and up steps, the theorem equates the exponent of p dividing this count to the number of carries when adding k and n-k in base p. This connection allows for the analysis of path counts modulo p^r, where paths to endpoints with no carries correspond to counts not divisible by p, and higher carry counts indicate "defects" in modular arithmetic for path statistics like area or height. For instance, when n and k are coprime, the paths can be partitioned into n equicardinal classes based on area modulo n, with the theorem verifying the necessary divisibility \binom{n}{k} \equiv 0 \pmod{n}.^[33] In generating functions, Kummer's theorem refines the expansion of (1 + x)^n modulo p by associating carries with the p-adic orders of coefficients, enabling precise tracking of terms in higher-order modular approximations. The theorem implies that coefficients with no carries contribute to the support of the generating function modulo p, while carry counts determine the vanishing orders for p^r. This is particularly useful in formal power series over finite fields, where the product formula for (1 + x)^n is dissected digit-by-digit in base p, with carries governing interactions between digits and thus higher p-powers in the coefficients. Such refinements aid in deriving congruences for generating functions in combinatorial identities.^[34] Combinatorial applications extend to subset sums, where the theorem facilitates counting subsets whose sums are divisible by p^r through carry-free additions in base p representations. For a set of elements with base p expansions that avoid digit overlaps in subsets, the number of such subsets with sum congruent to 0 modulo p^r corresponds to selections without carries, directly tying to zero-valuation cases in generalized binomial counts. In the context of lattice walks or multi-set selections, this manifests as enumerating carry-free partitionings of n into k parts, with the valuation given by carry counts upon addition, applicable in coding theory for determining codeword weights modulo prime powers.^[35] Algorithmically, Kummer's theorem enables efficient computation of v_p\left(\binom{n}{k}\right) in O(\log n) time by converting n and k to base p, performing the addition of k and n-k, and counting carries, a method foundational in computer algebra systems for exact arithmetic. This efficiency supports applications in random sampling of combinations, where the valuation informs probabilistic generation of uniform random k-subsets by weighting samples based on divisibility properties to avoid over- or under-representation in modular settings.^[23] In enumerative combinatorics, the theorem's extension to multinomial coefficients—where the p-adic valuation equals the number of carries when adding the parts in base p—provides bounds on the p-part of partition-related counts, such as Stirling numbers of the second kind, which enumerate partitions of an n-set into k non-empty subsets. For example, explicit formulas for v_p(S(n,k)) leverage carry counts in the multinomial \binom{n}{n_1, \dots, n_k} underlying the expression S(n,k) = \frac{1}{k!} \sum \binom{n}{n_1, \dots, n_k}, yielding asymptotic bounds on the p-divisibility of partition functions in restricted classes.

References

[1]
Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen.
Kummer, E.E.. "Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen.." Journal für die reine und angewandte Mathematik 44 (1852): 93-146.
[2]
[PDF] Enumeration of binomial coefficients by their p-adic valuations
Let νp(n) denote the exponent of the highest power of p dividing n. Example: ν3(18) = 2. Theorem (Kummer 1852) νp(.
[3]
[PDF] On the Divisibility of Binomial Coefficients - MIT Mathematics
Kum- mer's Theorem provides an easy way to determine the highest power of a prime that divides a binomial coefficient, and Lucas' Theorem yields the remainder ...Missing: source | Show results with:source
[4]
[PDF] The Power of a Prime That Divides a Generalized Binomial Coefficient
The highest power of a prime p dividing a generalized binomial coefficient is related to the number of "carries" when m and n are added in p-ary notation.Missing: statement | Show results with:statement
[5]
[PDF] On divisibility of Narayana numbers by primes
May 16, 2005 · Kummer's Theorem [5] gives a useful way of finding the order of binomial coefficients. For example, Knuth and Wilf [4] used it to find the ...<|control11|><|separator|>
[6]
Binomial Coefficient -- from Wolfram MathWorld
The binomial coefficient (n; k) is the number of ways of picking k unordered outcomes from n possibilities, also known as a combination or combinatorial number.Missing: "combinatorics | Show results with:"combinatorics
[7]
[PDF] ctgd.pdf - Combinatorics Through Guided Discovery
effort to create a combinatorics textbook that developed the key ideas of undergrad- ... binomial coefficient divided by an integer. Whenever we have a ...
[8]
p-adic valuation - PlanetMath
Mar 22, 2013 · The value group of the p -adic valuation consists of all integer-powers of the prime number p . The valuation ring. of the valuation is called ...
[9]
de Polignac's formula - PlanetMath.org
Mar 22, 2013 · de Polignac's formula. Given n n , the prime factorization of n! n ! can be obtained by applying de Polignac's formula: ...Missing: v_p( | Show results with:v_p(
[10]
[PDF] Math 221 Winter 2023, Lecture 11: Elementary number theory
Feb 16, 2023 · There turns out to be a nice formula for this:2. Theorem 3.6.15 (de Polignac's formula). Let p be a prime. Let n ∈ N. Then, vp (n!) = n p1. + n.
[11]
Eduard Kummer (1810 - 1893) - Biography - MacTutor
Having first been elected to the Berlin Academy while still a school teacher, Kummer ended up with high office in the Academy. He was secretary of the ...
[12]
[PDF] Kummer's theory on ideal numbers and Fermat's Last Theorem
Abstract. This paper is an exposition on Ernst Kummer's theory of ideal numbers, which “saves” unique factorization in the ring of integers of the cy-.Missing: original | Show results with:original
[13]
A CARRY THEOREM FOR RATIONAL BINOMIAL COEFFICIENTS
Ernst Eduard Kummer proved in 1852 that for any nonnegative integers j and k and any prime p, the exponent of the highest power of p that divides the ...
[14]
[PDF] Kummer, Regular Primes, and Fermat's Last Theorem
Abstract. This paper rephrases Kummer's proof of many cases of Fermat's last theorem in contemporary notation that was in fact derived from his work.
[15]
[PDF] We study the value of binomial coefficients modulo gi
In 1852 Kummer showed that the power of prime p that divides the binomial coefficient nmisgiven by the number of 'carries' when we add m andl -m in base p ...
[16]
[PDF] A GLORIOUS BEGINNING 1 Binomial coefficients
This formula was presented by Adrien-Marie Legendre in the second edition of his Essai sur la Théorie des Nombres, published in 1808. 5 Erd˝os's proof of ...
[17]
[PDF] Legendre's formula and p-adic analysis - arXiv
Apr 26, 2019 · Abstract. In number theory, we know Legendre's formula vp (n!) = ∑ k ≥ 1 ⌊n/p k⌋ , which calculates the p-adic valuation of the factorial, ...
[18]
Proof of Fermat's Little Theorem - The Prime Pages
Euler first published a proof in 1736, but Leibniz left virtually the same proof in an unpublished manuscript from sometime before 1683. Proof.Missing: date | Show results with:date
[19]
On Wolstenholme's theorem and its converse - ScienceDirect
Wolstenholme proved that if p is a prime ⩾5, then w p ≡ 1 ( mod p 3 ) . The converse of Wolstenholme's theorem, which has been conjectured to be true, remains ...
[20]
Introduction.
In 1852 Kummer showed that the power of prime p which divides the binomial coefficient is given by the number of `carries' when we add m and n-m in base p.Missing: Ernst | Show results with:Ernst
[21]
Kummer's theorem - PlanetMath
Mar 22, 2013 · Given integers n≥m≥0 n ≥ m ≥ 0 and a prime number p p , then the power of p p dividing (nm) ( n m ) is equal to the number of carries when ...
[22]
[PDF] arXiv:0811.2028v1 [math.NT] 13 Nov 2008
Nov 13, 2008 · (1.5) νp(n) = 1 + sp(n − 1) − sp(n) p − 1 . The p-adic valuations of binomial coefficients can be expressed in terms of the function sp: (1.6).Missing: (s_p( s_p(
[23]
[PDF] Legendre's and Kummer's Theorems Again
For example, in [3] this formula is named De Polignac's Formula. n! = Y p n ... vp(n!) =n − (a0 + a1 + ··· + ak) p − 1. : (1). The common proof of this ...Missing: v_p( | Show results with:v_p(
[24]
[PDF] arXiv:1704.05872v2 [math.NT] 24 Mar 2018
Mar 24, 2018 · A natural question suggested by this paper is whether various generalizations of binomial coefficients (Fibonomial coefficients, q-binomial ...
[25]
https://www.isibang.ac.in/~sury/kummerlegendre.pdf
[26]
[PDF] Classroom - Indian Statistical Institute, Bangalore
Kummer proved is that, if r < n, then the p-adic valua- tion of the binomial coefficient (~) is simply the number of 'carry-overs' when one adds r and n - r in ...
[27]
The Combinatorics of Kummer's Theorem on Binomial Coefficients
We present novel combinatorial proofs for some cases of a classic result of Kummer, that the highest power of p p dividing the binomial coefficient n n ...Missing: source | Show results with:source
[28]
Bisecting binomial coefficients - ScienceDirect
Aug 20, 2017 · Equivalently, v p n k is the number of borrows when subtracting k from N in base p (a result of Kummer rediscovered by Goetgheluck [12]).
[29]
[PDF] Bisecting binomial coefficients - Faculty
Apr 21, 2017 · Abstract. In this paper, we deal with the problem of bisecting binomial coefficients. We find many (previously unknown) infinite classes of ...
[30]
https://www.jstor.org/stable/10.4169/math.mag.87.2.135
[31]
https://arxiv.org/pdf/1511.05553
[32]
https://math.dartmouth.edu/~carlp/catalan5.pdf
[33]
Dominance Orders, Generalized Binomial Coefficients, and ... - jstor
Rank, “Carries,” and Kummer's Theorem for prime bases. The relevant feature of the b-dominance poset to our discussion is its rank function. Note that b ...
[34]
[PDF] arXiv:1511.05553v5 [math.NT] 29 Oct 2019
Oct 29, 2019 · The p-adic valuation of the binomial coefficient m+n m is equal ... Sun, Two congruences involving harmonic numbers with applications, Int.
[35]
[PDF] Divisors of the middle binomial coefficient - Dartmouth Mathematics
These bounds were so good that it seemed a promising path to the prime number theorem, but eventually that goal was reached by other methods. The central ...
[36]
[PDF] arXiv:2102.00944v2 [math.CO] 9 Apr 2021
Apr 9, 2021 · From a combinatorial perspective, the central binomial coefficient is equal to the number of lattice paths from (0, 0) to (n, n) by taking one ...Missing: v_2 | Show results with:v_2
[37]
Divisibility of binomial coefficients by powers of two - ScienceDirect
Divisibility of binomial coefficient by powers of primes is a notion strongly linked to the base-p expansion of integers. This connection is highlighted by ...
[38]
[PDF] Powers of 2 in High-Dimensional Lattice Walks - arXiv
Jun 15, 2025 · if and only if x1, x2, ..., xk form a carry-free partitioning of n. ... by Kummer's theorem. Furthermore, F(X) is divisible by 2 with ...