¿Cuál es una explicación intuitiva para la existencia de inversa modular de [matemática] a [/ matemática] módulo [matemática] n [/ matemática] si y solo si [matemática] mcd (a, n) = 1 [/ matemática]?

Answer 1

Asumamos lo contrario. Entonces, digamos que [math] \ gcd (a, n) = d [/ math]. Eso significa que [math] a [/ math] es un múltiplo de [math] d [/ math]. Además, esto significa que no importa qué número multipliquemos con [matemáticas] a [/ matemáticas], el resultado seguirá siendo un múltiplo de [matemáticas] d [/ matemáticas]. Incluso si restamos [math] n [/ math] algunas veces, que también es un múltiplo de [math] d [/ math], el número resultante todavía sería un múltiplo de [math] d [/ math].
Por lo tanto, es imposible obtener el número 1, a menos que 1 sea un múltiplo de [math] d [/ math]. Este es solo el caso si [math] \ gcd (a, n) = 1 [/ math], y solo en este caso existe el inverso modular.

Funciona mejor con un ejemplo:
Queremos encontrar el inverso de 3 mod 15.
Pero no importa con qué número multipliquemos 3 y luego restemos 15, el número resultante seguirá siendo un múltiplo de 3 y, por lo tanto, nunca 1.

Answer 2

[math] mcd (a, n) [/ math] es, por definición, el entero positivo más pequeño que es una combinación lineal de a y n. Si esto es 1, entonces hay enteros p, q tales que [math] ap + nq = 1 [/ math], de modo que [math] ap \ equiv 1 (\ mod n) [/ math], y p es el inverso de a . Si el mcd no es 1, entonces no existe tal número entero.