Factorial Modulo

Introduction

This article discusses results related to factorial computation modulo a certain modulus and provides a method with time complexity linear in the modulus size, making it suitable for moduli that are not too large (∼10^6). Besides the method introduced here, depending on the scenario, polynomial techniques can also be applied for fast computation.

According to the Chinese Remainder Theorem, the factorial modulo problem can be reduced to the case where the modulus is a prime power p^α. When dealing with such problems, it is often necessary to extract all factors p from the factorial n! for a prime p and positive integer n, obtaining the decomposition:

\[ n! = p^{\nu_p(n!)}(n!)_p. \]

Here, ν_p(n!) denotes the exponent of p in the prime factorization of n!, and (n!)_p denotes the integer obtained by removing all powers of p from the result of n!. This article discusses the remainder of (n!)_p modulo a prime (power) and the specific method for computing the exponent ν_p(n!).

This decomposition is particularly useful when factorials appear in both the numerator and denominator of an expression, such as when computing binomial coefficients modulo a modulus. For such problems, the exponents of p in the numerator and denominator can be directly subtracted, while the p-coprime part (n!)_p can be computed using modular inverses.

This article also introduces Wilson's theorem and its generalization, Legendre's formula, and Kummer's theorem, which are related to the above problems.

Wilson's Theorem

Wilson's theorem provides a necessary and sufficient condition for a natural number to be prime.

Wilson's Theorem

For a natural number n > 1, (n-1)! ≡ -1 (mod n) if and only if n is prime.

Proof

First, prove that for a prime p, (p-1)! ≡ -1 (mod p). This can be concisely proved using congruence equations or primitive roots, which we omit here. Below we provide a proof requiring less background knowledge:

When p = 2, the proposition is obvious. Now assume p ≥ 3, and we want to show that the product of all nonzero elements (i.e., congruence classes) in Z_p is \overline{-1}. Since every nonzero element \overline{a} in Z_p has an inverse \overline{a}^{-1}, the product of mutually inverse elements in Z_p is \overline{1}. However, note that \overline{a} and \overline{a}^{-1} may be equal: \overline{a} = \overline{a}^{-1} if and only if a^2 ≡ 1 (mod p), i.e.,

\[ 0\equiv a^2-1\equiv (a+1)(a-1),\pmod p \]

Thus, a ≡ 1 (mod p) or a ≡ -1 (mod p). This shows that the product of all elements in Z_p \setminus {\overline{0},\overline{1},\overline{-1}} is \overline{1}, and hence the product of all nonzero elements in Z_p is \overline{-1}.

Conversely, for composite n, we prove that (n-1)! ≢ -1 (mod n). By contradiction, assume (n-1)! ≡ -1 (mod n), i.e., there exists an integer k such that (n-1)! = kn - 1. Since n is composite, there exists a prime p < n such that n = pm, so (n-1)! = kpm - 1 ≡ -1 (mod p). However, the product (n-1)! must already contain p, so we must have (n-1)! ≡ 0 (mod p). This contradiction shows that (n-1)! ≢ -1 (mod n).

Using the notation of this article, Wilson's theorem can be written as (p!)_p ≡ -1 (mod p).

Generalization

Wilson's theorem can be generalized to general moduli.

Theorem (Gauss)

For a natural number m > 1,

\[ \prod_{1\le k<m,\ k\perp m} k \equiv \pm 1 \pmod{m}. \]

Moreover, the ±1 takes the value -1 if and only if a primitive root modulo m exists, i.e., when m = 2, 4, p^α, 2p^α, where p is an odd prime and α is a positive integer.

Proof

This theorem can be simply proved using the structure of the multiplicative group of integers modulo n. Here we give a more elementary proof with a similar idea.

For m = 2, we have 1! = 1 ≡ -1 (mod 2). For other cases where a primitive root exists, let g be a primitive root. Then every positive integer k less than m and coprime to m can be uniquely represented as g^i mod m, where 0 ≤ i < φ(m) and φ(m) is the Euler totient function. Direct verification shows that φ(m) must be even. Since g^i and g^{φ(m)-i} are multiplicative inverses of each other, pairing them in the product gives

