# Thread: How to calculate nCr mod p where p is prime

1. ## How to calculate nCr mod p where p is prime

Hi,

In n and r are quite large so that calculating their factorial is somewhat infeasible, how would one approach to find the solution to nCr mod p (nCr stands for n choose r) where p is a prime number ?

simple example: n=17 , r= 7 p =3 answer =2;
But what if n and r are of the order 2*10^9 and 10^9 respectively and p is a prime number say 103.

2. Hello,

You can use Lucas' theorem :

If you write $\left\{\begin{array}{l}n=n_dp^d+n_{d-1}p^{d-1}+...+n_1p+n_0\\k=k_dp^d+k_{d-1}p^{d-1}+...+k_1p+k_0\end{array}\right.$

Then $\color{blue}\boxed{C_n^k\equiv C_{n_d}^{k_d}C_{n_{d-1}}^{k_{d-1}}...C_{n_1}^{k_1}C_{n_0}^{k_0}~\text{mod}~p}$

It is nice, isn't it ?