Algoritmo de Euclides extendido.
Encontrar el inverso modular es una operación fundamental en la teoría de números, esencial para resolver congruencias lineales de la forma $ax \equiv b \pmod m$. Aunque el tanteo funciona para módulos pequeños, y el Fermat's Little Theorem aplica cuando el módulo es primo, el Extended Euclidean Algorithm es el método más robusto y general. Te permite calcular el inverso de un entero $a$ módulo $m$ de forma eficiente, siempre que $a$ y $m$ sean primos relativos (es decir, $\gcd(a, m) = 1$).
La técnica se basa en la Bézout's Identity, que dice que para cualquier par de enteros $a$ y $m$, existen enteros $x$ e $y$ tales que $ax + my = \gcd(a, m)$. Cuando $\gcd(a, m) = 1$, esta ecuación se convierte en $ax + my = 1$. Si tomas esta ecuación módulo $m$, el término $my$ desaparece, dejando $ax \equiv 1 \pmod m$. Así, el coeficiente $x$ que encuentras a través de esta combinación lineal es precisamente el inverso modular de $a$.
Para aplicar esto en la práctica, realiza el Euclidean Algorithm estándar para encontrar el máximo común divisor, llevando la cuenta de los cocientes. En cuanto llegues a un residuo de 1, realiza una "sustitución hacia atrás", revirtiendo los pasos para expresar 1 como una combinación lineal