dragneel3131's blog

Calcuate (a/b) mod p when p is not prime
By dragneel3131, history, 7 years ago, In English

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.

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +6 Vote: I do not like it

As usual, blog about CodeChef long challenge problem.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
← Rev. 63   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply