### SirRembocodina's blog

By SirRembocodina, history, 9 months ago, I have found these articles, where it's already described:

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

https://codeforces.com/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.  Comments (9)
•  » » » How to find inverse modulo when B mod M = 0. If you can also add this into your blog, it would be very helpful.
•  » » » » 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.