\[ \prod_{1\le k<m,\ k\perp m} k \equiv \prod_{i=0}^{\varphi(m)-1}g^i = g^{\varphi(m)/2}\prod_{i=1}^{\varphi(m)/2-1}g^{i}g^{\varphi(m)-i} \equiv g^{\varphi(m)/2} \pmod{m}. \]

Since g^{φ(m)/2} mod m is the unique element not equal to 1 mod m whose multiplicative inverse is itself, it equals -1 mod m. This shows that the remainder is -1 in this case.

For cases where a primitive root modulo m does not exist, we prove that the remainder is 1. To do this, first factor m as m = p_1^{e_1} p_2^{e_2} ... p_s^{e_s}. Then applying the Chinese Remainder Theorem, it suffices to prove

\[ \prod_{1\le k<m,\ k\perp m} k\equiv 1\pmod{p_j^{e_j}} \]

for each factor p_j^{e_j}. The Chinese Remainder Theorem implies that each possible remainder combination (r_1, r_2, ..., r_s), where 1 ≤ r_j < p_j^{e_j} and p_j ⟂ r_j, uniquely corresponds to a 1 ≤ k < m with k ⟂ m such that k ≡ r_j (mod p_j^{e_j}). Therefore, for a given remainder r_j, there are exactly φ(m) / φ(p_j^{e_j}) numbers k such that k ≡ r_j (mod p_j^{e_j}). Using this, we can group the product as

\[ \prod_{1\le k<m,\ k\perp m} k\equiv\left(\prod_{1\le r_j<p_j^{e_j},\ r_j\perp p_j} r_j\right)^{{\varphi(m)}/{\varphi(p_j^{e_j})}}\pmod{p_j^{e_j}}. \]

The exponent φ(m) / φ(p_j^{e_j}) = φ(m / p_j^{e_j}) must be odd only if m / p_j^{e_j} = 1, 2, because the Euler totient function φ(n) is even for n ≥ 3. If p_j is an odd prime, since a primitive root modulo m does not exist, we must have m / p_j^{e_j} ≠ 1, 2; if p_j^{e_j} = 2, 4, since a primitive root modulo m does not exist, m / p_j^{e_j} must contain some odd prime factor, hence greater than 2: in both cases the exponent φ(m) / φ(p_j^{e_j}) is even. The term inside parentheses has been proved to be congruent to -1 modulo p_j^{e_j}, so this power modulo p_j^{e_j} must be 1. The remaining case is when p_j = 2 and e_j > 2. For this case, we directly prove

\[ \prod_{1\le r_j<2^{e_j},\ r_j\perp 2}r_j \equiv 1\pmod{2^{e_j}}. \]

Following the previous proof idea, we can pair all odd numbers r_j with 1 ≤ r_j < 2^{e_j} to cancel them out. Those that cannot be paired must be solutions to x^2 ≡ 1 (mod 2^{e_j}). This equation implies 2^{e_j} | (x-1)(x+1). Let x = 2y + 1, then we must have 2^{e_j-2} | y(y+1), and y and y+1 must have opposite parity, so y = t 2^{e_j-2} or y = t 2^{e_j-2} - 1. Hence, x = t 2^{e_j-1} ± 1, where t is an integer. Among residues modulo 2^{e_j}, only ±1 and 2^{e_j-1} ± 1 are possible. Therefore,

\[ \prod_{1\le r_j<2^{e_j},\ r_j\perp 2}r_j \equiv (-1)(2^{e_j-1}-1)(2^{e_j-1}+1) \equiv 1\pmod{2^{e_j}}. \]

This completes the proof for all cases.

In computation, the case where the modulus is a prime power is particularly important:

Corollary

For a prime p and positive integer α,

