Inverso multiplicativo modular

Definición

Un inverso multiplicativo modular  de un entero $a$ es un entero $x$ tal que $a \cdot x$ es congruente con $1$ módulo algún módulo $m$. De forma formal: queremos encontrar un entero $x$ tal que

$$a \cdot x \equiv 1 \mod m.$$

También denotaremos $x$ simplemente como $a^{-1}$.

Hay que notar que el inverso modular no siempre existe. Por ejemplo, sea $m = 4$, $a = 2$. Al revisar todos los valores posibles módulo $m$, queda claro que no podemos encontrar un $a^{-1}$ que satisfaga la ecuación anterior. Se puede demostrar que el inverso modular existe si y solo si $a$ y $m$ son coprimos (es decir, $\gcd(a, m) = 1$).

En este artículo presentamos dos métodos para calcular el inverso modular cuando existe, y un método para calcular el inverso modular de todos los números en tiempo lineal.

Cálculo del inverso modular usando el algoritmo de Euclides extendido

Consideremos la siguiente ecuación (con incógnitas $x$ e $y$):

$$a \cdot x + m \cdot y = 1$$

Esta es una ecuación diofántica lineal en dos variables. Como se muestra en el artículo enlazado, cuando $\gcd(a, m) = 1$, la ecuación tiene una solución que se puede encontrar con el algoritmo de Euclides extendido. Nótese que $\gcd(a, m) = 1$ es también la condición para que exista el inverso modular.

Ahora, si tomamos módulo $m$ en ambos lados, podemos eliminar $m \cdot y$, y la ecuación queda:

$$a \cdot x \equiv 1 \mod m$$

Así, el inverso modular de $a$ es $x$.

La implementación es la siguiente:

int x, y;
int g = extended_euclidean(a, m, x, y);
if (g != 1) {
    cout << "No solution!";
}
else {
    x = (x % m + m) % m;
    cout << x << endl;
}

Nótese cómo modificamos x. El x que resulta del algoritmo de Euclides extendido puede ser negativo, así que x % m también podría ser negativo, y primero hay que sumarle m para que quede positivo.

Otro método para calcular el inverso modular es usar el teorema de Euler, que afirma que la siguiente congruencia es cierta si $a$ y $m$ son coprimos:

$$a^{\phi (m)} \equiv 1 \mod m$$

$\phi$ es la función φ de Euler. De nuevo, nótese que el hecho de que $a$ y $m$ sean coprimos era también la condición para que exista el inverso modular.

Si $m$ es un número primo, esto se simplifica al pequeño teorema de Fermat :

$$a^{m - 1} \equiv 1 \mod m$$

Si multiplicamos ambos lados de las ecuaciones anteriores por $a^{-1}$, obtenemos:

• Para un módulo $m$ arbitrario (pero coprimo): $a ^ {\phi (m) - 1} \equiv a ^{-1} \mod m$
• Para un módulo primo $m$: $a ^ {m - 2} \equiv a ^ {-1} \mod m$

A partir de estos resultados, podemos calcular fácilmente el inverso modular con el algoritmo de exponenciación binaria, que trabaja en tiempo $O(\log m)$.

Aunque este método es más fácil de entender que el del párrafo anterior, cuando $m$ no es un número primo hay que calcular la función φ de Euler, lo que implica factorizar $m$, y eso puede ser muy difícil. Si se conoce la factorización prima de $m$, la complejidad de este método es $O(\log m)$.

Dado un módulo primo $m > a$ (o podemos aplicar el módulo para hacerlo más chico en 1 paso), según la división euclidiana 

$$m = k \cdot a + r$$

donde $k = \left\lfloor \frac{m}{a} \right\rfloor$ y $r = m \bmod a$, entonces

$$\begin{array}{rlrlr}{\displaystyle }& {\displaystyle ⟹}& {\displaystyle 0}& {\displaystyle \equiv k\cdot a+r}& {\displaystyle \mathrm{m}\mathrm{o}\mathrm{d}m}\\ {\displaystyle }& {\displaystyle ⟺}& {\displaystyle r}& {\displaystyle \equiv -k\cdot a}& {\displaystyle \mathrm{m}\mathrm{o}\mathrm{d}m}\\ {\displaystyle }& {\displaystyle ⟺}& {\displaystyle r\cdot a^{-1}}& {\displaystyle \equiv -k}& {\displaystyle \mathrm{m}\mathrm{o}\mathrm{d}m}\\ {\displaystyle }& {\displaystyle ⟺}& {\displaystyle a^{-1}}& {\displaystyle \equiv -k\cdot r^{-1}}& {\displaystyle \mathrm{m}\mathrm{o}\mathrm{d}m}\end{array}$$$$\begin{align*} & \implies & 0 & \equiv k \cdot a + r & \mod m \ & \iff & r & \equiv -k \cdot a & \mod m \ & \iff & r \cdot a^{-1} & \equiv -k & \mod m \ & \iff & a^{-1} & \equiv -k \cdot r^{-1} & \mod m \end{align*}$$

