Modular Inverse

Aritmetika modulo mendukung penjumlahan, pengurangan, dan perkalian dengan baik — tetapi pembagian tidak langsung tersedia. Untuk membagi a dengan b modulo m, kita perlu mengalikan a dengan invers perkalian b (yaitu bilangan b⁻¹ sehingga b · b⁻¹ ≡ 1 mod m). Pada Chapter ini kita menurunkan dua metode utama: Fermat’s little theorem (untuk modulus prima) dan Extended Euclidean (untuk modulus apa pun yang koprima dengan b). Penguasaan keduanya esensial untuk perhitungan kombinatorial modular dan kriptografi.

Definisi Modular Inverse #

Aturan #

Invers perkalian dari a modulo m adalah bilangan bulat x sehingga:

a · x ≡ 1 (mod m)

Invers a⁻¹ mod m ada iff gcd(a, m) = 1 (yaitu a dan m koprima). Bila gcd(a, m) > 1, tidak ada invers — a tidak bisa dibalik modulo m.

Mekanisme: Mengapa Coprime Diperlukan #

Persamaan a · x ≡ 1 (mod m) berarti a · x - 1 = k · m untuk suatu k, atau a · x + (-k) · m = 1. Menurut Bézout’s identity, persamaan a · x + b · y = gcd(a, b) selalu memiliki solusi bilangan bulat (x, y). Maka a · x + m · y = 1 memiliki solusi iff gcd(a, m) = 1. Bila gcd(a, m) = g > 1, ruas kiri selalu kelipatan g sedangkan ruas kanan 1 — kontradiksi.

Metode 1: Fermat’s Little Theorem #

Aturan #

Bila m prima dan gcd(a, m) = 1:

a^(m-1) ≡ 1 (mod m)              (Fermat's little theorem)
a · a^(m-2) ≡ 1 (mod m)          (bagi kedua sisi dengan a)
maka: a^(-1) ≡ a^(m-2) (mod m)

Implementasi: panggil power(a, m - 2, m) — O(log m) per invers.

Mekanisme: Mengapa Hanya untuk Prima #

Fermat’s little theorem membutuhkan m prima. Untuk m komposit, a^(m-1) ≡ 1 (mod m) tidak dijamin. Contoh: m = 6, a = 5. a^4 = 625 ≡ 1 (mod 6) — kebetulan benar. Tetapi m = 6, a = 2: a^4 = 16 ≡ 4 (mod 6) ≠ 1. Algoritma Fermat akan menghasilkan jawaban salah untuk modulus komposit.

Metode 2: Extended Euclidean #

Aturan #

Algoritma Euclidean extended mengembalikan gcd(a, m) sekaligus koefisien Bézout (x, y) sehingga:

a · x + m · y = gcd(a, m)

Bila gcd(a, m) = 1, maka x adalah invers a mod m (modulo m).

Mekanisme: Rekursi Extended Euclidean #

Misalkan ext_gcd(a, m) → (g, x, y). Karena gcd(a, m) = gcd(m, a mod m), rekurens:

ext_gcd(a, 0) → (a, 1, 0)
ext_gcd(a, m) → (g, y', x' - (a / m) · y')
   di mana (g, x', y') = ext_gcd(m, a mod m)

Pada setiap langkah, koefisien x', y' dari rekursi yang lebih dalam ditransformasikan kembali ke koefisien untuk pemanggilan saat ini. Setelah g menjadi 1 (bila koprima), x (di level atas) adalah invers a mod m.

Kode: Dua Metode #

#include <iostream>

// Fast exponentiation (lihat chapter Fast Exponentiation)
long long power(long long b, long long k, long long m) {
    long long r = 1; b %= m;
    while (k > 0) {
        if (k & 1) r = (r * b) % m;
        b = (b * b) % m;
        k >>= 1;
    }
    return r;
}

// GCD via Euclidean
long long gcd(long long a, long long b) {
    while (b != 0) { long long t = b; b = a % b; a = t; }
    return a;
}

// Extended Euclidean: returns gcd(a, m); sets x, y such that a*x + m*y = gcd
long long ext_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 = ext_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular inverse via Fermat's little theorem (hanya untuk m prima)
// a^(-1) ≡ a^(m-2) (mod m) bila m prima dan gcd(a,m)=1
long long inv_fermat(long long a, long long m) {
    return power(a, m - 2, m);
}

// Modular inverse via Extended Euclidean (untuk m apa pun yang coprime dengan a)
// Mengembalikan -1 bila gcd(a, m) != 1
long long inv_extgcd(long long a, long long m) {
    long long x, y;
    long long g = ext_gcd(a, m, x, y);
    if (g != 1) return -1;
    return ((x % m) + m) % m;   // normalisasi ke [0, m)
}

int main() {
    const long long p = 1'000'000'007;

    // Test 1: invers 3 mod 1e9+7
    long long a = 3;
    long long inv_a = inv_fermat(a, p);
    std::cout << "Fermat: inv(" << a << ") mod p = " << inv_a << '\n';
    std::cout << "Verifikasi: " << a << " * inv = " << (a * inv_a) % p << " (expected 1)\n";

    long long inv_a2 = inv_extgcd(a, p);
    std::cout << "ExtGCD: inv(" << a << ") mod p = " << inv_a2 << '\n';
    std::cout << "Verifikasi: " << a << " * inv = " << (a * inv_a2) % p << " (expected 1)\n";

    // Test 2: pembagian modular
    // Hitung (7/3) mod p = 7 * inv(3) mod p
    long long num = 7, den = 3;
    long long div_mod = num * inv_fermat(den, p) % p;
    std::cout << "\n(7/3) mod p = " << div_mod << '\n';
    // Verifikasi: 3 * div_mod mod p = 7
    std::cout << "Verifikasi: 3 * " << div_mod << " mod p = "
              << (3 * div_mod) % p << " (expected 7)\n";

    // Test 3: m non-prima, ext_gcd bisa
    long long m_np = 1'000'000;  // bukan prima
    long long b = 7;             // coprime dengan 1e6
    long long inv_b = inv_extgcd(b, m_np);
    std::cout << "\nExtGCD: inv(" << b << ") mod " << m_np << " = " << inv_b << '\n';
    std::cout << "Verifikasi: " << b << " * " << inv_b << " mod " << m_np
              << " = " << (b * inv_b) % m_np << " (expected 1)\n";

    // Test 4: invers tidak ada bila gcd != 1
    long long c = 6, m2 = 9;  // gcd(6, 9) = 3
    long long inv_c = inv_extgcd(c, m2);
    std::cout << "\ninv(" << c << ") mod " << m2
              << " = " << inv_c << " (expected -1, gcd="
              << gcd(c, m2) << ")\n";

    return 0;
}

Output yang Dihasilkan:

Fermat: inv(3) mod p = 333333336
Verifikasi: 3 * inv = 1 (expected 1)
ExtGCD: inv(3) mod p = 333333336
Verifikasi: 3 * inv = 1 (expected 1)

(7/3) mod p = 333333338
Verifikasi: 3 * 333333338 mod p = 7 (expected 7)

ExtGCD: inv(7) mod 1000000 = 857143
Verifikasi: 7 * 857143 mod 1000000 = 1 (expected 1)

inv(6) mod 9 = -1 (expected -1, gcd=3)

1. Baris if (b == 0) { x = 1; y = 0; return a; }: base case Extended Euclidean. gcd(a, 0) = a dengan koefisien Bézout x = 1, y = 0 (yaitu a · 1 + 0 · 0 = a).
2. Baris long long g = ext_gcd(b, a % b, x1, y1);: rekursi pada pasangan (b, a mod b). Dapatkan (g, x', y') dari level lebih dalam.
3. Baris x = y1; y = x1 - (a / b) * y1;: transformasi koefisien kembali. Dari b · x' + (a mod b) · y' = g dan a mod b = a - (a/b) · b, dapatkan a · y' + b · (x' - (a/b) · y') = g. Maka koefisien untuk a adalah y' (= x), dan untuk b adalah x' - (a/b) · y' (= y).
4. Baris return ((x % m) + m) % m;: hasil x dari ext_gcd bisa negatif. Normalisasi ke [0, m) dengan + m lalu % m.
5. Hasil inv(3) mod p = 333333336: verifikasi 3 · 333333336 = 1000000008 ≡ 1 (mod 10⁹+7). Sesuai.
6. Hasil (7/3) mod p = 333333338: pembagian modular — 7 · inv(3) mod p. Verifikasi 3 · 333333338 = 1000000014 ≡ 7 (mod p). Sesuai.
7. Hasil inv(7) mod 10^6 = 857143: modulus komposit 10^6 = 2^6 · 5^6. Fermat tidak berlaku, tetapi Extended Euclidean tetap bekerja karena gcd(7, 10^6) = 1.
8. Baris if (g != 1) return -1;: deteksi ketiadaan invers. Bila gcd(a, m) > 1, a tidak koprima dengan m — tidak ada invers.
9. Hasil inv(6) mod 9 = -1: gcd(6, 9) = 3 > 1, sehingga 6 tidak memiliki invers modulo 9. Fungsi mengembalikan -1 sebagai penanda.

Perbandingan Dua Metode #

Aplikasi: Pembagian Modular #

Aturan #

Untuk menghitung (a / b) mod m (dengan b koprima dengan m):

(a / b) mod m = a · b^(-1) mod m = (a · inv(b, m)) mod m

Inilah esensi modular inverse — operasi pembagian di aritmetika modulo diubah menjadi perkalian dengan invers.

Precompute Invers Faktorial #

Untuk soal yang melibatkan banyak C(n, k) mod p, precompute invfact[0..N]:

1. invfact[N] = power(fact[N], p - 2, p) — satu kali Fermat.
2. invfact[i] = invfact[i + 1] · (i + 1) mod p — turun mundur, tanpa power().

Lihat implementasi lengkap di Chapter Permutasi dan Kombinasi .

Aplikasi: Chinese Remainder Theorem (CRT) #

Aturan #

Sistem kongruensi x ≡ a_i (mod m_i) dengan m_i saling koprima memiliki solusi unik modulo M = ∏ m_i. Solusi:

x = Σ a_i · M_i · inv(M_i, m_i)  (mod M)
   di mana M_i = M / m_i

Invers M_i modulo m_i dihitung via Extended Euclidean. Implementasi CRT membutuhkan modular inverse sebagai sub-rutin.

Ringkasan #

• Modular inverse a⁻¹ mod m ada iff gcd(a, m) = 1.
• Fermat’s little theorem: a^(-1) ≡ a^(m-2) (mod m) untuk m prima. Implementasi power(a, m-2, m) dalam O(log m).
• Extended Euclidean: bekerja untuk modulus apa pun yang coprime dengan a. Kompleksitas O(log m).
• Pembagian modular: (a / b) mod m = (a · inv(b, m)) mod m.
• Precompute invers faktorial dengan Fermat sekali lalu turun mundur invfact[i] = invfact[i+1] · (i+1) — O(N + log p).
• Aplikasi: binomial coefficient modular, CRT, kriptografi RSA (deksponen privat), hashing universal.