\[ \prod_{1\le k<p^\alpha,\ k\perp p}k \equiv \begin{cases} 1, & p=2\text{ and }\alpha\ge3,\\ -1, &\text{otherwise} \end{cases} \pmod{p^\alpha}. \]

Note that the left-hand side is not (p^α!)_p, because the latter also includes contributions from multiples of p.

Computing Factorial Remainders

This section discusses the computation of the remainder (n!)_p mod p^α.

Prime Modulus Case

The expression (n!)_p has a clear recursive structure. To see this, first examine a concrete example:

Example

To compute (32!)_5 mod 5, we can perform the following recursive computation:

\[ \begin{aligned} (32!)_5 &= 1\times 2\times 3 \times 4\times \underbrace{1}_{5}\times 6 \times 7 \times 8\times 9 \times \underbrace{2}_{10} \\ &\quad\times 11 \times 12 \times 13 \times 14\times \underbrace{3}_{15}\times 16 \times 17\times 18\times 19\times \underbrace{4}_{20} \\ &\quad\times 21 \times 22 \times 23 \times 24\times \underbrace{1}_{25}\times 26 \times 27\times 28\times 29\times \underbrace{6}_{30} \times 31 \times 32 \\ &\equiv 1\times 2\times 3 \times 4\times \underbrace{1}_{5}\times 1 \times 2 \times 3\times 4 \times \underbrace{2}_{10} \\ &\quad\times 1 \times 2 \times 3 \times 4\times \underbrace{3}_{15}\times 1 \times 2\times 3\times 4\times \underbrace{4}_{20} \\ &\quad\times 1 \times 2 \times 3 \times 4\times \underbrace{1}_{25}\times 1 \times 2\times 3\times 4\times \underbrace{1}_{30}\times 1\times 2\\ &= (1\times 2\times 3\times 4)^{6}\times(1\times 2)\times(\underbrace{1}_{5}\times \underbrace{2}_{10}\times \underbrace{3}_{15} \times \underbrace{4}_{20}\times \underbrace{1}_{25}\times \underbrace{1}_{30}) \pmod{5} \end{aligned} \]

It can be seen that, using the periodicity of residues modulo 5, this product can be divided into blocks of length 5, with the only difference being the residue of the last element in each block. Since 32 divided by 5 gives quotient 6 and remainder 2, the product can be divided into 6 complete blocks and a final incomplete block of length 2. Therefore, we can extract the part of the first 6 blocks excluding the last element (this part is exactly what Wilson's theorem handles), multiply by the product of the incomplete block, and finally multiply by the product of the last elements of the first 6 blocks. The last element of each block is a multiple of 5; after removing powers of 5, their product is exactly (6!)_5 (mod 5). This transforms the original problem into a smaller one.

Generalizing the recursive structure from the example yields the following recurrence:

Recurrence Formula

For a prime p and positive integer n,

\[ (n!)_p \equiv (-1)^{\left\lfloor n/p\right\rfloor}\cdot (n\bmod p)!\cdot\left(\left\lfloor n/p\right\rfloor!\right)_p\pmod{p}. \]

Proof

Let (k)_p denote the result of removing all powers of p from the prime factorization of k. Then,

\[ \begin{aligned} (n!)_p &= \prod_{k=1}^n(k)_p = \left(\prod_{1\le k\le n,\ k\perp p}(k)_p\right)\left(\prod_{1\le k\le\lfloor n/p\rfloor}(pk)_p\right) \\ &= \left(\prod_{i=0}^{\lfloor n/p\rfloor-1}\prod_{j=1}^{p-1}(ip+j)\right)\left(\prod_{j=1}^{n\bmod p}(\lfloor n/k\rfloor k+j)\right)\left(\prod_{1\le k\le\lfloor n/p\rfloor}(k)_p\right) \\ &\equiv\left(\prod_{j=1}^{p-1}j\right)^{\lfloor n/p\rfloor}\left(\prod_{j=1}^{n\bmod p}j\right)(\lfloor n/p\rfloor!)_p \\ &\equiv (-1)^{\lfloor n/p\rfloor}\cdot(n\bmod p)!\cdot(\lfloor n/p\rfloor!)_p \pmod p. \end{aligned} \]

This completes the proof. Below we provide a concrete explanation for this form.

To compute (n!)_p mod p. Following the example above, we have

\[ \begin{aligned} (n!)_p &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}_{2p} \\ &\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}_{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\ &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}_{2p} \cdot 1 \cdot 2 \\ &\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p}. \end{aligned} \]

