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
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)
, wherep
is the maximal integer number such thatB
is divisible byM
to the power ofp
; andr
is the remainder ofB / M^p
moduloM
. We must storeA
the same way.Now if you need to divide
A
byB
and you are sure thatA
is divisible byB
, you can do the following.If
A
is stored as(p_A, r_A)
andB
is stored as(p_B, r_B)
then you subtractp_B
fromp_A
and multiplyr_A
by the modular inverse ofr_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
\(^▽^)/