Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Modular Inverse / Inverse Remainder / Modular Division – A Quick Guide

Revision en4, by SirRembocodina, 2023-03-11 20:36:27

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 SirRembocodina 2023-03-11 20:36:27 709
ru4 SirRembocodina 2023-03-11 20:35:14 716
ru3 SirRembocodina 2023-03-11 20:28:48 151
en3 SirRembocodina 2023-03-11 20:25:19 142 Tiny change: 'number M and you' -> 'number M: A % M and B % M and you'
en2 SirRembocodina 2023-03-10 22:12:16 0 (published)
ru2 SirRembocodina 2023-03-10 22:11:59 34 (опубликовано)
ru1 SirRembocodina 2023-03-10 22:10:23 2008 Первая редакция перевода на Русский (сохранено в черновиках)
en1 SirRembocodina 2023-03-10 22:03:02 1995 Initial revision (saved to drafts)