Supongamos que deseamos calcular el $110^{-1} \bmod 9$. ¿Cómo puedo hacer esto mentalmente o con un mínimo de cálculos.
Gracias.
Respuestas
¿Demasiados anuncios?
fleablood
Puntos
5913
Mientras que el módulo es pequeño (y solo dígitos son muy pequeñas), es muy fácil de hacer mentalmente.
En primer lugar reducir $110$ módulo de $9$ conseguir $2$. Esto es sólo el resto de la división (el cociente no importa). Trate de trabajar con números más pequeños en cada paso del camino.
Entonces usted necesita para determinar qué número se multiplica $2$ por obtener un resto de $1$ cuando se divide por $9$. En este caso, usted sabe que $(2)(5)=10$. Así que la inversa es $5$.
Básicamente, usted sólo tiene que comprobar los números de $2$ a uno menos que el módulo integrador. Con un pequeño módulo es muy fácil de hacer mentalmente. Es sólo con la más grande de los módulos que necesita para utilizar el Algoritmo de Euclides Extendido.
melchizedek
Puntos
21
Es más fácil si usted está trabajando modulo de un primer $p$, por Fermat poco teorema:
$$ a^{p-1} \equiv 1 \pmod{p} $$
La cual puede escribirse como:
$$ a \cdot a^{p-2} \equiv 1 \pmod{p} $$
Asimismo, se puede utilizar el Teorema de Euler, que es más fuerte que la anterior, pero tendrá que calcular $\phi(n)$.
$$ \phi(9) = 3^2 - 3 = 6 $$
Utilizando el mismo truco que podemos obtener:
$$ 110^{6} \equiv 110 \cdot 110^{5} \equiv 1 \pmod{9}$$
Como se ha indicado en los comentarios, $110^{-1} \equiv 5 \pmod{9}$.
Se puede comprobar mediante el uso de la doble cuadrado método:
$$ 110 \equiv 2 \pmod{9} $$ $$ 110^2 \equiv 4 \pmod{9} $$ $$ 110^4 \equiv 16 \equiv 7 \pmod{9} $$ $$ 110^5 \equiv 7 \cdot 2 \equiv 5 \pmod{9} $$
Por lo $110^{-1} \equiv 5 \pmod{9}$.
