El inverso multiplicativo modular es un concepto fundamental en la teoría de números y tiene amplias aplicaciones en criptografía, informática y matemáticas discretas. Para un entero a y un módulo m, su inverso multiplicativo modular x (si existe) satisface la ecuación:

a * x ≡ 1 (mod m)

Esto significa que (a * x) % m = 1. El inverso existe si y solo si gcd(a, m) = 1 (es decir, a y m son coprimos).

Consideremos un problema clásico: dada la relación N = A % P, donde A % B = 0 y gcd(B, P) = 1, se pide calcular (A / B) % P. Si X = (A / B) % P, entonces se deduce que A / B ≡ X (mod P). Multiplicando por B, tenemos A ≡ B * X (mod P). Dado que N = A % P, podemos reescribir esto como N ≡ B * X (mod P). El objetivo es encontrar X, que es equivalente a encontrar X = N * B^-1 (mod P), donde B^-1 es el inverso multiplicativo de B modulo P.

Para este ejemplo, utilizaremos un módulo primo P = 9973.

Método 1: Búsqueda Exhaustiva (Fuerza Bruta)

La forma más sencilla de encontrar el inverso multiplicativo X para B * X ≡ N (mod P) es probar todos los posibles valores de X desde 0 hasta P-1. Dado que P es relativamente pequeño (9973), este método es viable aunque ineficiente para módulos grandes.

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int casos_prueba;
    std::cin >> casos_prueba;
    while (casos_prueba--) {
        int num_n, denom_b; // N y B en la ecuación N = B * X (mod P)
        std::cin >> num_n >> denom_b;
        num_n %= 9973;
        denom_b %= 9973;
        for (int res_x = 0; res_x < 9973; ++res_x) {
            // Buscamos X tal que (X * B) % P == N
            if ((static_cast<long long>(res_x) * denom_b) % 9973 == num_n) {
                std::cout << res_x << std::endl;
                break;
            }
        }
    }
    return 0;
}

Método 2: Teorema Pequeño de Fermat

Si el módulo P es un número primo y a no es un múltiplo de P (es decir, gcd(a, P) = 1), el Teorema Pequeño de Fermat establece que:

a^(P-1) ≡ 1 (mod P)

Multiplicando ambos lados por a^-1 (el inverso de a), obtenemos:

a^(P-2) ≡ a^-1 (mod P)

Por lo tanto, el inverso multiplicativo de a modulo P se puede calcular como a^(P-2) mod P. Este cálculo requiere una función eficiente para la exponenciación modular (también conocida como "exponenciación rápida" o "potencia binaria").

#include <iostream>

// Función para calcular (base^exponente) % modulo eficientemente
long long calcular_potencia(long long base, long long exponente, long long modulo) {
    long long resultado = 1;
    base %= modulo;
    while (exponente > 0) {
        if (exponente % 2 == 1) { // Si el bit actual del exponente es 1
            resultado = (resultado * base) % modulo;
        }
        base = (base * base) % modulo; // Cuadrar la base
        exponente /= 2; // Desplazar el exponente a la derecha
    }
    return resultado;
}

// Función para calcular el inverso multiplicativo usando Fermat
long long inverso_fermat(long long valor, long long modulo_primo) {
    // El inverso es valor^(modulo_primo - 2) mod modulo_primo
    return calcular_potencia(valor, modulo_primo - 2, modulo_primo);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int casos_prueba;
    std::cin >> casos_prueba;
    while (casos_prueba--) {
        long long num_n, denom_b; // N y B
        std::cin >> num_n >> denom_b;
        // Encontramos el inverso de B mod 9973
        long long inv_b = inverso_fermat(denom_b, 9973);
        // Calculamos (N * inv_b) % 9973
        long long resultado_final = (num_n * inv_b) % 9973;
        std::cout << resultado_final << std::endl;
    }
    return 0;
}

Método 3: Algoritmo Extendido de Euclides

El Algoritmo Extendido de Euclides puede encontrar enteros x e y para cualquier par de enteros a y b tales que:

a * x + b * y = gcd(a, b)

Para encontrar el inverso multiplicativo de a modulo m, buscamos x tal que a * x ≡ 1 (mod m). Esto es equivalente a encontrar x e k tales que a * x + m * k = 1. Esto solo es posible si gcd(a, m) = 1. El Algoritmo Extendido de Euclides puede resolver directamente esta ecuación.

La función recursiva euclides_extendido(a, m, x, y) devolverá gcd(a, m) y actualizará x e y con los coeficienets corespondientes. El valor de x obtenido puede ser negativo, por lo que es necesario ajustarlo para que sea positivo y esté dentro del rango [0, m-1] usando (x % m + m) % m.

#include <iostream>

// Implementación del Algoritmo Extendido de Euclides
// Calcula a*x_out + b*y_out = gcd(a, b)
long long euclides_extendido(long long a_val, long long b_val, long long &x_out, long long &y_out) {
    if (b_val == 0) {
        x_out = 1;
        y_out = 0;
        return a_val; // gcd(a, 0) = a
    }
    long long gcd_val = euclides_extendido(b_val, a_val % b_val, y_out, x_out);
    y_out -= (a_val / b_val) * x_out;
    return gcd_val;
}

// Función para calcular el inverso multiplicativo usando Euclides Extendido
long long inverso_euclides(long long valor, long long modulo) {
    long long x_coeff, y_coeff;
    // euclides_extendido(valor, modulo, x_coeff, y_coeff) nos da:
    // valor * x_coeff + modulo * y_coeff = gcd(valor, modulo)
    // Si gcd(valor, modulo) es 1, entonces valor * x_coeff % modulo = 1
    euclides_extendido(valor, modulo, x_coeff, y_coeff);
    // Ajustar x_coeff para que sea positivo
    return (x_coeff % modulo + modulo) % modulo;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int casos_prueba;
    std::cin >> casos_prueba;
    while (casos_prueba--) {
        long long num_n, denom_b; // N y B
        std::cin >> num_n >> denom_b;
        // Encontramos el inverso de B mod 9973
        long long inv_b = inverso_euclides(denom_b, 9973);
        // Calculamos (N * inv_b) % 9973
        long long resultado_final = (num_n * inv_b) % 9973;
        std::cout << resultado_final << std::endl;
    }
    return 0;
}