Hallar a⁻¹ mod n cuando mcd(a,n)=1.
El inverso modular es el equivalente en aritmética modular al recíproco en la aritmética de números reales estándar. En la aritmética normal, para "deshacer" la multiplicación por un número $a$, multiplicas por su recíproco $a^{-1}$ (o $\frac{1}{a}$) de tal forma que $a \cdot a^{-1} = 1$. De la misma forma, en aritmética modular con módulo $n$, el inverso modular de un entero $a$ es un entero $x$ tal que $ax \equiv 1 \pmod n$. Normalmente escribimos este inverso como $a^{-1}$.
Este concepto es fundamental en Teoría de Números porque te permite hacer "divisiones" en entornos modulares. Específicamente, es la herramienta principal que usas para resolver congruencias lineales de la forma $ax \equiv b \pmod n$. En lugar de dividir entre $a$, multiplicas ambos lados por $a^{-1}$ para despejar $x$. Esta técnica es esencial para resolver sistemas de congruencias (Teorema del Residuo Chino) y es la base matemática de la criptografía RSA.
Sin embargo, a diferencia de la aritmética estándar donde cada número distinto de cero tiene un inverso, un inverso modular existe si y solo si $a$ y $n$ son primos relativos, lo que significa que $\gcd(a, n) = 1$. Si $\gcd(a, n) > 1$, la congruencia $ax \equiv 1 \pmod n$ no tiene solución. Cuando el inverso existe, lo puedes encontrar usando el Algoritmo de Euclides Extendido (para cualquier $n$) o el Pequeño Teorema de Fermat (específicamente cuando $n$ es primo).
Definición El inverso modular de $a$ módulo $n$, que escribimos como $a^{-1}$, cumple que: $$a \cdot a^{-1} \equiv 1 \pmod n$$
Condición de Existencia El inverso $a^{-1} \pmod n$ existe si y solo si: $$\gcd(a, n) = 1$$ Si el inverso existe, es único módulo $n$.
Método de Cálculo 1: Algoritmo de Euclides Extendido Por la Identidad de Bézout, si $\gcd(a, n) = 1$, existen enteros $x$ e $y$ tales que: $$ax + ny = 1$$ Si tomas esta ecuación módulo $n$, el término $ny$ desaparece y te queda: $$ax \equiv 1 \pmod n$$ Aquí, $x$ es el inverso modular.
Método de Cálculo 2: Pequeño Teorema de Fermat Si el módulo $p$ es un número primo y $p \nmid a$, entonces: $$a^{p-2} \equiv a^{-1} \pmod p$$
Método de Cálculo 3: Teorema de Euler (Generalización) Para cualquier módulo $n$ donde $\gcd(a, n) = 1$: $$a^{\phi(n)-1} \equiv a^{-1} \pmod n$$ donde $\phi(n)$ es la función phi de Euler.
Teorema: La congruencia lineal $ax \equiv 1 \pmod n$ tiene solución si y solo si $\gcd(a, n) = 1$. Además, si existe una solución, es única módulo $n$.
Demostración de la Existencia: Hay que mostrar que $\gcd(a, n) = 1 \iff \exists x$ tal que $ax \equiv 1 \pmod n$.
$(\Rightarrow)$ Supón que $\gcd(a, n) = 1$. Por la Identidad de Bézout, existen enteros $x$ e $y$ tales que: $$ax + ny = \gcd(a, n) = 1$$ Si consideras esta ecuación módulo $n$, tienes: $$ax + ny \equiv 1 \pmod n$$ Como $ny$ es un múltiplo de $n$, $ny \equiv 0 \pmod n$. Por lo tanto: $$ax \equiv 1 \pmod n$$ Así que $x$ es el inverso modular de $a$.
$(\Leftarrow)$ Supón que existe un entero $x$ tal que $ax \equiv 1 \pmod n$. Por la definición de congruencia, esto implica que $ax - 1$ es un múltiplo de $n$. Por lo tanto, existe un entero $k$ tal que: $$ax - 1 = nk \implies ax - nk = 1$$ Sea $d = \gcd(a, n)$. Por definición, $d$ divide a $a$ y $d$ divide a $n$. En consecuencia, $d$ debe dividir cualquier combinación lineal de $a$ y $n$. Como $ax - nk = 1$, $d$ tiene que dividir a $1$. El único entero positivo que divide a $1$ es el $1$. Por lo tanto, $d = 1$, así que $\gcd(a, n) = 1$.
Demostración de la Unicidad: Supón que hay dos inversos, $x_1$ y $x_2$, tales que: $$ax_1 \equiv 1 \pmod n \quad \text{y} \quad ax_2 \equiv 1 \pmod n$$ Por transitividad: $$ax_1 \equiv ax_2 \pmod n$$ Multiplica ambos lados por $x_1$ (que ya sabes que existe): $$x_1(ax_1) \equiv x_1(ax_2) \pmod n$$ $$(x_1 a)x_1 \equiv (x_1 a)x_2 \pmod n$$ Como $x_1 a \equiv 1 \pmod n$: $$1 \cdot x_1 \equiv 1 \cdot x_2 \pmod n$$ $$x_1 \equiv x_2 \pmod n$$ Así, el inverso es único módulo $n$. $\square$