Calculadora de inverso modular

Calculadora de inverso modular

Popular AI Skill PRO

Ingresar cálculo

Resultados

Inverso modular
23
x tal que (a·x) mod m = 1
El inverso existe Sí
mcd(a, m) 1

Fórmula

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
Estadísticas de uso

Publicidad

Informar de un error en esta página

¿Qué es el inverso modular?

El inverso multiplicativo modular de un número entero a módulo m es un entero x que cumple \((a \cdot x) \bmod m = 1\). Equivale a la "división" dentro de la aritmética modular y resulta fundamental en la teoría de números, en el criptosistema RSA y en numerosos algoritmos de la teoría de códigos. Esta calculadora obtiene x mediante el algoritmo de Euclides extendido.

Recta numérica que rodea un anillo de módulo circular tipo reloj, donde a por x cae en 1
Un inverso modular x devuelve a al valor 1 al multiplicarlo, dando la vuelta al módulo m.

Cómo usar esta calculadora

Introduce el número a y el módulo m (con m ≥ 2). La herramienta devuelve el inverso x no negativo más pequeño dentro del rango 0 ≤ x < m, indica si existe el inverso y muestra el mcd(a, m). Si mcd(a, m) ≠ 1, no hay inverso posible y el resultado se muestra como "Ninguno".

La fórmula explicada

El inverso solo existe cuando \(\gcd(a, m) = 1\), es decir, cuando a y m son coprimos (primos entre sí). El algoritmo de Euclides extendido encuentra dos enteros x e y que satisfacen \(a \cdot x + m \cdot y = \gcd(a, m)\). Cuando el mcd vale 1, reducir x módulo m da como resultado el inverso. El valor se normaliza a un número positivo sumándole m si resulta negativo.

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$

Publicidad
Diagrama de flujo plano de los pasos del algoritmo de Euclides extendido que genera el gcd y los coeficientes
El algoritmo de Euclides extendido produce coeficientes que dan el inverso cuando gcd(a, m) = 1.

Ejemplo resuelto

Busquemos el inverso de 3 módulo 11. Necesitamos una x tal que \(3x \equiv 1 \pmod{11}\). Probando, \(3 \times 4 = 12 = 11 + 1\), así que \(12 \bmod 11 = 1\). Por lo tanto, x = 4. El algoritmo de Euclides extendido devuelve el mismo valor y, como \(\gcd(3, 11) = 1\), queda confirmado que el inverso existe.

Paso a paso: algoritmo de Euclides extendido a mano

El inverso modular de a módulo m es el número x tal que \(a \cdot x \equiv 1 \pmod{m}\). Solo existe cuando \(\gcd(a, m) = 1\). El algoritmo de Euclides extendido lo encuentra en tres pasos.

  1. División repetida. Divide m entre a, luego divide el divisor anterior entre el resto, y así sucesivamente, hasta que el resto sea 0. El último resto distinto de cero es el mcd. Si no es 1, no existe inverso.
  2. Expresar 1 como combinación. Trabaja hacia atrás (sustitución regresiva), o lleva el registro de los coeficientes a medida que avanzas, para escribir \(1 = a \cdot x + m \cdot y\). Esta es la identidad de Bézout.
  3. Reducir x. Toma \(x \bmod m\). Si x es negativo, suma m (repite si es necesario) para quedar en el rango de 0 a m − 1.

Ejemplo resuelto: a = 7, m = 40.

Paso División Cociente q Resto
1 40 = 5·7 + 5 5 5
2 7 = 1·5 + 2 1 2
3 5 = 2·2 + 1 2 1
4 2 = 2·1 + 0 2 0

El último resto distinto de cero es 1, así que \(\gcd(7, 40) = 1\) y existe un inverso.

Sustitución regresiva:

$$1 = 5 - 2\cdot 2 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7 = 3(40 - 5\cdot 7) - 2\cdot 7 = 3\cdot 40 - 17\cdot 7$$

Así que \(7 \cdot (-17) + 40 \cdot 3 = 1\), lo que da \(x = -17\).

Comprobación iterativa (coeficiente t de a): empieza con \(t_0 = 0\) (para m = 40) y \(t_1 = 1\) (para a = 7), y luego usa \(t_{k+1} = t_{k-1} - q_k \, t_k\).

