I have to calculate the value of (a/b) mod p where p may or may not be a prime number. For p being prime, I can simply find (b inverse for mod p) using euclid theorem or little fermat theorem, and perfrom (a * inverse(b)) % p. But in case p is not prime, how can I find the solution? I think there is a method by doing prime factorization of p and then using chineese remainder theorem but not sure about it. Can anyone help how can I solve this problem?
a and b both are less than p.
As usual, blog about CodeChef long challenge problem.
https://cs3.interviewstreet.com/challenges/dashboard/#problem/50877a587c389 This is the problem link. Its from a past contest on interviewstreet. (Not able to edit the post so putting the link here).
I am trying to compute ncr mod p, for which i am using simple loop (on remainder after applying lucas), and inverse method is not working for p not being prime.
It's obviously related, but it's only a prerequisite in a quite hard problem and I don't think it's bad seeking help for it. Similarly, I wouldn't blame anyone for asking about Dijkstra's algorithm when there is a distances in graph problem in ongoing contest.
That said, the answer is so easy to google that I'd call this post spam.
What you really need is inverse modulo p for non prime p. Link : https://discuss.codechef.com/questions/1440/algorithm-to-find-inverse-modulo-m
I have heard of one idea, but I am not sure whether it can help or not.
Suppose that (a/b) mod p = r. Then, a/b=mp+r, i.e., a=bmp+br.
Thus, a mod (bp) = br mod (bp). Since r<p, i.e., br<bp, we have a mod (bp) = br.
Therefore, (a mod (bp))/b = br /b = r.
This is not coming out to be true in few cases like - suppose a = 4, b = 3 and p = 7. Now, inverse of 3 for mod 7 is = 5 as (3 * 5) % 7 = 1 so (a/b) mod p = (4 * 5) mod 7 = 6. which is correct answer. Now according to your formula - bp = 3 * 7 = 21. so (a mod bp)/b = (4 mod 21)/b = 4 / 3 = 1 != 6. So it is giving wrong answer. But your derivation seems correct, then whats the problem here?
Hmm, I'm sorry that perhaps I have missed some details in the arguments.
I think that equation holds under the condition that a is a multiple of b. For instance, when asked to calculate
mod 107, we can equivalently compute (7 * (1010000 - 1) mod (107 * 9))/9, where 1010000 can be calculated based on Fast Exponentiation Algorithm.