Euler Fermat con doble exponente.

Question

Tengo que calcular

PS

(sin calculo). Quiero hacer esto usando Euler / Fermat. Lo que ya tengo es que$$ 3^{{2014}^{2014}} \pmod {98} $, así que sé que puedo usar la fórmula de Euler Fermat.

Entonces sé que$\gcd(3, 98) = 1$

Entonces puedo decir eso

PS

Ahora no sé cómo progresar. ¿Ideas / sugerencias?

Answer 1

Continuar para $2014^{2014} \pmod{42} \equiv (2014 \pmod {42})^{2014} \equiv (-2)^{2014} \equiv 2^{2014} $

Teorema del Resto chino y Fermat Poco Teorema: $42 = 2 \times 3 \times 7 $

$ 2^{2014} \pmod 2 \equiv 0 \bmod 2 $

$ 2^{2014} \pmod 3 \equiv (-1)^{2014} \equiv 1 $

$ 2^{2014} \pmod 7 \equiv 2^{2014 \bmod \ 6} \equiv 2^4 \equiv 16 \equiv 2 $

CRT: $2^{2014} \pmod{42} \equiv 16 $

Nos quedamos con $3^{16} \pmod {98} $

Aplicar repite el cuadrado:

$ 3^{16} \equiv (3^4)^4 \equiv (-17)^4 \equiv 17^4 \equiv (17^2)^2 \equiv (-5)^2 \equiv \boxed{25} $

Answer 2

Bueno, yo había escrito casi de todo esto, y, a continuación, @GohP.iHan publicado un mucho mejor/más corto enfoque. :) Voy a seguir adelante y post en caso de que alguien más lo encuentra útil, pero usted debe utilizar a su manera.

El problema, ahora, es que desea calcular $2014^{2014}\pmod{42}$. Podemos factor de 2014, lo que debería hacer que sea más fácil: $$2014^{2014} = (2\cdot19\cdot53)^{2014}$$

Así, podemos utilizar Euler/Fermat para$19^{2014}$$53^{2014}$:

\begin{align} 19^{2014}&\equiv 19^{2014\bmod \phi(42)}\pmod{42}\\ &\equiv 19^{2014\bmod 12}\\ &\equiv 19^{10}\\ &\equiv \left(19^{-1}\right)^2\equiv 31^2\\ &\equiv 37\pmod {42} \end{align} Nota de cómo he utilizado ese $9^{10}\equiv 19^{12}\cdot \left(19^{-1}\right)^2$; esto me salva de tener que hacer repetidas plazas para evaluar el poder. Yo uso el mismo truco para $53^{2014}$ a continuación: \begin{align} 53^{2014}&\equiv 11^{10}\pmod{42}\\ &\equiv \left(11^{-1}\right)^2\equiv 23^2\\ &\equiv 25 \pmod {42} \end{align}

Ahora tenemos que molestos $2^{2014}\pmod{42}$, donde el exponente de la base no coprime para el módulo. En este punto, sólo diré que "el uso de la CRT como @GohP.iHan hizo en su respuesta," porque no estaba seguro de cómo se enfoque. Usted debe tener ese $2^{2014} \equiv 16$.

La multiplicación, tenemos una respuesta: $$2014^{2014} \equiv 16\cdot 37\cdot 25 = 14800 \equiv 16 \pmod 42$$

Así, la respuesta final es $3^{16}\equiv 25\pmod {98} $