AIOJ

Introduction

This article discusses results concerning factorials modulo a given modulus and presents a method whose time complexity is linear in the modulus, so it is mainly suitable for relatively small moduli ( $\sim 10^6$ ). Depending on the setting, polynomial techniques can also be used for fast computation.

By the Chinese remainder theorem, the factorial modulo problem can be reduced to the case where the modulus is a prime power $p^\alpha$ . When handling such problems, it is often necessary, for a prime $p$ and positive integer $n$ , to extract from the factorial $n!$ all factors $p$ , yielding the decomposition:

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

Here, $\nu_p(n!)$ denotes the exponent in the prime factorization of $n!$ of $p$ , while $(n!)_p$ denotes the integer obtained from $n!$ after removing all powers of $p$ . This article discusses how to compute the residue of $(n!)_p$ modulo a prime (or prime power) and the exponent $\nu_p(n!)$ .

This decomposition is especially useful when factorials occur in both the numerator and denominator of an expression, for example when computing a binomial coefficient modulo a given modulus. In such problems, the powers of $p$ in the numerator and denominator can be subtracted directly, while the part coprime to $p$ , $(n!)_p$ , can be computed using a multiplicative inverse.

This article also introduces Wilson's theorem and its generalization, Legendre's formula, Kummer's theorem, and other related results.

Wilson's theorem

Wilson's theorem gives a necessary and sufficient condition for determining whether a natural number is prime.

Wilson's theorem

For a natural number $n>1$ , $n$ is prime if and only if $(n-1)!\equiv -1\pmod n$ .

Proof

First, for a prime $p$ , prove $(p-1)!\equiv -1\pmod{p}$ . This can be shown by either of two concise proofs using a congruence equation or a primitive root; the details are omitted here. We give below a proof requiring less background knowledge:

When $p=2$ , the statement is obvious. Now assume $p\geq 3$ ; we must show that the product of all nonzero elements (that is, residue classes) in $\mathbf{Z}_p$ is $\overline{-1}$ . Every nonzero element of $\mathbf{Z}_p$ , $\overline{a}$ , has an inverse $\overline{a}^{-1}$ , so the products of mutually inverse elements in $\mathbf{Z}_p$ are $\overline{1}$ . However, $\overline{a}$ and $\overline{a}^{-1}$ may be equal: $\overline{a}=\overline{a}^{-1}$ if and only if $a^2\equiv 1\pmod p$ , namely

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

Therefore, $a\equiv 1\pmod p$ or $a\equiv -1\pmod p$ . This shows that the product of all elements in $\mathbf{Z}_p\setminus\{\overline{0},\overline{1},\overline{-1}\}$ is $\overline{1}$ , and hence the product of all nonzero elements in $\mathbf{Z}_p$ is $\overline{-1}$ .

Conversely, for a composite number $n$ , we prove that $(n-1)!\not\equiv-1\pmod{n}$ . By contradiction, suppose $(n-1)!\equiv -1\pmod{n}$ , so there is an integer $k$ such that $(n-1)!=kn-1$ . Since $n$ is composite, there is a prime $p<n$ such that $n=pm$ , and therefore $(n-1)!=kpm-1\equiv -1\pmod{p}$ . But the product $(n-1)!$ necessarily contains $p$ , so $(n-1)!\equiv 0\pmod{p}$ . This contradiction proves that $(n-1)!\not\equiv-1\pmod{n}$ .

Using the notation of this article, Wilson's theorem can be written as $(p!)_p\equiv -1\pmod{p}$ .

Generalization

Wilson's theorem can be generalized to arbitrary 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 $\pm 1$ in the remainder takes the value $-1$ if and only if, for modulus $m$ , a primitive root exists, that is, when $m=2,4,p^\alpha,2p^\alpha$ , where $p$ is an odd prime and $\alpha$ is a positive integer.

Proof

This theorem follows readily from the structure of the multiplicative group of integers modulo $n$ . Here we give a proof with a similar idea but more elementary details.

