How to evaluate $\binom{n}{k}\bmod{m}$

Question

Hey I am trying to evaluate, $\binom{n}{k}\bmod m$. I know that to evaluate multiplication modulo I can evaluate it as follows, $(x_1 x_2 x_3\cdots x_n) \bmod m = ((x_1 x_2)\bmod{m})\cdot x_3)\bmod m\cdots$. But to evaluate $\dfrac{x_n x_{n-1} \cdots x_{n-k-1}}{x_1 x_2\cdots x_k} \bmod m$ I have a denominator part which I am not sure how to evaluate.

Please provide some hints or guide me on how to proceed from here.

Answer 1

There are 3 ways i can think of.

Method 1
Use recurrence relation. ${n \choose k}\%m = ({n-1 \choose k-1} + {n-1 \choose k}) \% m$

Required base cases,
${n \choose 0}=1$
${n \choose n}=1$ .

Advantages

• Independent of m being prime or not.
• Simple to implement using recursion.

Disadvantages

• Slow in terms of computation, linear number of operations required.

Method 2
This might be an overkill for your purpose.
Re-write recurrence in method 1 in form of 2D transformation matrix. Then use logarithmic power exponentiation with modulo to find out in logarithmic nos of operations. I am assuming this is an overkill, will workout transformation matrix in case you are looking for this solution.

Advantages

• Fastest of all.
• Doesn't assumes m is prime

Disadvantages

• Overkill probably.
• Time consuming

Method 3
We can use Fermat's Little theorem if $m$ is prime. So you can use your solution described while handling the denominator this way.
$a^{-1} \equiv a^{m-2} \pmod m$ So basically $a/b \pmod m = a*b^{-1} \pmod m$. Now you can use Fermat's Little theorem.
Kindly point out if you find anything incorrect,my first answer :)

Answer 2

Here's another way that's not very fast (or slow) but is pretty straightforward to implement. Let $P=\{p_1,p_2,\dots,p_t\}$ be the distinct prime factors of $m$.

Let $b=\binom{n}{k}$, then $$ (k!)b = n(n-1)(n-2)\cdots (n-k+1) $$ Since $b$ is an integer, every prime power in $k!$ divides the right hand side. For each prime $p$ in $P$, factor out the prime power on the LHS and RHS, then divide both sides by the LHS. So all these primes end on the RHS.

After doing this for all primes in $P$, for the left hand side you get $$ b\frac{k!}{f} = bc $$ for some factor $f$ that has been divided out. Now $(k!)/f = c$ is coprime to $m$ so you can take inverse to find $b$, i.e. $$ b \equiv \frac{n(n-1)(n-2)\cdots (n-k+1)}{f} \left(\frac{k!}{f}\right)^{-1} \pmod m $$

Here is a straightforward (but non-optimized) pseudocode for how you would do this:

binomial_mod(n,k,m):
P={distinct prime factors of m}
L = Array[k+1]
R = Array[k+1]

//Initialize factors on left hand side and right hand side.
For i = 1, i<= k, i++:
$\qquad$L[i] = i
$\qquad$R[i] = N+1-i

//Find product mod m due to primes dividing m.
prod = 1
For p in P:
$\qquad$exponent = 0
$\qquad$//Divide out p from arrays and move them to RHS.
$\qquad$//RHS contribute +1 for each p, LHS removes 1 for each p.
$\qquad$For i = 1, i<= k, i++:
$\qquad$$\qquad$While(R[i]%p==0):
$\qquad$$\qquad$$\qquad$R[i] = R[i] / p
$\qquad$$\qquad$$\qquad$exponent = exponent + 1
$\qquad$$\qquad$While(L[i]%p==0):
$\qquad$$\qquad$$\qquad$L[i] = L[i] / p
$\qquad$$\qquad$$\qquad$exponent = exponent - 1
$\qquad$prod = (prod * power_mod(p,exponent,m)) % m

//Find product mod m for remaining factors in arrays.
prodL = 1
prodR = 1
For i = 1, i<=k, i++:
$\qquad$prodL = (prodL * L[i]) % m
$\qquad$prodR = (prodR * R[i]) % m

//Product is (RHS * LHS^-1 * prod) % m
prod = (prod * prodR * multiplicative_inverse(prodL,m)) % m

Ideally you want to use a sieving method for the prime powers extraction. For example, if $(n,k)=(1001,101)$ and $p=7$ is one of the primes of $m$, then you know to divide out primes from $\{7,14,21,\dots,98\}$ and $\{1001,994,987,\dots,903\}$ since those are the integers divisible by $7$. This would reduce the trial divisions.

It is also possible to not require two large arrays and deal only with one at a time.