[napolitana]

Hola a todos ,

Cómo calculo \(  3^{14}  \)  (mod 17) \( \Bbb Z(17) \). Si alguien me podría resolverlo , sin hacer las operaciones completas . Si hubiera algunas propiedades .
Si el modulo fuera menor que el exponente , podría aplicar el phi de Euler , y así lo descompondría . Pero en este caso 17 es mayor que 14 . Aunque si lo puedo aplicar no sabría cómo hacer luego las inversas .

Muchas gracias

[feriva]

Hola a todos ,

Cómo calculo \(  3^{14}  \)  (mod 17) \( \Bbb Z(17) \). Si alguien me podría resolverlo , sin hacer las operaciones completas . Si hubiera algunas propiedades .
Si el modulo fuera menor que el exponente , podría aplicar el phi de Euler , y así lo descompondría . Pero en este caso 17 es mayor que 14 . Aunque si lo puedo aplicar no sabría cómo hacer luego las inversas .

Muchas gracias

\( 3^{3}=27\equiv10(mod\,17) \)

Entonces

\( 3^{12}=(3^{3})^{4}\equiv10000(mod\,17) \)

\( 3^{14}=(3^{3})^{4}\cdot9=3^{14}\equiv90000(mod\,17) \)

Y sólo haces esta división 90000/17 y sacas el resto, que es 2.

Saludos.

[Luis Fuentes]

Hola

Cómo calculo \(  3^{14}  \)  (mod 17) \( \Bbb Z(17) \). Si alguien me podría resolverlo , sin hacer las operaciones completas . Si hubiera algunas propiedades .
Si el modulo fuera menor que el exponente , podría aplicar el phi de Euler , y así lo descompondría . Pero en este caso 17 es mayor que 14 . Aunque si lo puedo aplicar no sabría cómo hacer luego las inversas .

Otra forma: tienes que \( 3\cdot 6=18=17+1 \) y por tanto \( 3^{-1}=6 \) mod \( 17 \).

Por Euler \( 3^{16}=1 \) mod \( 17 \) y entonces:

\( 3^{14}=3^{14-16}=3^{-2}=6^2=36=2 \) mod \( 17 \).

Saludos.

[napolitana]

Por Euler \( 3^{16}=1 \) mod \( 17 \) y entonces:

\( 3^{14}=3^{14-16}=3^{-2}=6^2=36=2 \) mod \( 17 \).

No doy ahora visto cómo pasas de
\( 3^{-2}=6^2 \)
Cómo lo hiciste , la duda que tenía yo en principio era cómo hacer cuando era elevadas a números negativos .

Gracias

[feriva]

Por Euler \( 3^{16}=1 \) mod \( 17 \) y entonces:

\( 3^{14}=3^{14-16}=3^{-2}=6^2=36=2 \) mod \( 17 \).

No doy ahora visto cómo pasas de
\( 3^{-2}=6^2 \)

Supongo que ese 6 es el inverso de 3 módulo 17, es rápido de encontrar: \( 3\cdot6=18=17+1\equiv1 \).
 Entonces \( 3^{-2}=(3^{-1})^2\equiv 6^2 \).

*(Creo, pero espera a ver qué te dice Luis)

[napolitana]

Por Euler \( 3^{16}=1 \) mod \( 17 \) y entonces:

\( 3^{14}=3^{14-16}=3^{-2}=6^2=36=2 \) mod \( 17 \).

No doy ahora visto cómo pasas de
\( 3^{-2}=6^2 \)

Supongo que ese 6 es el inverso de 3 módulo 17, es rápido de encontrar: \( 3\cdot6=18=17+1\equiv1 \).
 Entonces \( 3^{-2}=(3^{-1})^2\equiv 6^2 \).

*(Creo, pero espera a ver qué te dice Luis)

Si , cierto , creo que es así . No lo estaba viendo antes  . El inverso es 6 . Aunque a simple vista yo no lo vea , haciendo la congruencia lineal \( 3X\equiv1 (modulo 17)  \) debería de dar 6 . Bien es cierto que se puede encontrar sin hacer la ecuación de congruencia lineal , yo ahora mismo no sabría encontrarlo sin hacer los cálculos de la inversa . Tampoco sé si hay algún truco o algo

Muchas gracias a los dos 

[feriva]

Por Euler \( 3^{16}=1 \) mod \( 17 \) y entonces:

\( 3^{14}=3^{14-16}=3^{-2}=6^2=36=2 \) mod \( 17 \).

No doy ahora visto cómo pasas de
\( 3^{-2}=6^2 \)

Supongo que ese 6 es el inverso de 3 módulo 17, es rápido de encontrar: \( 3\cdot6=18=17+1\equiv1 \).
 Entonces \( 3^{-2}=(3^{-1})^2\equiv 6^2 \).

*(Creo, pero espera a ver qué te dice Luis)

Si , cierto , creo que es así . No lo estaba viendo antes  . El inverso es 6 . Aunque a simple vista yo no lo vea , haciendo la congruencia lineal \( 3X\equiv1 (modulo 17)  \) debería de dar 6 . Bien es cierto que se puede encontrar sin hacer la ecuación de congruencia lineal , yo ahora mismo no sabría encontrarlo sin hacer los cálculos de la inversa . Tampoco sé si hay algún truco o algo

En este caso es una ecuación diofántica tan sencilla que no hace falta algoritmo de Euclides ni nada, se ve casi sin tantear.

La cuestión importante es que 1/3 es el inverso “universal” de 3, para cualquier módulo, en todo Z, y, aunque no es entero, tendrá unas equivalencias en enteros (unas u otras) según los módulos con que trabajes.

Saludos.

[Luis Fuentes]

Hola

 Lo del inverso fue lo primero que dije en mi respuesta

Otra forma: tienes que \( 3\cdot 6=18=17+1 \) y por tanto \( 3^{-1}=6 \) mod \( 17 \).

 En este caso incluso resolver la ecuación diofántica que permite hallar el inverso sería bastante rápido:

3x+17y=1

 Aplicando el algoritmo de Euclides:

\(  17=3\cdot 5+2 \)
\(  3=2\cdot 1+1 \)
 
de donde:

\(  3=(17-3\cdot 5)+1 \)
\(  3\cdot 6=17+1 \)

Saludos.