Encuentre los dos últimos dígitos de $9^{{9}^{9}}$

Question

Tengo que encontrar las dos últimas cifras decimales del número $9^{{9}^{9}}$ .

Eso es lo que hice:

$$m=100 , \phi(m)=40, a=9$$ $$(100,9)=1, \text{ so from Euler's theorem,we have :} 9^{40} \equiv 1 \pmod{100}$$

$$9^{{9}^{9}} \equiv 9^{9^{2+2+2+2+1}} \equiv 9^{9^2 \cdot 9^2 \cdot 9^2 \cdot 9^2 \cdot 9} \equiv 9^{81 \cdot 81 \cdot 81 \cdot 81 \cdot 9} \equiv 9^{(40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot 9} \equiv (9^{(40+40+1)})^{(40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot 9} \equiv 9^9 \equiv 9^4 \cdot 9^4 \cdot 9 \equiv 6561 \cdot 6561 \cdot 9 \equiv 3721 \cdot 9 \\ \equiv 21 \cdot 9 \equiv 89 \pmod{100}$$

Entonces, los dos últimos dígitos son $8 \text{ and } 9$ . $$$$But,is there also an other way two calculate the last two digits of $ 9^{{9}^{9}}$ o la anterior es la única?

Answer 1

Observación clave: Por el teorema del binomio, para cada impar $k$ , $(10-1)^k=n+10\cdot k-1$ para algún número entero $n$ que es un múltiplo de $100$ . Desde $10\cdot k=10\cdot\ell(k)\bmod{100}$ donde $\ell(k)$ denota el último dígito de $k$ Esto demuestra que, para cada impar $k$ , $9^k=10\cdot \ell(k)-1\bmod{100}$ .

Primera aplicación: $\ell(9)=9$ por lo que la observación clave anterior da como resultado $9^9=10\cdot \ell(9)-1=89\bmod{100}$ .

Segunda aplicación: nuestra primera aplicación implica que $\ell(9^9)=9$ Por lo tanto, utilizando la observación clave una vez más, pero esta vez para $k=9^9$ se obtiene $9^k=10\cdot\ell(k)-1=89\bmod{100}$ .

Y así sucesivamente: por cada torre de nueves, $9^{9^{9^{9^{\cdots}}}}=89\bmod{100}$ .

Answer 2

También puedes hacer simplemente la exponenciación modular y tomar nota de los puntos.

Los poderes de $9 \mod 100$ son: 1, 9, 81, 29, 61, 49, 41, 69, 21, 89, 1, 9, 81, 29, 61, 49, ... Tienen un periodo de $10$ . Esto significa que si $n \equiv 9 \mod 10$ entonces $9^n \equiv 89 \mod 100$ . Desde $9^9 = 387,420,489$ Esto significa que $9^{9^9} \equiv 89 \mod 100$ .

Answer 3

Dejemos que $k$ sea el orden de $9$ mod $100$ . Entonces $$1\equiv 9^k=(10-1)^k \equiv 10\binom{k}{1}\cdot 10(-1)^{k-1}+(-1)^k\pmod{100}$$ Esto implica que $1=\pm (10k-1)\pmod{100}$ . El mínimo número entero que satisface esta condición es $k=10$ . De ello se desprende que $$9^{9^9} \equiv 9^9 \equiv 9^{-1}\equiv 89\pmod{100}.$$

Answer 4

Una variante para minimizar el tiempo de cálculo del orden de $9\bmod100$ por el Teorema del resto chino , $$\mathbf Z/100\mathbf Z\simeq\mathbf Z/4\mathbf Z\times \mathbf Z/25\mathbf Z. $$ Ahora $\varphi(25)=20$ y $9\equiv 1\mod4$ . Por lo tanto, $9^{20}\equiv 1\mod100$ , por lo que el orden de $9$ es un divisor de 20.

Algoritmo de exponenciación rápida muestra que tiene orden $10$ . Así, $$9^{9^9}\equiv9^{9^9\bmod 10}\equiv 9^{(-1)^9\bmod 10}\equiv 9^{-1}\mod100. $$ La identidad de Bézout $\;100_11\cdot 9=1\;$ entonces muestra $\; 9^{-1}\equiv -11\equiv 89\mod100$ .