Calcular $1008^{189642}\pmod{2011}$

Question

Cómo comenzar el cálculo de $1008^{189642}\pmod{2011}$

Estoy bastante perdido tratando de averiguar cómo ir sobre esto.

Hay algunos "hechos" que puedo encontrar, pero no está seguro de cómo estos me puede ayudar

• gcd(2011,1008) = 1.
• 2011 es el primer.
• El primer factorización de $1008$ $2^4\times3^2\times7$

Answer 1

Un peatón solución:

Por Fermat poco teorema, $1008^{2010}\equiv 1 \bmod 2011$, y desde $189642\equiv 702 \bmod 2010$, obtenemos $1008^{189642}\equiv 1008^{702} \bmod 2011$.

Un par de iteraciones rendimiento $1008^9\equiv 48 \bmod 2011$, por lo tanto $1008^{702} \equiv 48^{78} \bmod 2011 $.

Tomando nota de que $48^3 \equiv -13 \bmod 2011$, obtenemos $48^{78}\equiv 13^{26} \bmod 2011$.

Finalmente, $13^{26} = 13^{15}\cdot 13^{11}\equiv 74 \cdot 183 \equiv 1476 \bmod 2011$.

Poner todo junto, $1008^{189642}\equiv 1476 \bmod 2011$.

Answer 2

Primero que todo $2011$ es primo. Uno tiene en el campo de $\mathbb F_{2011}$ como una primera simplificación $$1008^{189642}=1008^{2011\cdot94+608}=1008^{94+608}=1008^{702}$$ since $2\cdot1008=2011+5$ $$1008^{702}=\left(\frac52\right)^{702}=\left(\frac52\right)^{2\cdot27\cdot13}=\left(\frac{25}{4}\right)^{27\cdot13}=\left(\frac{1548}{64}\right)^{9\cdot13}=\left(\frac{387}{16}\right)^{9\cdot13}$$ Una solución de $16x=2011y+1$ $(x,y)=(3645,29)$ $\mathbb F_{2011}$ ha $\dfrac{1}{16}=3645=1634$.

Sigue $$\left(\frac{387}{16}\right)^{9\cdot13}=(387\cdot1634)^{117}=904^{117}$$ Calculations follow in $\mathbb F_{2011}$ $$904^5=551\\904^{30}=551^6=1188\\904^{90}=1188^3=1400\\904^{25}=754$ $ , Finalmente, $$904^{117}=1400\cdot754\cdot904^2=\color{red}{1476}$$