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

Правка en3, от rembocoder, 2023-03-11 20:25:19

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.

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

const int mod = 998244353;

int bin_exp(int a, int b) {
    if (b == 0) {
        return 1;
    }
    if (b % 2) {
        return bin_exp(a, b - 1) * a % mod;
    }
    int res = bin_exp(a, b / 2);
    return res * res % mod;
}

int inv(int a) {
    return bin_exp(a, mod - 2);
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int a, b;
    cin >> a >> b;
    cout << a * inv(b) % mod << '\n';
}

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.

Теги modular inverse, number theory, modular arithmetic, combinatorics

История

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