For $m=2$ , we have $1!=1\equiv -1\pmod{2}$ . For the other cases where primitive roots exist, let the primitive root be $g$ . Every positive integer less than $m$ and coprime to it, denoted by $k$ , can be uniquely represented as $g^i\bmod m$ , where $0\le i<\varphi(m)$ and $\varphi(m)$ is the Euler totient function. It is easy to verify that $\varphi(m)$ is always even. Since $g^i$ and $g^{\varphi(m)-i}$ are multiplicative inverses, pair them in the product to obtain

\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^{\varphi(m)/2}\bmod m$ is the unique element other than $1\bmod{m}$ whose multiplicative inverse is itself, it must equal $-1\bmod{m}$ . Thus, the remainder in this case is $-1$ .

For the case where no primitive root modulo $m$ exists, we prove that the remainder is $1$ . First factor $m=p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}$ , and then the Chinese remainder theorem shows that it suffices to prove

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

This holds for every factor $p_j^{e_j}$ . The Chinese remainder theorem states that every possible residue tuple $(r_1,r_2,\cdots,r_s)$ , where $1\le r_j<p_j^{e_j}$ and $p_j\perp r_j$ , corresponds uniquely to a $1\le k<m$ with $k\perp m$ and $k\equiv r_j\pmod{p_j^{e_j}}$ . Therefore, for a given residue $r_j$ , exactly ${\varphi(m)}/{\varphi(p_j^{e_j})}$ values of $k$ satisfy $k\equiv r_j\pmod{p_j^{e_j}}$ . Grouping the product using this fact gives

\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}}.