Clearly, except for the last block, the factorial is divided into several complete blocks of equal length.

\[ \begin{aligned} (n!)_p&= \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}_{2\text{nd}} \cdot \ldots \\ &\quad \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}. \end{aligned} \]

Excluding the last element of each block, the main part of a complete block, (p-1)! mod p, is easy to compute using Wilson's theorem:

\[ (p-1)!\equiv -1\pmod p. \]

There are ⌊n/p⌋ complete blocks, so we need to raise -1 to the power ⌊n/p⌋.

The value of the last partial block is (n mod p)! mod p, which can be computed separately.

The remaining part is the last element of each block. Hiding the already processed elements, we see the following pattern:

\[ (n!)_p = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots \]

This is also a modified factorial, but much shorter. It is:

\[ \left(\left\lfloor \frac{n}{p} \right\rfloor !\right)_p. \]

Multiplying all parts together gives the recurrence formula above.

Using this recurrence for computation, the recursion depth is O(log_p n). If the middle term is recomputed each time, the complexity per level is O(p), resulting in total time complexity O(p log_p n). If n! mod p is precomputed for all n = 1, 2, ..., p-1, the preprocessing complexity is O(p), the complexity per level is O(1), and the total time complexity is O(p + log_p n).

In implementation, since it is tail recursion, iteration can be used. The following implementation precomputes the first p-1 factorials. If multiple calls are needed, the precomputation can be moved outside the function.

Reference Implementation

// Calculate (n!)_p mod p.
int factmod(int n, int p) {
  // Pretreatment.
  std::vector<int> f(p);
  f[0] = 1;
  for (int i = 1; i < p; ++i) {
    f[i] = (long long)f[i - 1] * i % p;
  }
  // Recursion.
  int res = 1;
  while (n > 1) {
    if ((n / p) & 1) res = p - res;
    res = (long long)res * f[n % p] % p;
    n /= p;
  }
  return res;
}

If space is limited and storing all factorials is not feasible, we can also compute all factorials n! mod p that are actually used in the function calls, sort them, and then compute their values in one batch at the end, aggregating into the final result, avoiding storing all factorial values.

Prime Power Modulus Case

For prime power moduli, the approach is similar to the prime modulus case, only replacing Wilson's theorem with its generalization. The ±1 in the two results of this section specifically means: take 1 when modulus p = 2 and α ≥ 3, and take -1 otherwise.

Recurrence Formula

For a prime p and positive integers α, n,

\[ (n!)_{p} \equiv (\pm 1)^{\lfloor n/p^\alpha\rfloor}\cdot\left(\prod_{1\le j\le (n\bmod p^\alpha),\ j\perp p}j\right)\cdot(\lfloor n/p\rfloor!)_p\pmod{p^\alpha}. \]

Here, the ±1 is defined as in the generalization of Wilson's theorem.

Proof

The proof idea is exactly the same as in the prime modulus case. Let (k)_p denote the result of removing all powers of p from the prime factorization of k. Then,

