Calculating nCr modulo p, a prime

Question

I'm trying to compute nCr modulo p, where p is a prime.

One approach I've tried is to compute n! / (r! * (n-r)!) modulo p using multiplicative inverses, but this fails when either r or n - r is greater than or equal to p, since then the factorials are zero modulo p and the inverses don't exist.

What method works in all cases and not just when multiplicative inverses exist?

Answer 1

I'd use Lucas's theorem

C(14,1), p=13
N = 14 = 1 * 13 + 1
K = 1  = 0 * 13 + 1
C(N,K) mod p = (C(1,0) mod 13 ) * (C(1,1) mod 13) = 1

Answer 2

Calculating nCr modulo p,p is prime number

1. pre-calculate the factorial of n modulo p using
   fact[n]=n*fact[n-1]%p
   
2. pre-calculate inverse of factorial of n modulo p, using
   invfact[n] = modular_inverse(n)*infact[n-1]%p
   
   modular_inverse can be easily found out by using Fermat's little theorem or Extended Euclidean algorithm.(As p is prime number both can be used)
   
3. Get the nCr by multiply fact[n]*infact[r]*infact[n-r]%p
   
   

Another Method: You can also use pascal method to calculate nCr

As, for any nCr,you can use

row[0]=1;
for(i=1;i<n/2;i++)
{
   row[i]=row[i-1]*(n-i+1)/i
}

for(i=n/2;i<=n;i++)
{
   row[i]=row[n-i]
}

In this you have to take modulo_inverse of (i) using any of the above way( Fermat's little theorem or Extended Euclidean algorithm )

Reference: Best known algos for calculating nCr % M