Please subscribe to the official Codeforces channel in Telegram via the link ×

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:

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.

Tags modular inverse, number theory, modular arithmetic, combinatorics


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