Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 2
Lección 5: Aritmética modular- ¿Qué es la aritmética modular?
- Operador módulo
- Desafío de módulo
- Congruencia módulo
- Relación de congruencia
- Relaciones de equivalencia
- El teorema del cociente y del residuo
- Suma y resta modular
- Suma modular
- Desafío de módulo (suma y resta)
- Multiplicación modular
- Multiplicación modular
- Exponenciación modular
- Exponenciación modular rápida
- Exponenciación modular rápida
- Inversos modulares
- El algoritmo de Euclides
© 2023 Khan AcademyTérminos de usoPolítica de privacidadAviso de cookies
Inversos modulares
¿Qué es un inverso?
Recuerda que un número multiplicado por su inverso es igual a 1. De la aritmética básica sabemos que:
- El inverso de un número A es 1/A ya que A * 1/A = 1 (por ejemplo, el inverso de 5 es 1/5)
- Todos los números reales que no sean 0 tienen un inverso
- Multiplicar un número por el inverso de A es equivalente a dividir entre A (por ejemplo, 10/5 es lo mismo que 10* 1/5)
¿Qué es un inverso modular?
En aritmética modular no tenemos una operación de división. Sin embargo, sí tenemos inversos modulares.
- El inverso modular de A (mod C) es A^-1
- (A * A^-1) ≡ 1 (mod C) o, de manera equivalente, (A * A^-1) mod C = 1
- Solo los primos relativos de C (los números que no comparten factores primos con C) tienen un inverso modular (mod C)
¿Cómo encontrar un inverso modular?
Un método ingenuo de encontrar un inverso modular para A (mod C) es:
Paso 1. Calcula A * B mod C b para los valores de B entre 0 y C-1.
Paso 2. El inverso modular de A mod C es el valor B que hace que se cumpla A * B mod C = 1.
Observa que el término B mod C solo puede tener un valor entero entre 0 y C-1, así que probar valores mayores de B es redundante.
Ejemplo: A=3, C=7
Paso 1. Calcula A * B mod C para los valores de B entre 0 y C-1
3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <------ ¡ENCONTRASTE EL INVERSO!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Paso 2. El inverso modular de A mod C es el valor B que hace A * B mod C = 1
5 es el inverso modular de 3 mod 7 ya que 5*3 mod 7 = 1.
¡Fácil!
Hagamos un ejemplo más en donde no encontremos un inverso.
Ejemplo: A=2 C=6.
Paso 1. Calcula A * B mod C para los valores de B entre 0 y C-1
2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)
Paso 2. El inverso modular de A mod C es el valor B que hace A * B mod C = 1
Ningún valor de B hace que se cumpla A * B mod C = 1. Por lo tanto, A no tiene inverso modular (mod 6).
Esto es porque 2 no es primo relativo de 6 (comparten el factor primo 2).
Esto es porque 2 no es primo relativo de 6 (comparten el factor primo 2).
Este método parece lento...
Hay un método mucho más rápido para encontrar el inverso de A (mod C) que vamos a discutir en los siguientes artículos sobre el algoritmo de Euclides extendido.
¿Quieres unirte a la conversación?
Sera que en el apartado "¿Como encontrar un inverso modular?" hay un error de edición? No entiendo la siguente parte: "Paso 1. Calcula A * B mod C b para los valores de B entre 0 y C-1." La "b" minuscula esta demas? Gracias. Esta muy bien explicado este articulo, me confundi. Quizas solo le falte una coma. Pero logre enterlo gracias a este articulo! Gracias.(4 votos)
entonces un inversor modular es lo mismo de un neutro aditivo multiplicador(3 votos)- este es la magia del modulo(1 voto)
- Sera que en el apartado "¿Como encontrar un inverso modular?" hay un error de edición? No entiendo la siguente parte: "Paso 1. Calcula A * B mod C b para los valores de B entre 0 y C-1." La "b" minuscula esta demas? Gracias. Esta muy bien explicado este articulo, me confundi. Quizas solo le falte una coma. Pero logre enterlo gracias a este articulo! Gracias.(1 voto)