\[ \begin{aligned} (n!)_p &= \prod_{1\le k\le n}(k)_p = \left(\prod_{1\le k\le n,\ k\perp p}(k)_p\right)\left(\prod_{1\le k\le\lfloor n/p\rfloor}(pk)_p\right) \\ &= \left(\prod_{i=0}^{\lfloor n/p^\alpha\rfloor-1}\prod_{1\le j\le p^\alpha,\ j\perp p}(ip^\alpha+j)_p\right)\left(\prod_{1\le j\le (n\bmod p^\alpha),\ j\perp p}(\lfloor n/p^\alpha\rfloor p^\alpha+j)_p\right)\left(\prod_{1\le k\le\lfloor n/p\rfloor}(k)_p\right)\\ &\equiv \left(\prod_{1\le j\le p^\alpha,\ j\perp p}j\right)^{\lfloor n/p^\alpha\rfloor}\cdot\left(\prod_{1\le j\le (n\bmod p^\alpha),\ j\perp p}j\right)\cdot(\lfloor n/p\rfloor!)_p\\ &\equiv (\pm 1)^{\lfloor n/p^\alpha\rfloor}\cdot\left(\prod_{1\le j\le (n\bmod p^\alpha),\ j\perp p}j\right)\cdot(\lfloor n/p\rfloor!)_p \pmod{p^\alpha}. \end{aligned} \]

Differences from the prime modulus case, besides possibly replacing -1 with ±1, include the data to be preprocessed. For prime power moduli, we need to precompute for all positive integers n up to p^α the product of all integers from 1 to n that are not multiples of p, i.e.,

\[ \prod_{1\le k\le n,\ k\perp p} k\bmod{p^\alpha}. \]

In the prime modulus case, this reduces to n! mod p, but this expression no longer applies in the general prime power case.

Below is an example of computing factorial remainders modulo a prime power to understand the above method:

Example

To compute (32!)_3 mod 9, we can perform the following recursive computation:

\[ \begin{aligned} (32!)_3 &= 1\times 2\times \underbrace{1}_{3} \times 4\times 5\times \underbrace{2}_{6}\times 7\times 8\times\underbrace{1}_{9}\\ &\quad\times 10\times 11\times\underbrace{4}_{12}\times 13\times 14\times\underbrace{5}_{15}\times 16\times 17\times\underbrace{2}_{18}\\ &\quad\times 19\times 20\times\underbrace{7}_{21}\times 22\times 23\times\underbrace{8}_{24}\times 25\times 26\times\underbrace{1}_{27}\\ &\quad\times 28\times 29\times\underbrace{10}_{30}\times 31\times 32\\ &\equiv 1\times 2\times \underbrace{1}_{3} \times 4\times 5\times \underbrace{2}_{6}\times 7\times 8\times\underbrace{1}_{9}\\ &\quad\times 1\times 2\times\underbrace{4}_{12}\times 4\times 5\times\underbrace{5}_{15}\times 7\times 8\times\underbrace{2}_{18}\\ &\quad\times 1\times 2\times\underbrace{7}_{21}\times 4\times 5\times\underbrace{8}_{24}\times 7\times 8\times\underbrace{1}_{27}\\ &\quad\times 1\times 2\times\underbrace{1}_{30}\times 4\times 5\\ &=(1\times 2\times 4\times 5\times 7\times 8)^{3}\times (1\times 2\times 4\times 5)\\ &\quad\times\begin{pmatrix}\underbrace{1}_{3}\times\underbrace{2}_{6}\times\underbrace{1}_{9}\times\underbrace{4}_{12}\times\underbrace{5}_{15}\times\underbrace{2}_{18}\\\times\underbrace{7}_{21}\times\underbrace{8}_{24}\times\underbrace{1}_{27}\times\underbrace{1}_{30}\end{pmatrix}\pmod{9}. \end{aligned} \]

The decomposition of (32!)_3 mod 9 can also be divided into three parts:

Complete blocks: the product of all integers from 1 to 9 not divisible by 3, with ⌊32/9⌋ = 3 blocks;
Incomplete tail block: the product of all integers not divisible by 3 from 1 up to 32 mod 9;
The product of all integers divisible by 3. Comparing with the second-to-last equality, this is its first ⌊32/3⌋ = 10 terms, i.e., (⌊32/3⌋!)_3 mod 9.

