Fermat Poco y Teorema el Teorema de Euler

Question

Estoy teniendo problemas para la comprensión inteligente de las aplicaciones de Fermat Poco Teorema y su generalización, el Teorema de Euler. Yo ya entender la derivación de ambos, pero no puedo pensar en maneras de utilizarlos en problemas que sé que debo utilizar (es decir, el tema está establecido).

Aquí hay dos preguntas que yo tenía problemas con el intento de uso de la FLT y ET:

1. Encontrar el 5to dígito del extremo derecho al final del número de $N = 5^{\displaystyle 5^{\displaystyle 5^{\displaystyle 5^{\displaystyle 5}}}}$.

2. Definir la secuencia de enteros positivos $a_n$ recursivamente por $a_1=7$ $a_n=7^{a_{n-1}}$ todos los $n\geq 2$. Determinar los dos últimos dígitos de $a_{2007}$.

Me las arreglé para resolver el segundo, con ataques y el descubrimiento de un ciclo en potencias de 7 mod 1000, y ese puede ser el camino más fácil para esta pregunta en particular, en lugar de utilizar ET. Sin embargo, la aplicación ET al apilados exponentes creo sin embargo es un concepto esencial para la solución de las cuestiones más complejas como la número 1 que deseo aprender. Sería de gran ayuda si me pudieran obtener sugerencias sobre el uso de ET en esos dos problemas y, en general, ET enfoque apilados exponentes y su motivación.

Answer 1

Para el primer problema se necesita un poco de Teorema del Resto Chino. Usted quiere encontrar el resto de la pila de exponencial modulo $10^5 = 2^5 \times 5^5$. Considere los dos primos divisores por separado.

Como $\phi(2^5) = 16$ tenemos que si $r_1$ es el resto de $5^{5^{5^{5}}}$ modulo $\phi(2^5) = 16$$5^{5^{5^{5^{5}}}} \equiv 5^{r_1} \pmod {2^5}$. Ahora tenemos que encontrar a $r_1$, que es una solución de $5^{5^{5^{5}}} \equiv r_1 \pmod {2^4}$. Repita este algoritmo par de veces y te va a deshacerse de los exponentes y usted encontrará un valor tal que: $5^{5^{5^{5^{5}}}} \equiv r \pmod {2^5}$. Ahora uso ese $5^{5^{5^{5^{5}}}} \equiv 0 \pmod {5^5}$ y la cola de las dos soluciones con el Teorema del Resto Chino.

La segunda puede ser resuelto usando un método similar, pero esta vez no necesitará el Teorema del Resto Chino, como $(7,100) = 1$. En realidad esto es más fácil como $7^4 \equiv 1 \pmod {100}$.

Answer 2

Caminar a través de el primer problema, que efectivamente necesita encontrar a $a \equiv 5^{5^{5^{5^{5}}}} \bmod 10^5$. Este se divide fácilmente en la búsqueda de $a_1 \equiv a \bmod 2^5$ $a_2 \equiv a \bmod 5^5$ que puede ser re-unidas con el teorema del resto Chino.

El orden de $5 \bmod 32$ divide $\phi(32)=16$ (y de hecho podríamos decir que se divide $\lambda(32) = 8$ debido a la Carmichael función). Debido a $16$ es una potencia de dos (por lo que el orden de cada número también va a ser una potencia de dos) que rápidamente puede cuadrado repetidamente: $(5\to25\equiv-7\to49 \equiv17\to 289\equiv 1)$ a que el orden de $5$ es en el hecho de $8$. Así que necesitamos encontrar:

$ a$ b \equiv 5^{5^{5^{5}}} \bmod 8 \\ \text {, que le dará:}\qquad a_1\equiv 5^b \bmod 32$$

Siguiente paso; la orden de $5 \bmod 8$ es fácilmente visto a $2$, y podemos notar que el restante exponente es impar. Caminando de nuevo hacia abajo el exponente de la escalera, $ a$ b \equiv 5^\text{impar} \equiv 5 \bmod 8 \\ \text{y }\qquad a_1\equiv 5^5 \equiv 21 \bmod 32$$

También tenemos $a_2\equiv a \equiv 0 \bmod 5^5$. Como sucede a $5^5=3125\equiv 21 \bmod 32$, lo $a\equiv 3125 \bmod 10^5$ y la solicitud de dígitos es $0$.

Tenga en cuenta que esto es cierto para $5$s en una torre de los exponentes de la altura de la $3$ o más; y esto es inevitable, el comportamiento, los valores del exponente de la torre no muy lejos no tiene ningún efecto a la final modular resultado. En el segundo problema, el factor de intimidación de una torre de exponentes $2007$ alto se retira por este conocimiento; sólo la parte inferior algunos hacen una diferencia.