Hola, estoy estudiando aritmética modular en forma autodidacta y tengo varias dudas al respecto del calculo de inversor de n en Zm.
Para número chicos me resulta simple usar el Teorema de Bezout o el pequeño teorema de Fermat.
Teorema de Bezout: Si \( (a,b) = 1 \Rightarrow{ \exists{x \ e \ y \ tal\ que\ ax\ +\ by\ =\ 1}} \)
Pequeño teorema de Fermat: Si p es un número primo, entonces, para cada número natural a, con a>0 , \( a^m\ ≡\ a\ (mod_{m}) \)
Por ejemplo: Obtener el inverso de \( 7\ en\ Z_{17} \)
Como \( mcd(6,17)\ =\ 1 \Rightarrow{ 7x\ +\ 17y\ =\ 1} \)
Factorizando m = 17 tenemos: \( 17\ =\ 7.2\ +\ 3 \) (1)
Factorizando a = 7 tenemos: \( 7\ =\ 2.3\ +\ 1 \) (2)
Despejando el 3 de (1) y reemplazando el (2) tenemos:
\( 7 = 2.(17\ -\ 7.2)\ +\ 1\ =\ 2.17\ -\ 4.7\ +\ 1 \)
Por lo tanto:
\( 7\ -\ 2.17\ +\ 4.7\ = 1 \)
\( 5.7\ -\ 2.17\ =\ 1 \Rightarrow{ x = 5 , y = -2} \)
Y el inverso buscado es \( 5^{-1}\ ≡\ 7\ mod_{7} \)
Pero para número grandes me resulta complejo saber si \( mcd(a,b)\ =\ 1 \) o si el módulo de \( [Z_{m} \) es primo.
Por ej: \( Sacar\ el\ inverso\ de\ 777\ en\ Z_{1009} \)
Tenemos que por el algoritmo de Euclides \( mcd(777,1009)\ =\ 3 \)\( \Rightarrow{ no\ son\ coprimos\ y\ no\ se\ puede\ aplicar\ el\ teorema\ de\ Bezout } \)
La otra opción es usar el pequeño teorema de Fermat:
\( 777^{1007}\ ≡\ 777\ mod_{1009} \)
\( 777^{777+230}\ ≡\ 777 mod_{1009} \)
luego, no se como seguir, ¿que me recomiendan para continuar?.