The last parentheses can be solved recursively, thus transforming the original problem into a smaller one.

Thus, we obtain the following recurrence result:

Recurrence Result

For a prime p and positive integers α, n,

\[ (n!)_p \equiv (\pm 1)^{\sum_{j\ge\alpha}\lfloor{n}/{p^j}\rfloor}\prod_{j\ge 0}F(\lfloor n/p^j\rfloor\bmod p^\alpha), \]

where F(m) = ∏_{1 ≤ k ≤ m, k ⟂ p} k mod p^α, and ±1 is defined as above.

Implementation for prime power moduli is similar to the prime modulus case, with only minor differences. As above, preprocessing can also be moved outside the function.

Reference Implementation

// Calculate (n!)_p mod pa.
int factmod(int n, int p, int pa) {
  // Pretreatment.
  std::vector<int> f(pa);
  f[0] = 1;
  for (int i = 1; i < pa; ++i) {
    f[i] = i % p ? (long long)f[i - 1] * i % pa : f[i - 1];
  }
  // Recursion.
  bool neg = p != 2 || pa <= 4;
  int res = 1;
  while (n > 1) {
    if ((n / pa) & neg) res = pa - res;
    res = (long long)res * f[n % pa] % pa;
    n /= p;
  }
  return res;
}

Preprocessing time complexity is O(p^α), and single query time complexity is O(log_p n).

Computing the Exponent

This section discusses the computation of the exponent ν_p(n!) of p in the factorial n!, which can be used to compute binomial coefficients modulo a modulus. In binomial coefficients, factorials appear in both numerator and denominator, and whether the prime p cancels between numerator and denominator becomes an important factor determining the final remainder.

Legendre's Formula

The exponent of a prime p in the factorial n! can be computed by Legendre's formula, and it is related to the representation of n in base p.

Legendre's Formula

For a positive integer n, the exponent ν_p(n!) of prime p in the factorial n! is

\[ \nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \dfrac{n}{p^i} \right\rfloor = \dfrac{n-S_p(n)}{p-1}, \]

where S_p(n) is the sum of digits of n in base p. In particular, the exponent of 2 in the factorial is ν_2(n!) = n - S_2(n).

Proof

Since

\[ n! = 1\times 2\times \cdots \times p\times \cdots \times 2p\times \cdots \times \lfloor n/p\rfloor p\times \cdots \times n. \]

The product of multiples of p is p × 2p × ... × ⌊n/p⌋ p = p^{⌊n/p⌋} ⌊n/p⌋!, and ⌊n/p⌋! may continue to contain multiples of p. So for the exponent, we have the recurrence:

\[ \nu_p(n!) = \lfloor n/p\rfloor + \nu_p(\lfloor n/p\rfloor!). \]

Expanding this gives Legendre's formula.

To prove the second equality, first expand n in base p, which is equivalent to writing it as the sum:

\[ n = n_\ell p^{\ell} + \cdots + n_1 p + n_0 = \sum_{k=0}^\ell n_kp^k. \]

Therefore,

\[ \begin{aligned} \nu_p(n!) &= \sum_{i=1}^{\ell}\left\lfloor\dfrac{n}{p^i}\right\rfloor = \sum_{i=1}^\ell\sum_{k=i}^{\ell}n_kp^{k-i} = \sum_{k=1}^\ell n_k\sum_{i=1}^kp^{k-i} \\ &= \sum_{k=1}^\ell n_k\dfrac{p^k-1}{p-1} = \dfrac{\sum_{k=0}^\ell n_kp^k - \sum_{k=0}^\ell n_k}{p-1} = \dfrac{n - S_p(n)}{p-1}. \end{aligned} \]

A reference implementation for computing the exponent of a prime in factorial is as follows:

Reference Implementation

// Obtain multiplicity of p in n!.
int multiplicity_factorial(int n, int p) {
  int count = 0;
  do {
    n /= p;
    count += n;
  } while (n);
  return count;
}

