rembocoder's blog

By rembocoder, history, 20 months ago, In English

I have found these articles, where it's already described:

https://codeforces.net/blog/entry/72527

https://codeforces.net/blog/entry/46620

They are both very good, but I want to write a more concise blog about the modular inverse specifically, as it is needed in many problems that don't even belong to number theory.

The Problem

There are two integer numbers A and B. Suppose you know that A is divisible by B. But they are very big, so you only know their remainders modulo some prime number M: A % M and B % M. You want to know the remainder of their quotient – (A / B) % M. But (A % M) may be not divisible by (B % M). What to do?

Such question is very common in combinatorical problems, for example when counting binomial coefficients, where you need to divide n! by k! and (n - k)!.

The solution

The short answer is you need to calculate B to the power of M - 2 modulo M (using binary exponentiation). The resulting number is called the modular inverse of B. Now you can multiply A by it to effectively divide it by B.

Note: this only works if B % M is not 0 and M is prime.

The implementation

If you don't use #define int int64_t
If you use #define int int64_t

The Proof

This is a well-known formula that relies on Fermat's little theorem and the fact that every non-zero element of the ring of remainders modulo prime number has exactly one multiplicative inverse. If you want to know more, you can read the aforementioned articles.

  • Vote: I like it
  • +40
  • Vote: I do not like it

| Write comment?
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

why all these downvotes?

  • »
    »
    20 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Maybe they didn't like how it was written. I've updated the post to make it clearer.

    My goal was not to write an excessive material, but just provide information that every participant is required to know to solve many of the CF problems.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to find inverse modulo when B mod M = 0. If you can also add this into your blog, it would be very helpful.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        There would be no inverse in the same way that multiplying by 0 has no inverse.

      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There is a way. Instead of just the remainder of B you need to store a pair of numbers (p, r), where p is the maximal integer number such that B is divisible by M to the power of p; and r is the remainder of B / M^p modulo M. We must store A the same way.

        Now if you need to divide A by B and you are sure that A is divisible by B, you can do the following.

        If A is stored as (p_A, r_A) and B is stored as (p_B, r_B) then you subtract p_B from p_A and multiply r_A by the modular inverse of r_B.

        I've never used it, but I think it should work.

    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Do you plan to upload YouTube video on certain topics? (Like number theory, probability or combinatorics?)