¿Cuál es el diez dígitos de $\zeta=7^{7^{7^{7^7}}}$. Tengo esta pregunta, mientras que haciendo teorema del binomio. Creo que el $7^4=2401$ y sólo necesitamos $\zeta\pmod{100}$. Todo lo que podía pensar es que ya ha presentado (el pensamiento no es nada en realidad), ¿puede ayudar?
Respuestas
¿Demasiados anuncios?
Tenga en cuenta que $$7^2=49,\ 7^3=343,\ 7^4=2401,\ 7^5=168\color{red}{07}.$$
Así que, todo lo que necesitamos es encontrar a $7^{7^{7^{7}}}$ mod $4$.
Ahora $$7^{7^{7^{7}}}\equiv (-1)^{7^{7^{7}}}\equiv -1\equiv 3\pmod 4.$$ Por lo tanto, la respuesta que queremos es el mismo que el de los diez dígitos de $343$, es decir,$\color{red}{4}$.
user26486
Puntos
8588
El teorema de Euler: $(a,n)=1\,\Rightarrow\, a^{\phi(n)}\equiv 1\pmod {\!n}$ donde $\phi(n)$ denota Euler totient función, la cual es una función de la salida de la cantidad de enteros positivos a menos de $n$ que son coprime a $n$.
Así, por ejemplo, $\phi (10)=4$, debido a $1,3,7,9$ (cuatro números enteros positivos) son coprime a $10$ $2,4,5,6,8$ no lo son.
Puede demostrarse que (no hay una única representación $n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ $p_i$ prime (porque de Teorema Fundamental de la Aritmética))
$$\phi(n)=\phi(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k})=(p^\alpha_1-p^{\alpha_1-1})(p_2^{\alpha_2}-p_2^{\alpha_2-1})\cdots(p_k^{\alpha_k}-p_k^{\alpha_k-1})$$
Así, por ejemplo, $\phi(2700)=\phi(2^23^35^2)=(4-2)(27-9)(25-5)=2\cdot 18\cdot 20=720$.
$\phi(n)$ ) y otros (los números de $m$ tal que $a^m\equiv 1\pmod{n}$ puede ser utilizado para reducir los exponentes ($a^E\equiv a^{E\!\pmod {\! m}}\!\pmod {\!n}$), como se muestra más adelante en esta respuesta.
Su problema no es fácilmente accesible mediante el teorema de Euler (utilizando para reducir el exponente no será tan sencillo, ya que es demasiado grande y podemos encontrar pequeños números - $4$ en este ejemplo), pero es una excepción. La mejor estrategia para este tipo de problemas con la exponenciación ($a^E\!\pmod {\!n}$) es encontrar el orden (lo voy a explicar), denotado $\text{ord}_n a$ $a$ modulo $n$, o un múltiplo de ella, y esta es la razón por la búsqueda y uso de $\phi(n), \lambda(n)$ (me voy a presentar más adelante en la respuesta) es útil.
La multiplicación de la orden, que se denota $\text{ord}_n a$ $a$ modulo $n$ es el menos positivo $s$ tal que $a^s\equiv 1\!\pmod {\!p}$.
Así, en nuestro ejemplo, $\text{ord}_{100} 7=4$, ya que el $7^4\equiv 2401\equiv 1\!\pmod {\! 100}$ mientras $7^1,7^2,7^3\not\equiv 1\!\pmod {\!100}$.
Entonces cualquier $t$ tal que $a^t\equiv 1\!\pmod{\!n}$ será divisible por $s$, es decir, $t=sl$ algunos $l\in\mathbb Z$. Observe que $\phi(n),\lambda(n)$ son casos de ese $t$, por lo que son múltiplos de los pedidos.
La razón por la búsqueda de órdenes o múltiplos de ellos (como $\phi(n),\lambda(n)$) es importante en este tipo de problemas es, porque nos permite reducir el exponente. E. g., en el caso de este problema, $$7^{7^{7^{\ldots}}}\equiv 7^{7^{7^{\ldots}}\!\pmod{\!4}}\equiv 7^{(-1)^{7^{\ldots}}\!\pmod {\!4}}\equiv 7^{-1\!\pmod {\!4}}\equiv 7^3\equiv 343\!\!\!\pmod{\!100}$$
La razón por la que podría reducir el exponente modulo $4$ es debido a $7^4\equiv 1\!\pmod{\!100}$, de modo que, por ejemplo, $7^{13}\equiv 7^{4+4+4+1}\equiv 7^47^47^47^1\equiv 1\cdot 1\cdot 1\cdot 7\equiv 7\!\pmod {\!100}$. La razón por la que dijo: "Su problema no es fácilmente accesible mediante el teorema de Euler" es porque la $\phi(100)=40$ es demasiado grande en comparación a $4$. Mathlove la respuesta utiliza la misma idea.
Carmichael función, denotada $\lambda (n)$, se define como el menor $m$ tal que $(a,n)=1\,\Rightarrow\, a^m\equiv 1\!\pmod{\!n}$.
Observe cómo $\phi(n)$ satisface las condiciones, excepto por el 'más pequeño'. Por lo $\lambda(n)$ es simplemente una versión más pequeña de $\phi(n)$ (tenemos $\lambda(n)\le \phi(n)$).
Se puede demostrar que $$\lambda(n)=\begin{cases}\phi(n),\ \ \ n=2,4,p_{\text{odd}}^k\\\frac{1}{2}\phi(n),\ \ \ n=2^k,k\ge 3\\\text{lcm}(\lambda(p_1^{\alpha_1}),\lambda(p_2^{\alpha_2}),\ldots,\lambda(p_k^{\alpha_k}))\ \ \ \text{ otherwise}\end{cases}$$
Así, por ejemplo, (si $k\ge 4$)
$$\lambda(10^k)=\text{lcm}(\lambda(2^k),\lambda(5^k))=\text{lcm}(2^{k-2},4\cdot 5^{k-1})=2^{k-2}5^{k-1}$$
mientras que $\phi(10^k)=(2^k-2^{k-1})(5^{k}-5^{k-1})=2^{k-1}\cdot 4\cdot 5^{k-1}=2^{k+1}5^{k-1}$.
Observe cómo de $k\ge 4$ tenemos $\lambda(10^k)=\frac{\phi(10^k)}{8}$.
$\lambda (n)$, en comparación con $\phi(n)$, hace que sea muy significativamente más fácil encontrar la última $\ge 4$ de los dígitos de un exponentiated entero (dependiendo del exponente - la más pequeña de función lambda puede reducir el exponente más, pero no necesariamente).
