Saltar al contenido

¿Cómo calculo el módulo inverso de un número cuando el módulo no es primo?

Esta cuestión se puede resolver de variadas maneras, pero en este caso te mostramos la respuesta más completa en nuestra opinión.

Solución:

Usando el algoritmo euclidiano y el álgebra básica obtenemos

$900=24*37+12 rightarrow 900-24*37=12$

$37=3*12+1 rightarrow 37-3(900-24*37)=1$

Por lo tanto $73*37-3*900=1$. Entonces el inverso de 37 mod 900 es 73.

Describimos una forma que es análoga al enfoque del Teorema de Fermat. Para módulos grandes $M$ cuya factorización de potencia temporal es conocido el método es razonablemente eficiente. Sin embargo, el Algoritmo Euclidiano Extendido ofrece un mejor camino a la inversa.

Primero calculamos $varphi(900)$. De la factorización de potencia prima $2^2 3^25^2$ de $900$, esto es $(2)(6)(20)=240$. Así $$37^240equiv 1pmod900,$$ y por lo tanto el inverso de $37$ es congruente con $37^239$ módulo $900$.

Observación: En lugar de usar la función $varphi$ de Euler, podemos usar la función $lambda$ de Carmichael. En nuestro caso, tenemos $lambda(900)=textlcm(2,6,20)=60$ y por lo tanto el inverso de $37$ módulo $900$ es congruente con $37^59$ módulo $900$ .

Valoraciones y reseñas

Finalizando este artículo puedes encontrar las interpretaciones de otros programadores, tú igualmente puedes insertar el tuyo si lo crees conveniente.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *