Hallar el último dígito usando el teorema de Euler
Estoy un poco atascado con este problema, espero que puedas ayudar. Quiero encontrar el último dígito de una torre de energía usando el teorema de Euler: \begin{align} q &= 10, \\ \varphi(q) &= 4, \\ \varphi(\varphi(q)) &= 2, \\\varphi(\varphi(\varphi(q))) &= 1. \end{align} \begin{align} 625703 ^{\displaystyle 43898 ^{\displaystyle 614961 ^{\displaystyle 448629}}} &\equiv (625703 \bmod 10)^{\displaystyle (43898 \bmod \varphi(10))^{\displaystyle (614961 \bmod \varphi(\varphi(10)))^{\displaystyle (448629 \bmod \varphi(\varphi(\varphi(10))))}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1^{\displaystyle 0}}} \mod 10 \\ &\equiv 3^{\displaystyle 2^{\displaystyle 1}} \mod 10 \\ &\equiv 3^{\displaystyle 2} \mod 10 \\ &\equiv 9 \mod 10 \end{align} De acuerdo con este enfoque, el último dígito de la torre de energía debe ser 9. Sin embargo, la solución correcta es 1 (ver aquí ). ¿Qué estoy haciendo mal?
Este enfoque se basa en las siguientes dos respuestas
informática ${{27^{27}}^{27}}^{27}\pmod {10}$
¿Qué es un algoritmo / técnica general para encontrar el último dígito de una exponencial anidada?
Respuestas
¿Qué estoy haciendo mal?
El teorema de Euler asume que la base y el módulo son relativamente primos.
En su problema, ese no es el caso: $43898$ no es relativamente primordial para $4$.
De hecho, $43898^n\equiv0\pmod4$ para $n\ge2$.
¿Puedes resolverlo ahora?
Insinuación: $ $ Darse cuenta de: $\ n\ge 2\,\Rightarrow\, \color{#c00}{(2k)^n\bmod 4 \,\equiv\, 0}\ $ Entonces por $ $ reducción de pedidos modular
$\!\!\bmod 10\!:\ 3^{\large \color{#c00}4}\equiv 1 \Rightarrow\ 3^{\large \color{}{(2k)^{\large n}}}\!\!\!\equiv 3^{\large \color{#c00}{(2k)^{\large n}\bmod 4}}\!\equiv 3^{\:\!\large\color{#c00} 0}\equiv 1,\ $ y
$\!\!\bmod 10\!:\ 625703\equiv 3\Rightarrow 625703^N\!\equiv 3^N\,$por la regla del poder de congruencia .
Observación $ $ El descuido es: el teorema de Euler $\,a^{\phi(m)}\equiv 1\pmod{\!m}\,$ tiene hipótesis $\,\gcd(a,m)= 1\,$ por lo que no se aplica a $\,(2k)^n\pmod{\! 4}.\,$ En tales casos, podemos extraer el mcd de $\,a^N$ y $\,m\,$usando la Ley Distributiva mod , reduciendo al caso coprime donde se aplica Euler, por ejemplo, ver aquí . Aunque es excesivo en este caso, podríamos aplicarlo arriba para factorizar el factor común$2^2$ como sigue
$$\quad\ \color{#0a0}{n\ge 2}\,\Rightarrow\,\color{#c00}{(2k)^{\large n}\!\bmod 4} \,=\, 2^2 (k^2 (2k)^{\large \color{#0a0}{n-2}}\!\bmod 1) \:\!=\:\! 2^2(0) \:\!=\:\! 0$$
\begin{align} 625703^{43898^{\scriptstyle614961^{\scriptstyle448629}}}\mkern-18mu\bmod 10&= (625703\bmod 10)^{43898^{\scriptstyle614961^{\scriptstyle448629}}\bmod\varphi(10)}\\ &= 3^{43898^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^{2^{\scriptstyle614961^{\scriptstyle448629}}\mkern-12mu\bmod4}=3^0. \end{align}