Invers modular — împărțirea modulo un prim

De ce ai nevoie de invers

În lecția anterioară ai văzut că adunarea și înmulțirea se distribuie frumos peste modulo: poți reduce la fiecare pas și rezultatul rămâne corect. Împărțirea NU se poartă la fel. Concret, (a / b) % m nu este egal cu (a % m) / (b % m) — uneori b nici nu divide pe a în întregi, deci a / b nici nu are sens ca număr întreg.

Soluția e să înlocuiești împărțirea cu o înmulțire. Definim inversul modular al lui b modulo m ca numărul b^(-1) pentru care:

b · b^(-1) ≡ 1 (mod m)

Cu el, împărțirea devine înmulțire:

a / b ≡ a · b^(-1) (mod m)

Inversul joacă exact rolul lui 1 / b din aritmetica obișnuită: înmulțirea cu el „anulează” înmulțirea cu b. Atenție: inversul există doar dacă gcd(b, m) = 1 (adică b și m sunt prime între ele). Din fericire, când m e prim, orice b care nu e multiplu de m are invers.

Exemplu pas cu pas: inversul lui 3 modulo 7

Căutăm numărul x cu 3 · x ≡ 1 (mod 7). Încercăm pe rând:

• 3 · 1 = 3, iar 3 % 7 = 3 — nu e 1
• 3 · 2 = 6, iar 6 % 7 = 6 — nu e 1
• 3 · 3 = 9, iar 9 % 7 = 2 — nu e 1
• 3 · 4 = 12, iar 12 % 7 = 5 — nu e 1
• 3 · 5 = 15, iar 15 % 7 = 1 — am găsit, x = 5

Deci inversul lui 3 modulo 7 este 5. Verificare a împărțirii: 6 / 3 ar trebui să dea 2; cu invers, 6 · 5 = 30, iar 30 % 7 = 2. Corect.

Căutarea prin încercări e O(m) — prea lentă pentru m = 1000000007. Aici intervine mica teoremă a lui Fermat: dacă m e prim și b nu e multiplu de m, atunci b^(m-1) ≡ 1 (mod m). Împărțind, obținem formula de aur:

b^(-1) ≡ b^(m-2) (mod m)

Calculul lui b^(m-2) pare uriaș, dar cu exponentiere rapidă (ridicare la putere prin pătrate) îl faci în O(log m) pași — câteva zeci de înmulțiri.

Implementare C++

#include <iostream>
using namespace std;

const long long MOD = 1000000007;   // modul prim

// ridicare la putere modulo, in timp logaritmic O(log e)
long long putereMod(long long b, long long e, long long m) {
    long long rez = 1;
    b %= m;                         // reducem baza de la inceput
    while (e > 0) {
        if (e & 1) {                // daca bitul curent e 1
            rez = (rez * b) % m;    // long long ca sa nu dea overflow
        }
        b = (b * b) % m;            // ridicam baza la patrat
        e >>= 1;                    // trecem la bitul urmator
    }
    return rez;
}

// inversul modular prin Fermat: b^(m-2) mod m (cere m prim)
long long invers(long long b, long long m) {
    return putereMod(b, m - 2, m);
}

int main() {
    cout << invers(3, 7) << "\n";        // 5  -> invers(3,7)=5

    // impartire modulo: a / b = a * invers(b)
    long long a = 6, b = 3;
    long long rez = (a % MOD) * invers(b, MOD) % MOD;
    cout << rez << "\n";                 // 2  -> 6 / 3 = 2

    return 0;
}

Observă cum nu apare niciodată operatorul / aplicat modulo: împărțirea „la 3” s-a transformat în înmulțirea cu invers(3).

Complexitate

Recapitulare

• Împărțirea nu se distribuie peste modulo; împarți înmulțind cu inversul: a / b ≡ a · b^(-1).
• Inversul există doar când gcd(b, m) = 1; pentru m prim, Fermat dă b^(-1) ≡ b^(m-2).
• Calculezi inversul cu exponentiere rapidă pe long long, în O(log m), reducând % m la fiecare pas.