Resto q usado t
40 – 0
7 – 1
5 5 0 − 5·1 = −5
2 1 1 − 1·(−5) = 6
1 2 −5 − 2·6 = −17

La fila donde el resto llega a 1 da \(t = -17\). Redúcelo: \(-17 + 40 = \)23.

Verificación: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\), así que \(161 \bmod 40 = 1\). ✓

El mismo método funciona con números más grandes. Para a = 17, m = 3120 da x = 2753, porque \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\). Este par es un ejemplo clásico de libro de texto sobre RSA.

Ejemplos de entradas y sus inversos

Cada inverso a continuación cumple \((a \cdot x) \bmod m = 1\). Cuando \(\gcd(a, m) > 1\), no existe inverso.

a m mcd(a, m) Inverso x Comprobación
3 11 1 4 3·4 = 12 = 1·11 + 1
7 26 1 15 7·15 = 105 = 4·26 + 1
5 12 1 5 5·5 = 25 = 2·12 + 1
10 17 1 12 10·12 = 120 = 7·17 + 1
17 3120 1 2753 17·2753 = 46801 = 15·3120 + 1
4 6 2 Ninguno 4x mod 6 siempre es par, nunca 1
6 9 3 Ninguno 6x mod 9 siempre es múltiplo de 3, nunca 1

Observa que 5 es su propio inverso módulo 12. En general, \(x^2 \equiv 1 \pmod{m}\) tiene soluciones distintas de 1, por lo que algunos números son autoinversos.

Publicidad

Términos clave: coprimo, mcd, congruencia y residuo

  • Módulo (m): el entero positivo en el que los valores se reinician, como en la esfera de un reloj.
  • Congruencia (≡): \(a \equiv b \pmod{m}\) significa que m divide a \(a - b\), por lo que a y b dejan el mismo resto al dividirlos entre m.
  • MCD: el máximo común divisor, el mayor entero que divide a ambos números.
  • Coprimos (primos relativos): dos enteros cuyo mcd es 1. Esta es exactamente la condición para que exista un inverso modular.
  • Identidad de Bézout: para los enteros a y m existen enteros x e y con \(a \cdot x + m \cdot y = \gcd(a, m)\). Cuando el mcd es 1, reducir esta ecuación módulo m da \(a \cdot x \equiv 1\), así que x es el inverso.
  • Clase de residuo: el conjunto de todos los enteros que comparten el mismo resto módulo m. El inverso es único como clase de residuo, y la calculadora muestra el representante de 0 a m − 1.
  • Inverso multiplicativo modular: el residuo \(x = a^{-1} \bmod m\) con \(a \cdot x \equiv 1 \pmod{m}\).

Teorema de Euler: si \(\gcd(a, m) = 1\), entonces \(a^{\varphi(m)} \equiv 1 \pmod{m}\), donde \(\varphi\) es la función phi de Euler. Por tanto, el inverso también puede calcularse como \(a^{\varphi(m)-1} \bmod m\).

Pequeño teorema de Fermat: cuando m = p es primo, \(\varphi(p) = p - 1\), así que \(a^{-1} \equiv a^{p-2} \pmod{p}\) para cualquier a no divisible entre p. Ejemplo: \(3^{9} = 19683 = 1789 \cdot 11 + 4\), así que \(3^{-1} \equiv 4 \pmod{11}\), que coincide con la tabla anterior. La fórmula de potencias necesita la factorización de m (para hallar \(\varphi\)), mientras que el algoritmo de Euclides extendido no, por lo que suele ser el método más rápido para módulos generales.

Preguntas frecuentes

¿Cuándo no existe el inverso? Cuando a y m comparten un factor común mayor que 1; por ejemplo, 4 módulo 6 (mcd = 2) no tiene inverso.

¿Tiene que ser m un número primo? No. m puede ser cualquier entero ≥ 2; lo único que importa es que a y m sean coprimos.

¿En qué rango está la respuesta? El inverso se expresa como el menor residuo no negativo, entre 0 y m − 1.

Última actualización:

Lo más popular en Matemáticas y Estadísticas

Ver todas las calculadoras de Matemáticas y Estadísticas