Nótese que este razonamiento no vale si $m$ no es primo, porque la existencia de $a^{-1}$ no implica la existencia de $r^{-1}$ en el caso general. Para verlo, intentemos calcular $5^{-1}$ módulo $12$ con la fórmula anterior. Quisiéramos llegar a $5$, ya que $5 \cdot 5 \equiv 1 \bmod 12$. Sin embargo, $12 = 2 \cdot 5 + 2$, y tenemos $k=2$ y $r=2$, y $2$ no es invertible módulo $12$.

Si el módulo es primo, en cambio, todos los $a$ con $0 < a < m$ son invertibles módulo $m$, y podemos usar la siguiente función recursiva (en C++) para calcular el inverso modular del número $a$ respecto de $m$

int inv(int a) {
  return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
}

La complejidad temporal exacta de esta recursión no se conoce. Está en algún punto entre $O(\frac{\log m}{\log\log m})$ y $O(m^{\frac{1}{3} - \frac{2}{177} + \epsilon})$. Ver On the length of Pierce expansions . En la práctica esta implementación es rápida; por ejemplo, para el módulo $10^9 + 7$ siempre termina en menos de 50 iteraciones.

inv[1] = 1;
for(int a = 2; a < m; ++a)
    inv[a] = m - (long long)(m/a) * inv[m%a] % m;

Cálculo del inverso modular para un arreglo de números módulo $m$

Supongamos que nos dan un arreglo y queremos calcular el inverso modular de todos sus números (todos son invertibles). En lugar de calcular el inverso de cada número, podemos ampliar la fracción por el producto de prefijos (excluyéndose a sí mismo) y el producto de sufijos (excluyéndose a sí mismo), y terminar calculando un solo inverso.

$$\begin{array}{rllll}& {\displaystyle x_i^{-1}}& {\displaystyle =\frac{1}{x_i}=\frac{\stackrel{{\text{prefix}}_{i-1}}{\overbrace{x_1\cdot x_2\cdots x_{i-1}}}\cdot 1\cdot \stackrel{{\text{suffix}}_{i+1}}{\overbrace{x_{i+1}\cdot x_{i+2}\cdots x_n}}}{x_1\cdot x_2\cdots x_{i-1}\cdot x_i\cdot x_{i+1}\cdot x_{i+2}\cdots x_n}}& & \\ & {\displaystyle }& {\displaystyle ={\text{prefix}}_{i-1}\cdot {\text{suffix}}_{i+1}\cdot {(x_1\cdot x_2\cdots x_n)}^{-1}}& & \end{array}$$$$\begin{align} x_i^{-1} &amp;= \frac{1}{x_i} = \frac{\overbrace{x_1 \cdot x_2 \cdots x_{i-1}}^{\text{prefix}$${i-1}} \cdot 1 \cdot \overbrace{x{i+1} \cdot x_{i+2} \cdots x_n}^{\text{suffix}{i+1}}}{x_1 \cdot x_2 \cdots x{i-1} \cdot x_i \cdot x_{i+1} \cdot x_{i+2} \cdots x_n} \ &amp;= \text{prefix}{i-1} \cdot \text{suffix}{i+1} \cdot \left(x_1 \cdot x_2 \cdots x_n\right)^{-1} \end{align}

En el código podemos armar un arreglo de productos de prefijos (excluyéndose a sí mismo, empezando desde el elemento identidad), calcular el inverso modular del producto de todos los números y después multiplicarlo por el producto de prefijos y el producto de sufijos (excluyéndose a sí mismo). El producto de sufijos se calcula iterando de atrás hacia adelante.

std::vector<int> invs(const std::vector<int> &a, int m) {
    int n = a.size();
    if (n == 0) return {};
    std::vector<int> b(n);
    int v = 1;
    for (int i = 0; i != n; ++i) {
        b[i] = v;
        v = static_cast<long long>(v) * a[i] % m;
    }
    int x, y;
    extended_euclidean(v, m, x, y);
    x = (x % m + m) % m;
    for (int i = n - 1; i >= 0; --i) {
        b[i] = static_cast<long long>(x) * b[i] % m;
        x = static_cast<long long>(x) * a[i] % m;
    }
    return b;
}

Problemas de práctica

• UVa 11904 - One Unit Machine 
• Hackerrank - Longest Increasing Subsequence Arrays 
• Codeforces 300C - Beautiful Numbers 
• Codeforces 622F - The Sum of the k-th Powers 
• Codeforces 717A - Festival Organization 
• Codeforces 896D - Nephren Runs a Cinema