Kummer’s Theorem

Project Euler presents many problems in number theory and combinatorics. This post documents Kummer’s theorem, which I studied while solving these problems. Kummer’s theorem provides a method to compute the exponent of a prime $p$ in the prime factorization of a binomial coefficient $\binom{n}{k}$, denoted $v_p\binom{n}{k}$.

Kummer’s Theorem

Kummer’s theorem states the following: Given integers $n$ and $k$, and a prime $p$, the exponent $v_p\binom{n}{k}$ is given by:

\[v_p\binom{n}{k} = \frac{n - S_p(n)}{p - 1}\]

Here, $S_p(n)$ denotes the sum of digits of $n$ when written in base $p$. For example, if $n = 123_{(p)}$, then $S_p(n) = 1 + 2 + 3 = 6$.

Derivation

Kummer’s theorem follows from Legendre’s formula:

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

When the integer $n$ is expressed in base $p$ as $n = \sum_{i=0}^k a_i p^i$, we have:

\begin{align} v_p(n!) &= \sum_{i=1}^k \left\lfloor \frac{n}{p^i} \right\rfloor = \sum_{i=1}^k \sum_{j=i}^k a_j p^{j - i} \nonumber \newline &= \sum_{j=1}^k a_j \sum_{i=1}^j p^{j - i} = \sum_{j=1}^k a_j \sum_{i=0}^{j - 1} p^i \nonumber \newline &= \sum_{j=1}^k a_j \frac{p^j - 1}{p - 1} = \frac{n - S_p(n)}{p - 1} \nonumber \end{align}

Using this result, the exponent $v_p(\binom{n}{k})$ is:

\begin{align} v_p\binom{n}{k} &= v_p(n!) - v_p(k!) - v_p((n - k)!) \nonumber \newline &= \frac{n - S_p(n)}{p - 1} - \frac{k - S_p(k)}{p - 1} - \frac{(n - k) - S_p(n - k)}{p - 1} \nonumber \newline &= \frac{S_p(k) + S_p(n - k) - S_p(n)}{p - 1} \nonumber \end{align}

Application

When solving problems, it is important to reuse previously computed results rather than recalculating the same quantities repeatedly. Kummer’s theorem likewise allows us to cache intermediate results and avoid redundant computation. If $n$ is expressed as $n = qp + r$, the formula for $v_p(n!)$ can be rewritten as follows:

\begin{align} S_p(n) &= S_p(qp + r) = S_p(q) + r \nonumber \newline v_p(n!) &= \frac{qp + r - S_p(q) - r}{p - 1} = \frac{qp - S_p(q)}{p - 1} \nonumber \end{align}