Hello,
You can use Lucas' theorem :
If you write
Then
It is nice, isn't it ?
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.
Please provide some guidance.
Thanks for your patience.