Its time complexity is O(log n).

Kummer's Theorem

The result of a binomial coefficient modulo a number often forms fractal structures; for example, the Sierpinski triangle can be obtained from binomial coefficients modulo 2.

If analyzed carefully, whether p divides a binomial coefficient is related to whether subtraction of the upper and lower indices in base p requires borrowing. This leads to Kummer's theorem.

Kummer's Theorem

The exponent of a prime p in the binomial coefficient \binom{m}{n} is exactly the number of borrows required when subtracting n from m in base p, i.e.,

\[ \nu_p\left(\dbinom{m}{n}\right)=\frac{S_p(n)+S_p(m-n)-S_p(m)}{p-1}. \]

In particular, the exponent of 2 in the binomial coefficient is ν_2\left(\binom{m}{n}\right) = S_2(n) + S_2(m-n) - S_2(m).

Proof

First prove the following expression. Using Legendre's formula, we have

\[ \begin{aligned} \nu_p\left(\dbinom{m}{n}\right) &=\nu_p(m!)-\nu_p(n!)-\nu_p((m-n)!)\\ &=\sum_{i=1}^\infty\left(\left\lfloor\dfrac{m}{p^i}\right\rfloor-\left\lfloor\dfrac{n}{p^i}\right\rfloor-\left\lfloor\dfrac{m-n}{p^i}\right\rfloor\right)\\ &=\frac{S_p(n)+S_p(m-n)-S_p(m)}{p-1}. \end{aligned} \]

This expression can be interpreted as the number of borrows required when subtracting n from m in base p. Because if at the i-th digit (lowest digit index 1) there is insufficient subtraction requiring a borrow, then the digits before the i-th digit in the subtraction result, ⌊(m-n)/p^i⌋, are actually the digits before the i-th digit in m, ⌊m/p^i⌋, minus one (the borrowed one), minus the digits before the i-th digit in n, ⌊n/p^i⌋. So the difference

\[ \left\lfloor\dfrac{m}{p^i}\right\rfloor-\left\lfloor\dfrac{n}{p^i}\right\rfloor-\left\lfloor\dfrac{m-n}{p^i}\right\rfloor = 1 \]

if and only if a borrow occurs; otherwise, the difference is 0. Therefore, the summation in the above expression can be interpreted as the number of borrows. This gives the verbal statement of Kummer's theorem.

Example Problems

Problem HDU 2973 - YAPTCHA

Given n, compute

\[ \sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor \]

Solution

If 3k+7 is prime, then

\[ (3k+6)!\equiv-1\pmod{3k+7} \]

Let (3k+6)!+1 = k(3k+7)

Then

\[ \left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\left\lfloor k-\left\lfloor k-\frac{1}{3k+7}\right\rfloor\right\rfloor=1 \]

If 3k+7 is not prime, then (3k+7) | (3k+6)!, i.e.,

\[ (3k+6)!\equiv 0\pmod{3k+7} \]

Let (3k+6)! = k(3k+7), then

\[ \left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\left\lfloor k+\frac{1}{3k+7}-k\right\rfloor=0 \]

Therefore,

\[ \sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\sum_{k=1}^n[3k+7\text{ is prime}] \]

Reference Code

#include <iostream>

constexpr int M = 1e6 + 5, N = 3 * M + 7;

bool not_prime[N];
int sum[M];

int main() {
  for (int i = 2; i < N; ++i)
    if (!not_prime[i])
      for (int j = 2; j * i < N; ++j) not_prime[j * i] = true;
  for (int i = 1; i < M; ++i) sum[i] = sum[i - 1] + !not_prime[3 * i + 7];

  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::cout << sum[n] << std::endl;
  }
}

References

Feng Keqin. Elementary Number Theory and Its Applications.
Wilson's theorem - Wikipedia
Legendre's formula - Wikipedia

This page is mainly translated from the blog post Вычисление факториала по модулю and its English translation Factorial modulo p. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0. The content has been modified.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用