Calculadora del inverso modular paso a paso (Euclides extendido)

La idea

Decimos que $x$ es el inverso de $a$ módulo $n$ si

$$a\,x\equiv1\pmod{n}.$$

Se escribe $x=a^{-1}$. Sirve para «dividir» en aritmética modular: multiplicando por $a^{-1}$ se despeja. Existe si y solo si $\operatorname{mcd}(a,n)=1$.

Cómo se calcula

Si $\operatorname{mcd}(a,n)=1$, el algoritmo de Euclides extendido, aplicado a $n$ y $a$, da enteros $s,t$ con

$$s\,n+t\,a=1.$$

Módulo $n$ el término $s\,n$ desaparece, así que $t\,a\equiv1$: el inverso es $t$, reducido al intervalo $0,\dots,n-1$. Si $\operatorname{mcd}(a,n)\ne1$, no hay inverso.

Un ejemplo completo

Hallemos $29^{-1}\pmod{99}$. En la tabla de Euclides extendido, cada fila cumple $r_i=s_i\cdot99+t_i\cdot29$, y cada fila nueva es la de dos filas antes menos $q_i$ veces la anterior:

$i$	$q_i$	$r_i$	$s_i$	$t_i$
$0$		$99$	$1$	$0$
$1$		$29$	$0$	$1$
$2$	$3$	$12$	$1$	$-3$
$3$	$2$	$5$	$-2$	$7$
$4$	$2$	$2$	$5$	$-17$
$5$	$2$	$1$	$-12$	$41$

El último resto no nulo es $1$, así que hay inverso, y la fila 5 dice

$$1=(-12)\cdot99+41\cdot29.$$

El inverso es $29^{-1}\equiv41\pmod{99}$. Comprobación: $29\cdot41=1189=12\cdot99+1$.

Errores típicos

• Olvidar comprobar el $\operatorname{mcd}$: si no es $1$, no hay inverso, y la tabla no «sale».
• Dar $t$ negativo sin reducirlo: si la tabla acabara en $t=-17$, el inverso sería $-17+99=82$, no $-17$.
• Confundir inverso modular con opuesto: el opuesto de $a$ es $-a$ (suma $0$); el inverso es $a^{-1}$ (producto $1$).
• No reducir antes un número negativo o mayor que $n$.

Dónde se usa

En RSA la clave privada es el inverso de la clave pública $e$ módulo $\varphi(n)$. También aparece al descifrar el cifrado afín y al resolver congruencias lineales.