Special factorial modulo p

Let $n!_{% p}$ be a special factorial where $n!$ is divided by the maximum exponent of $p$ that divides $n!$

n!_{% p} = \frac{n!}{d_{p} (n!)}

Where $d_{p} (n!)$ is called Legendre’s Formula which is explained in detail in this article

Compute $n!_{% p} (\mod p)$ given that $p$ is a prime number

First let’s write this special factorial explicitly

\begin{matrix} (1) & n!_{% p} = \frac{1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot p \cdot (p + 1) \cdot \dots \cdot (2 p - 1) \cdot 2 p \cdot (2 p + 1) \cdot \dots \cdot (k p - 1) \cdot k p \cdot (k p + 1) \cdot \dots \cdot (n - 1) \cdot n}{p^{\frac{n}{p} + \frac{n}{p^{2}} + . . .}} \end{matrix}

The number $k p$ is a number that is divisible by $p$ , we also see that $k$ might be a composite number that could be divisible by $p$ again

Now let’s first divide the equation by $p^{\frac{n}{p}}$ which is exactly the number of multiples of $p$

n!_{% p} = \frac{1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot 1 \cdot (p + 1) \cdot \dots \cdot (2 p - 1) \cdot 2 \cdot (2 p + 1) \cdot \dots \cdot (k p - 1) \cdot k \cdot (k p + 1) \cdot \dots \cdot (n - 1) \cdot n}{p^{\frac{n}{p^{2}} + . . .}}

If we apply the modulo operation to each term except the multiples of $p$ we have

n!_{% p} = \frac{1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot 1 \cdot 1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot 2 \cdot 1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot p \cdot 1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot k p}{p^{\frac{n}{p^{2}} + . . .}} \cdot 1 \cdot 2 \cdot \dots \cdot (n - 1) \cdot n

NOTE: we’re not applying the modulo operator to each multiple of $p$ because they don’t actually exist since there are no $p$ factors in the equation, they are reduced with posterior divisions by $p^{\frac{n}{p^{i}}}$

NOTE: the number $k p$ described in $(1)$ just denotes a multiple of $p$

We see that the expression $1 \cdot 2 \cdot \dots \cdot (p - 1)$ is repeated many times in the equation above + a product of some additional terms which don’t form an entire sequence, let $c = 1 \cdot 2 \cdot \dots \cdot (p - 1)$ then

n!_{% p} = \frac{1 c \cdot 2 c \cdot \dots \cdot (p - 1) c \cdot p c \cdot (p + 1) c \cdot \dots \cdot (k p - 1) c \cdot k p c}{p^{\frac{n}{p^{2}} + . . .}} \cdot 1 \cdot 2 \cdot \dots \cdot (n - 1) \cdot n

Since each $c$ factor occurs in every contiguous sequence of length $p$ there are exactly $⌊ \frac{n}{p} ⌋$ $c$ factors, factoring $c$ we have

n!_{% p} = c^{⌊ \frac{n}{p} ⌋} \cdot \frac{1 \cdot 2 \cdot \dots \cdot (p - 1) \cdot p \cdot (p + 1) \cdot \dots \cdot (2 p - 1) \cdot 2 p \cdot (2 p + 1) \cdot \dots \cdot (k p - 1) \cdot k p}{p^{\frac{n}{p^{2}} + . . .}} \cdot 1 \cdot 2 \cdot \dots \cdot (n - 1) \cdot n

Note that the term multiplying $c^{⌊ \frac{n}{p} ⌋}$ is the same as $(1)$ , we now have to divide it by $p^{\frac{n}{p^{2}}}$ which is exactly the number of multiples of $p^{2}$ (NOTE: $k p$ is a multiple of $p$ but might/might not be a multiple of $p^{2}$ )

This observation leads to a recursive implementation

Complexity: $O (p, l o g_{p} n)$

long long special_factorial_mod_p(long long n, long long p) {
  long long res = 1;

  // computation of c
  long long c = p-1;

  while (n > 1) {
    res = (res * binary_exponentiation_modulo_m(c, n / p, p)) % p;
    for (long long i = 2; i <= n % p; i += 1) {
      res = (res * (long long)i) % p;
    }
    n /= p;
  }
  return res % p;
}

Applications

Finding the value of $n C r$

We can quickly calculate the value of $n C r$ , we can compute the maximum exponents of $p$ in $n!$ , $(n - r)!$ and $r!$ , let those numbers be $p^{a}$ , $p^{b}$ and $p^{c}$ then $n C r$ can be expressed as

n C r = (\binom{p^{a} \cdot \dots}{p^{b} \cdot p^{c} \dots})

Which means that $n C r$ will be a multiple of $p$ when $a - b - c > 0$ , if $a - b - c = 0$ then the number is equal to

n C r = \frac{n!_{% p}}{(n - r)!_{% p} \cdot r!_{% p}}

NOTE: $a - b - c$ can never be less than zero, that would imply that $n C r$ is not an integer

The denominator can be found using the modular multiplicative inverse of $(n - r)!_{% p}$ and $r!_{% p}$

long long nCr_mod_p(int n, int r, int p) {
  int a = max_power_in_factorial(n, p);
  int b = max_power_in_factorial(n - r, p);
  int c = max_power_in_factorial(r, p);
  if (a > b + c) {
    return 0;
  }

  return (special_factorial_mod_p(n, p) *
    ((modular_multiplicative_inverse(special_factorial_mod_p(n - r, p), p) *
    modular_multiplicative_inverse(special_factorial_mod_p(r, p), p)) % p) % p);
}

Problems to solve

Codechef - CB01

Applications

Finding the value of nCr

Problems to solve

See Also

Integer Factorization

Euler's phi function

Divisor Function

Finding the value of $n C r$