¿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:
  • The inverse of a number A is 1/A since A * 1/A = 1 
    e.g. the inverse of 5 is 1/5
  • All real numbers other than 0 have an inverse
  • Multiplying a number by the inverse of A is equivalent to dividing by A
    e.g. 10/5 is the same as 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.
  • The modular inverse of A (mod C) is A^-1
  • (A * A^-1) ≡ 1 (mod C) or equivalently (A * A^-1) mod C = 1
  • Only the numbers coprime to C (numbers that share no prime factors with C) have a modular inverse (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 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 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).

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 próximos artículos sobre el algoritmo de Euclides extendido. Primero, ¡hagamos algunos ejercicios!