For the exponent ${\varphi(m)}/{\varphi(p_j^{e_j})}=\varphi(m/p_j^{e_j})$ to be odd, it is necessary that $m/p_j^{e_j}=1,2$ , because the Euler function $\varphi(n)$ is even for every $n\ge 3$ . If $p_j$ is an odd prime, then because no primitive root modulo $m$ exists, we must have $m/p_j^{e_j}\neq 1,2$ . If $p_j^{e_j}=2,4$ , then because no primitive root modulo $m$ exists, $m/p_j^{e_j}$ must contain an odd prime factor and hence be greater than $2$ . In both cases, the exponent ${\varphi(m)}/{\varphi(p_j^{e_j})}$ is even. The term in parentheses above has already been proved to be $p_j^{e_j}$ -congruent to $-1$ , so this power is $p_j^{e_j}$ -congruent to $1$ . The only remaining case is $p_j=2$ and $e_j>2$ ; for this case, we can directly prove `

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

Following the proof idea above, for $1\le r_j<2^{e_j}$ , pair off and cancel the odd integers $r_j$ . Those that cannot be paired must be solutions of $x^2\equiv 1\pmod{2^{e_j}}$ . This equation means $2^{e_j}\mid (x-1)(x+1)$ . Let $x=2y+1$ ; then $2^{e_j-2}\mid y(y+1)$ . Since $y$ and $y+1$ have opposite parity, we have $y=t2^{e_j-2}$ or $y=t2^{e_j-2}-1$ . Hence $x=t2^{e_j-1}\pm 1$ for an integer $t$ . Among the residues modulo $2^{e_j}$ , the only four are $\pm 1$ and $2^{e_j-1}\pm 1$ . 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 computations, the case where the modulus is a prime power is particularly important:

Corollary

For a prime $p$ and a positive integer $\alpha$ ,

\prod_{1\le k \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^\alpha!)_p$ , because the latter must also account for the contribution of multiples of $p$ .

Computing factorial residues

This section discusses how to compute $(n!)_p\bmod p^{\alpha}$ .

The prime-modulus case

The expression $(n!)_p$ has an evident recursive structure. To see this, first consider a concrete example:

Example

To compute $(32!)_5 \bmod{5}$ , we can proceed recursively:

\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}

We can see that, using the periodicity of residues modulo $5$ , this product can be divided into blocks of length $5$ , with the only difference between blocks being the residue of the last element. Since dividing $32$ 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$ . Thus, we can extract the part of the first $6$ blocks except for their last elements (which is exactly what Wilson's theorem handles), multiply by the product of the final incomplete block, and finally multiply by the product of the last elements of the first $6$ blocks. The last element of every block is a multiple of $5$ ; after removing powers of $5$ , their product is exactly $(6!)_{5}\pmod{5}$ . This reduces the original problem to a smaller one.

Generalizing the recursive structure in this example gives the following recurrence:

Recurrence

For a prime $p$ and a 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 $(n)_p$ be the result obtained from $n$ by removing all powers of $p$ from its prime factorization. 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/p\rfloor p+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. We now give a concrete explanation of this form of the proof.

To compute the value of $(n!)_p\bmod 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}

It is clear that, except for the final 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}

Apart from the last element of each block, the main part of a complete block, $(p-1)!\ \mathrm{mod}\ p$ , is easy to compute; Wilson's theorem gives

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

There are $\left\lfloor \dfrac{n}{p} \right\rfloor$ complete blocks, so we must place $\left\lfloor \dfrac{n}{p} \right\rfloor$ in the exponent of $-1$ .

The value of the final partial block is $(n\bmod p)!\bmod p$ , which can be computed separately.

What remains are the last elements of the blocks. If we hide the elements already processed, we can 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 the parts together gives the recurrence above.

Using this recurrence, the recursion depth is $O(\log_p n)$ . If the intermediate term is recomputed at every step, each level has complexity $O(p)$ and the total time complexity is $O(p\log_p n)$ . If, for all $n=1,2,\cdots,p-1$ , $n!\bmod p$ is precomputed, the preprocessing complexity is $O(p)$ , each level has complexity $O(1)$ , and the total time complexity is $O(p+\log_p n)$ .

In an implementation, this is a tail recursion and can be implemented iteratively. The implementation below precomputes the first $p-1$ factorials; if it is called many times, 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 it is impossible to store all factorials, we can compute the $n!\bmod p$ values actually used by the function calls, sort the corresponding $n$ values, and then compute these factorials all at once at the end, combining them into the final result without storing every factorial value.

The prime-power-modulus case

The prime-power-modulus case can be handled similarly to the prime-modulus case, replacing Wilson's theorem with its generalized form. In the two conclusions in this section, $\pm 1$ is defined specifically as follows: when the modulus satisfies $p=2$ and $\alpha\ge 3$ , its value is $1$ , and otherwise its value is $-1$ .

Recurrence

For a prime $p$ and positive integers $\alpha,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}.

The value of $\pm 1$ is defined as in the generalization of Wilson's theorem above.

Proof

The proof is exactly analogous to the prime-modulus case. Let $(k)_p$ be the result obtained from $k$ by removing all powers of $p$ from its prime factorization. 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}

The difference from the prime-modulus case is not only that $-1$ may need to be replaced by $\pm 1$ , but also that the data to be precomputed is different. For a prime-power modulus, for every positive integer not exceeding $p^\alpha$ , namely $n$ , we need to precompute the product of all integers from $1$ to $n$ that are not multiples of $p$ , namely

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

For a prime modulus, this degenerates to $n!\bmod p$ , but this expression is no longer applicable for a general prime power.

The following example computes a factorial residue modulo a prime power to illustrate the method above:

Example

To compute $(32!)_3\bmod 9$ , we can proceed recursively:

\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 the expression for $(32!)_3\bmod 9$ can likewise be divided into three parts:

Complete blocks: the product of all integers between $1\sim 9$ that are not divisible by $3$ , with a total of $\lfloor 32/9\rfloor=3$ blocks;
Incomplete tail block: multiply all integers not divisible by $3$ from $1$ through $32\bmod 9$ ;
The product of all integers divisible by $3$ . Comparing it with the result at the penultimate equality, we see that this is the first $\lfloor 32/3\rfloor=10$ terms, namely $(\lfloor 32/3\rfloor!)_3\bmod 9$ .

The recurrence in the final parentheses can be solved recursively, reducing the original problem to a smaller one.

Thus, we obtain the following recurrence result:

Recurrence result

For a prime $p$ and positive integers $\alpha,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) = \prod_{1\le k\le m,\ k\perp p} k\bmod{p^\alpha}$ , and the value of $\pm 1$ is the same as above.

The implementation for a prime-power modulus is similar to that for a prime modulus, with only a few details differing. As above, the precomputation 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;
}

The preprocessing time complexity is $O(p^\alpha)$ , and the time complexity of a single query is $O(\log_p n)$ .

Computing exponents

This section discusses the factorial $n!$ and the exponent of $p$ in it, denoted by $\nu_p(n!)$ ; it can be used to compute binomial-coefficient residues. Since factorials occur in both the numerator and denominator of a binomial coefficient, whether the powers of the prime $p$ in them cancel becomes an important factor determining the final residue.

Legendre's formula

The factorial $n!$ has an exponent of the prime $p$ that can be computed using Legendre's formula, and this exponent is related to the representation of $n$ in base $p$ .

Legendre's formula

For a positive integer $n$ , the factorial $n!$ contains the prime $p$ to the power $\nu_p(n!)$ ,

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

Here, $S_p(n)$ is the sum of the base- $p$ digits of $n$ . In particular, the power of $2$ in a factorial is $\nu_2(n!)=n-S_2(n)$ .

Proof

Because

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 the multiples of $p$ is $p\times 2p\times \cdots \times \lfloor n/p\rfloor p=p^{\lfloor n/p\rfloor }\lfloor n/p\rfloor !$ , while $\lfloor n/p\rfloor !$ may contain further multiples of $p$ . Therefore, the exponents satisfy the recurrence

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

Expanding it gives Legendre's formula.

To prove the second equality, first expand $n$ in base $p$ , which is equivalent to writing it as the following 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}

The reference implementation for finding the exponent of a prime in a 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 reducing binomial coefficients modulo a number often forms a fractal structure; for example, the Sierpiński triangle can be obtained from binomial coefficients modulo $2$ .

A careful analysis shows that whether $p$ divides a binomial coefficient is related to whether subtracting the lower index from the upper index in base $p$ requires a borrow. This gives Kummer's theorem.

Kummer's theorem

The exponent of the prime $p$ in the binomial coefficient $\dbinom{m}{n}$ is exactly the number of borrows required when, in base $p$ , subtracting $m$ by $n$ , namely

\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 a binomial coefficient is $\nu_2\left(\dbinom{m}{n}\right)=S_2(n)+S_2(m-n)-S_2(m)$ .

Proof

We first prove the following expression. By Legendre's formula,

\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 understood as the number of borrows required when, in base $p$ , subtracting $m$ by $n$ . If, when computing digit $i$ (with the lowest digit indexed by $1$ ), the prefix before digit $i$ in the result, $\left\lfloor\dfrac{m-n}{p^i}\right\rfloor$ , is actually the prefix of $m$ before digit $i$ , $\left\lfloor\dfrac{m}{p^i}\right\rfloor$ , minus one (the borrowed one), minus the prefix of $n$ before digit $i$ , $\left\lfloor\dfrac{n}{p^i}\right\rfloor$ , 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 one borrow occurs; otherwise, this difference is $0$ . Therefore, the sum in the expression above can be understood as the number of borrows. This gives the verbal statement of Kummer's theorem.

Example problems

Example 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 idea

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)\mid(3k+6)!$ , that is,

(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 primarily 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.

Factorial Modulo

Introduction

Wilson's theorem

Generalization

Computing factorial residues

The prime-modulus case

The prime-power-modulus case

Computing exponents

Legendre's formula

Kummer's theorem

Example problems

References