Page 1 of 1

Computing n choose k modulo composite m

Posted: Sun Nov 09, 2014 4:12 pm
by [Iasi] georgepopoiu
Hello, I am trying to compute C(n, k) = n! / ( (n - k)! * k! ) mod m without using the recurrence relation C(n, k) = C(n - 1, k) + C(n-1, k-1).

m might be a composite number and we might have n >= m. I know how to do it mod p where p is prime and we have n < p, but in my case the modulus is composite and n can also be larger than the modulus... I have found some information on the web, but nothing explained clearly.

Can someone help me ?

Thanks in advance !

Re: Computing n choose k modulo composite m

Posted: Thu Aug 04, 2016 11:18 am
by lsonrdrt
GREAT POST