Chapter 126

Home

Modular Inverse

The modular inverse a⁻¹ mod M satisfies a × a⁻¹ ≡ 1 (mod M). Use Fermat's little theorem (a^(M−2) mod M) when M is prime, or extended Euclidean algorithm for any M where gcd(a, M) = 1.

Modular Inverse Methods

C++ — Fermat (M prime)

long long mod_inv(long long a, long long MOD) {
    return mod_pow(a, MOD - 2, MOD);  // binary exponentiation
}

C++ — Extended Euclidean (any M)

long long mod_inv(long long a, long long MOD) {
    long long x, y;
    long long g = extended_gcd(a, MOD, x, y);
    if (g != 1) return -1;  // inverse doesn't exist
    return (x % MOD + MOD) % MOD;
}

long long extended_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    long long x1, y1;
    long long g = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}