parcial 2021 segundo semestre, ejercicio 2c

parcial 2021 segundo semestre, ejercicio 2c

de Lorena Paola Rodriguez Lasarte -
Número de respuestas: 1

Buenas noches, estaba haciendo este ejercicio pero me quede trancada y no se me ocurre como seguir.

Lo que hice fue usar euler y llegue a que  (2^{70})^{10} * 2^{26} \equiv 2^{26} (71)  , después pensé en usar la  2^{26} \equiv ?(71)  y para eso use  2^7 \equiv 57(71)  y podría seguir un poco mas razonando de forma similar pero me siguen quedando números muy grandes, entonces no se si debería elevar el 2 a un numero mas grande para que me quede mas chico el 57 o como es que saca el ejercicio.

espero su respuesta,

Lorena 

En respuesta a Lorena Paola Rodriguez Lasarte

Re: parcial 2021 segundo semestre, ejercicio 2c

de Marco Antonio Perez -
Hola, Lorena:

En efecto, haces bien arrancando con Euler para tener que 2^{70} \equiv 1 \ ({\rm mod} \ 71). Recuerda que llegados a este punto, la idea es dividir el exponente original del problema, en este caso 3^{242} entre 70 para poder encontrar el resto de dividir 2^{3^{242}} entre 71. En otras palabras, la idea es hallar r entre 0 y 69 tal que 3^{242} = 70q + r, ya que a partir de allí puedes elevar a la q la congruencia 2^{70} \equiv 1 \ ({\rm mod} \ 71) y después multiplicar la congruencia resultante por 2^{r} (fíjate que no importa cuánto vale q). Entonces, lo que importa hallar es tal r, es decir, resolver 3^{242} \equiv r \ ({\rm mod} \ 70).

Espero que lo anterior sea de utilidad.

Saludos,
Marco