Cuando quieres encontrar el inverso de un número \( a \) módulo \( M \), entonces tienes que resolver la congruencia
\( ax\simeq 1 \pmod M \)
Para poder resolver esta congruencia necesita s que \( a \) y \( M \) sean primos relativos, por lo que entonces existiran enteros \( x_0, y_0 \) tal que \( ax_0+My_0 =1 \). Al reducir esta identidad módulo \( M \), encontramos que el inverso de \( a \) es justamente el entero \( x_0 \) que nos da la identidad anterior.
Así que para encontrar el inverso de \( a \) tienes varias opciones. Todas aplicables sólo si \( (a,M)=1 \).
1) Si \( M \) es pequeño, entonces multiplica a \( a \) por los naturales menores que \( M \) y reducelos módulo M hasta que encuentres el inverso. Por ejemplo, para encontrar el inverso de 3 módulo 5, me basta con hacer la multiplicaciíon 3x2 =6 que es congruente con uno módulo 5, y por lo tanto el inverso de tres modulo 5 es 2.
2) Usar el algoritmo de Euclides para encontrar la combinación lineal \( ax_0+My_0 =1 \), espero conozcas este proceso.
3) Usar el pequeño teorema de Fermat, que dice que \( a^{\phi(M)} \simeq 1 \pmod M \) por lo que entonces el inverso está dado por \( a^{\phi(M)-1} \).