I have a conceptual doubt in modular multiplicative inverse for finding nCr%M that why M needs to be prime for Modular multiplicative inverse to be applied, I mean the condition is only that A and M should be coprime for the existence of inverse so M need not be prime for that. Am I missing something, Can you please explain the reason for M to be prime. Also if we get a number large enough and M is neither prime nor coprime, what are we supposed to use then. Thanks
1 Like
@vishesh_345, the condition for existence of modular multiplicative inverse of a number is that the number and the modulus should be coprime. Generally speaking, when M is prime it is possible to use Fermat’s little theorem to calculate the inverse, and when coprime the extended Euclidean algorithm may be used. There is also a way to precompute inverse values upto a range in linear time. You can refer to this page for more information on these methods.
The calculation of ^n C _r \% M is a common problem. When M is neither prime nor coprime but square-free, one can prime factorize M, use Lucas’s theorem to find the answer for all factors and reconstruct the answer using the Chinese remainder theorem. When M is NOT square-free, a generalization of Lucas theorem for prime powers can be applied. Refer to here and here for detailed explanations on ways to find ^n C _r \% M . Additionally, you can take a look at the problem SANDWICH of May Challenge 2017, which involved finding ^n C _r \% M for M \le 10^6 with no additional restrictions. The approach for solving it is discussed here.
2 Likes
Thanks a lot. It was really helpful. Method of precomputing inverse was great.
Can you please explain what this line means “M is NOT square-free” Is it so that M factors are repeating like (2,2,3,3). If it is so then it could not be a prime number. Please correct me if I am wrong.
Also it would be of great help if you could explain Chinese remainder theorem application (in layman language). Thanks again.
Yes, I will take care of it. I was not aware of the previous answer. Thanks:)
For n as large as 10^{18} and M non-prime, you will have to use the generalization of Lucas theorem for prime powers.
Prime factorisation of M=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}...p_{u}^{\alpha_{u}}
And after calculating ^{n}C_{r} \% p_{i}^{\alpha_{i}} for all 1<=i<=u, you will have to use Chinese remainder theorem to calculate ^{n}C_{r} \% M,
because p_{i}^{\alpha_{i}} and p_{j}^{\alpha_{j}} are coprime for i\not=j.
Lucas theorem for calculating ^{n}C_{r} \% p^{\alpha} is Theorem 1(page 2) in [this research paper][1]
Chinese remainder theorem
If x\equiv a_{i} $($mod m_{i}) for 1<=i<=r and
m_{i} are copime (gcd(m_{i},m_{j})=1 \forall i\not=j) then
$x\equiv a_{1}b_{1}\frac{M}{m_{1}}+…+a_{r}b_{r}\frac{M}{m_{r}}
($mod $M)$ where $M=m_{1}m_{2}..m_{r}$ and $b_{i}\frac{M}{m_{i}}\equiv 1
($mod m_{i}),
b_{i} is the multiplicative inverse of \frac{M}{m_{i}} modulo m_{i}
[1]: https://www.dropbox.com/s/h7665pcqto17pl4/BinCoeff.pdf?dl=0
2 Likes
Yes, that is correct. A square-free number is a number which does not have any perfect square as a factor other than 1. This also means that it will not have any repeated primes is its prime factorization.
Chinese remainder theorem allows us to find x\%M when x\%m_1, x\%m_2, … x\%m_r are known and m_1 \times m_2 \times... \times m_r=M. @prakhariitd has described it in his answer. You can find an implementation of CRT on geeksforgeeks.
I love how you address the issues so nicely!!
Thank you for the explanation. I will practice more questions to get better at it.
So, it is like we just have a different method to calculate the inverse of that number (in case M is not prime) and we after calculation of inverse we go by the same method fact[n]^(Inverse(fact[r])^Inverse(fact[n-r])).
Please Correct if i am wrong.
Thanks! 