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.

why all these downvotes?

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.

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 would be no inverse in the same way that multiplying by 0 has no inverse.

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.

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

Yes

＼(＾▽＾)／

Looking forward to it ;)