Últimos dos dígitos de $17^{17^{17}}$

Question

Para un conjunto de problemas, tuvimos que encontrar los dos últimos dígitos de 17^17^17

Entonces, lo que hice fue encontrar el último dígito de 17^17 y luego tomar 17 elevado a ese último dígito de 17 y luego encontrar los dos últimos dígitos de ese número. Obtuve los dos últimos dígitos como 17.

¿Es correcto mi método, si no, cuál es el método y cuál es tu respuesta? Gracias

Answer 1

Tienes la posibilidad de usar la aritmética módulo $100$ cuando todo lo que te importa son los últimos dos dígitos. Además, dado que $\varphi(100)=40$ y $17$ es coprimo con $100$, puedes hacer aritmética módulo $40$ en los exponentes.

Entonces, primero podemos enfocarnos en $17^{17}$ módulo $40$: $$\begin{align} 17^{17}&\equiv17\cdot289^8&\mod40\\ &\equiv17\cdot9^8&\mod40\\ &\equiv17\cdot81^4&\mod40\\ &\equiv17\cdot1^4&\mod40\\ &\equiv17&\mod40\\ \end{align}$$

Así que tenemos que $$17^{17^{17}}\equiv17^{17}\mod100$$

$$\begin{align} 17^{17^{17}}&\equiv17^{17}&\mod100\\ &\equiv17\cdot289^8&\mod100\\ &\equiv17\cdot89^8&\mod100\\ &\equiv17\cdot(-11)^8&\mod100\\ &\equiv17\cdot121^4&\mod100\\ &\equiv17\cdot21^4&\mod100\\ &\equiv17\cdot441^2&\mod100\\ &\equiv17\cdot41^2&\mod100\\ &\equiv17\cdot(50-9)^2&\mod100\\ &\equiv17\cdot(2500-900+81)&\mod100\\ &\equiv17\cdot81&\mod100\\ &\equiv17\cdot(-19)&\mod100\\ &\equiv-\left(18^2-1\right)&\mod100\\ &\equiv-323&\mod100\\ &\equiv77&\mod100\\ \end{align}$$

Answer 2

Pensé que tal vez a alguien le interesaría otro método muy similar a lo que Alex y Lab presentaron. Requiere otro Teorema de teoría de números pero utiliza números más pequeños:

Factorizamos $100=4 \cdot 25$. Entonces, como gcd(4,25)=1 y $17 \equiv 1 \mod 4$ según el Teorema del Resto Chino, es suficiente calcular $$17^{17^{17}} \mod 25.$$ Calculamos $\varphi(25)=4\cdot 5=20$. Usando el Pequeño Teorema de Fermat, que establece que $17^{\varphi(25)}\equiv 1 \mod 25$, queremos calcular $$17^{17} \mod 20.$$ Podemos hacerlo de la forma en que lo hizo Alex. Alternativamente, calculamos $\varphi(\varphi(25))=\varphi(20)=2\cdot 4=8$ y aplicamos el Pequeño Teorema de Fermat una segunda vez, obteniendo $$17\equiv1 \mod \varphi(\varphi(25)) \\ \Rightarrow 17^{17} \equiv 17^{17 \mod \varphi(\varphi(25))} \equiv 17 \mod \varphi(25) \\ \Rightarrow 17^{17^{17}} \equiv 17^{17^{17} \mod \varphi(25)}\equiv 17^{17} \mod 25 .$$ Ahora, en este caso especial tenemos la suerte de que es fácil encontrar $17 \cdot 3 \equiv 1 \mod 25$, es decir, $17^{-1} \equiv 3 \mod 25$. Así, usando Fermat nuevamente, podemos calcular $$17^{17} \equiv 17^{20-3} \equiv 17^{20}17^{-3}\equiv 17^{-3} \equiv 3^3 \equiv 27 \equiv 2 \mod 25.$$

Entonces, si $17^{17^{17}}\equiv x \mod 100$ es nuestro resultado final, tenemos $$x\equiv 1 \mod 4 \\ x\equiv 2 \mod 25.$$ Existe un algoritmo estándar para resolver congruencias de este tipo: Comprobamos múltiplos de 25 para encontrar $$25 \equiv 1 \mod 4\\25 \equiv 0 \mod 25$$ y $$76 \equiv 0 \mod 4 \\76 \equiv 1 \mod 25.$$ Por lo tanto, el resultado final es $$x\equiv 1 \cdot 25 + 2\cdot 76 \equiv 77 \mod 100.$$

Answer 3

Básicamente necesitamos encontrar $$17^{17^{17}}\pmod{100}$$

El uso de la función Carmichael es más útil que la función Phi de Euler si el módulo es compuesto como $100,20$ a continuación.

Donde $\lambda(100)=20$

$\displaystyle\implies 17^{17^{17}}\equiv 17^{17^{17}\pmod{20}}\pmod{100}$

Una vez más, $\displaystyle \lambda(20)=4\implies17^4\equiv1\pmod{20}$

$\displaystyle\implies17^{17}=17\cdot(17^4)^4\equiv17\cdot1^4\equiv17\pmod{20}$

$\displaystyle\implies 17^{17^{17}}\equiv 17^{17} \pmod{100}$

Ahora, $\displaystyle17=20-3,\implies 17^{17}=(20-3)^{17}=-3^{17}+\binom{17}1\cdot3^{16}\cdot20\pmod{100}$ como los términos superiores contienen $20^2$ que son divisibles por $100$

Ahora, como $\displaystyle3\equiv-1\pmod5, 3^{16}\equiv(-1)^{16}\equiv1\pmod5$

Como $a\equiv b\pmod m\implies a\cdot n\equiv b\cdot n\pmod{m\cdot n},$

Entonces, $\displaystyle\binom{17}1\cdot3^{16}\cdot20\equiv17\cdot1\cdot20\pmod{5\cdot20}\equiv40$

$\displaystyle\implies 17^{17}\equiv-3^{17}+40\pmod{100}$

Nuevamente, $\displaystyle3^{17}=3\cdot9^8$

Pero, $\displaystyle(10-1)^8=1-\binom8110\pmod{100}\equiv-79$

$\displaystyle\implies 3^{17}\equiv3(-79)\pmod{100}\equiv-237\equiv-37$

$\displaystyle\implies 17^{17}\equiv40-(-37)\pmod{100}\equiv77$