Inverso Multiplicativo (Aritmética Modular)

Inverso Multiplicativo (Aritmética Modular)
Decimos que dos números enteros son congruentes módulo m (aunque también se puede generalizar paracualquier otro dominio euclídeo) si al dividirlos entre m obtenemos el mismo residuo. Por ejemplo, 7 es congruente con 12 módulo 5 porque al dividir 7entre 5 y 12 entre 5, en ambos casos obtenemos el mismo residuo (que es 2). Cuando a es congruente con b módulo m se escribe,
En el ejemplo anteriorse tiene . Supóngase que se conocen los valores de a, b y m, pero que se desconoce el valor x de la siguienteecuación:
(2)
Basta con encontrar un valor a − 1 que tenga la característica de que ,
pues de esta manera al multiplicar la ecuación (2) por a − 1se tendría la solución deseada:

Al valor a − 1 se le llama inverso modular de a módulo m. Desafortunadamente este valor no siempre existe. Porejemplo, con a = 4 y m = 6 no existe ningún número entero entero a − 1 tal que . De hecho este valor existe si y sólo si mcd(a,m) = 1. Más aún, si alusar el algoritmo de Euclides extendido (ahora con b = m) se obtiene 1 = as + mt, entonces el valor s es el inverso modular de a módulo m. Por ejemplo,se desea resolver la ecuación

Entonces con el algoritmo de Euclides extendido se calcula que mcd (5,9) = 1 = 5(2) + 9( − 1). Como mcd(5,9) = 1entonces 5 tiene un inverso modular. Más aún, como 1 = 5(2) + 9( − 1), entonces ese inverso es 2. Entonces

Es decir que el valor de x es 4.