¿Los últimos dos dígitos de $2^{1000}$ vía Teorema chino del resto?

Question

Me encontré a través de la mencionada pregunta en mis notas, mientras que el estudio de hoy y yo me he olvidado de cómo hacerlo. Recuerdo que el uso de la CRT para resolver un problema como este en uno de mis pruebas, muy mal por no darle la espalda a mis soluciones :(.

Desde $\gcd(100,2) = 2$, no puede usar la costumbre, el teorema de Euler para resolver a través de $\pmod {100}$. Por lo $100 = 5^2 2^2$, y la aplicación de Euler en el 25 me da $2^{20} \equiv 1 \pmod {25}$. Sin embargo, desde $\gcd(2,4) = 2$, no podemos hacer lo mismo para $\bmod 4$. En consecuencia ¿cómo puedo configurar el otro modulo de la congruencia para que yo pueda aplicar CRT?

Answer 1

Usted tiene que $2^{20}\equiv 1\pmod{25}$ (gracias a el Teorema de Euler), y, por tanto, que el $2^{1000} = (2^{20})^{500}\equiv 1\pmod{25}$.

Para la congruencia modulo $4$ usted incluso no necesita invocar el Teorema de Euler; usted puede apenas notar que debido a $2^2\equiv 0\pmod{4}$,$2^{1000}\equiv 0 \pmod{4}$. Así, el sistema de congruencias que tiene es: $$\begin{align*} x &\equiv 1\pmod{25}\\ x &\equiv 0 \pmod{4} \end{align*}$$ Hay uno y sólo un número de módulo 100 que satisfaga a ambas congruencias por el Teorema del Resto Chino (es $x\equiv 76\pmod{100}$). Desde $2^{1000}$ satisface a ambas congruencias, la CRT le dice que...

(El uso de el Teorema de Euler fue sólo para simplificar el cálculo de $2^{1000}$ modulo $25$; pero para averiguar $2^{1000}$ modulo $4$, no hay necesidad de una simplificación, ya es muy simple.)

Answer 2

$\rm n = (2^{10})^{100} =\: 1024^{100}\: \equiv\ 0\ (mod\ 4);\:\ n\equiv (-1)^{100}\equiv 1\equiv -24\ (mod\ 25)\ $ so $\rm\: n \equiv\: -24\ (mod\ 100)$

La prueba anterior es completamente elemental: no utilice el Fermat / Teorema de Euler ni el Teorema chino del resto - sólo $\rm\ 4,\:25\ |\ n+24\ \Rightarrow\ lcm(4,25)\ |\ n+24\:,\ $ $\rm\ 100\ |\ n+24\:.$ le supone conocido $\rm\ 2^{10} = 1024 = 1K\:,\:$ pero que es omnipresente en la era de la computadora!

Tenga en cuenta cuánto más simple se trata de aplicar fuerza bruta CRT + Euler/Fermat. Muchos problemas similares pueden resolverse también, más simplemente, de esta manera (gracias a la ley de números pequeños).

Answer 3

Estás casi allí. De $2^{20} \equiv 1 \bmod {25}$ tiene $2^{22} \equiv 4 = 2^2 \bmod {100}$, y que es el ciclo que estás buscando.