Invers modular

Problema

În cadrul multor probleme de informatică se cere calcularea unei valori și afișarea acesteia modulo unei constante precizate în enunț. Se poate observa faptul că operațiile de adunare, scădere și înmulțire se pot efectua fără probleme cu respect la un anumit modul, însă operația de împărțire trebuie tratată diferit. Mai exact, dacă $A$, $B$ si $M$ sunt numere întregi, $M \ne 0$, $B \ne 0$, egalitatea $\frac{A}{B} \mod{M} = \frac{A \mod{M}}{B \mod{M}} \mod{M}$ nu este întotdeauna adevărată.

Se recomandă citirea informațiilor din articolul despre matematică de bază înainte de a citi noțiunile de aici.

Ce este inversul modular?

În matematică, inversul unui număr real $x$ este acel număr $x^{-1}$ care satisface $x \cdot x^{-1} = 1$. Împărțirea unui număr la $x$ este echivalentă cu înmulțirea acestuia cu $x^{-1} = \frac{1}{x}$. Tot așa, și în aritmetica modulară definim inversul modular al unui număr $x$ (cu respect la modulul $M$) acel număr notat $x^{-1}$ care satisface relația $x \cdot x^{-1} \equiv{1} \pmod{M}$. Se poate demonstra faptul că un număr întreg are un invers modular modulo $M$ dacă și numai dacă el și $M$ sunt prime între ele.

Atunci, pentru a efectua operația de împărțire cu respect la modul dintre $A$ și $B$ trebuie să îl înmulțim pe $A$ cu inversul modular al lui $B$, deoarece $(\frac{A}{B}) \mod{M} = (A \cdot B^{-1}) \mod{M}$.

Cum calculăm inversul modular al unui număr?

Calcularea folosind mica teoremă a lui Fermat

Congruența se mai poate scrie ca:

$a \cdot a^{p - 2} \equiv 1 \pmod{p}$

Se poate observa ușor că de fapt inversul modular al lui $a$ este $a^{p - 2}$, care poate fi calculat rapid folosind exponențierea logaritmică.

Algoritmul extins al lui Euclid

Luăm în considerare următoarea identitate:

Daca $A$ și $M$ sunt prime între ele, atunci există $x_1$ și $y_1$ astfel încât $Ax_1 + My_1 = 1$. De aici reiese faptul că $Ax_1 \equiv 1 \pmod{M}$, adică $x_1$ este inversul modular al lui $A$.

Fie $c$ câtul împărțirii lui $A$ la $M$ și $r$ restul. Algoritmul lui Euclid ne spune că $cmmdc(A, M) = cmmdc(M, r) \implies cmmdc(M, r) = 1$. Astfel, există $x_2$ și $y_2$ care satisfac $Mx_2 + ry_2 = 1$.

Dar

Se observa că $x_1 = y_2$ și $y_1 = x_2 - c \cdot y_2$, iar $c = \lfloor \frac{A}{M} \rfloor$. Astfel, putem folosi recursiv algoritmul lui Euclid, adăugându-i parametrii $x_1$ și $y_1$:

void euclidExtins(const int a, const int b, int &x1, int &y1);

În cazul în care parametrul $b$ din funcție este egal cu 0, atunci $a$ va fi egal cu 1 și astfel vom seta $x_1 = 1$, iar $y_1$ poate lua orice valoare, de exemplu tot 1.

Mai jos se poate observa o implementare în C++ a algoritmului lui Euclid, respectiv a funcției de calculare a inversului modular al lui $A$ pentru modulul $M$:

void euclidExtins(const int a, const int b, int &x1, int &y1) {
    if (b == 0) {
        x1 = 1;
        y1 = 1;
        return;
    }

    int x2, y2;

    euclidExtins(b, a % b, x2, y2);

    x1 = y2;
    y1 = (x2 - a / b * y2) % M;
}

int inversModular(const int A) {
    int x1, y1;

    euclidExtins(A, M, x1, y1);

    /* daca vrem x1 pozitiv
    if(x1 < 0)
        x1 += M;
    */

    return x1;
}

Probleme cu invers modular

• Invers Modular
• Lot 2021 Juniori Prosum
• Codeforces Beautiful Numbers
• Toate aplicatiile prezentate la combinatorica
• Codeforces Sum of the kth powers

Lectură suplimentară

• Algoritmul lui Euclid extins. Invers modular - Pbinfo
• Modular arithmetic - USACO Guide
• Modular multiplicative inverse
• Calculate modulo inverses efficiently
• Modular arithmetic for Beginners - Codeforces
• Funcție scurtă de a calcula inversul modular - Codeforces
• Modular Inverse / Inverse Remainder / Modular Division – A Quick Guide - Codeforeces