Calcular el resto de $666^{666}$ cuando se divide por $1000$.

Question

Quiero calcular el resto de $666^{666}$ cuando se divide por $1000$. Pero para los métodos habituales, yo uso el divisor es muy grande. Además $1000$ no es un número primo, $666$ es un divisor de cero en a $\mathbb{Z}_{1000}$.

Tengo algo pensado, aquí está...

1. No existe $n\in\mathbb{N}$ tal que $666^n\equiv 1\,\pmod{\!1000}$
2. $666$ puede ser nilpotent con grado de $n \leq 666$. En este caso,$666^{666}\equiv 0\,\pmod{\!1000}$.
3. $666$ puede ser nilpotent con grado de $n \geq 666$. Si no sé el grado exacto no sé qué hacer aquí.
4. $666$ podría no nilpotent. Por ejemplo, $4\in\mathbb{Z}_6$ es idempotente. Pero $666$ no es idempotente, como $666^2\equiv 556\,\pmod{\!1000}$, por lo que incluso si $666$ no es nilpotent no veo la respuesta tan fácilmente. Si $666$ no es nilpotent, y como no es idempotente, no sé qué hacer aquí.

Alguna idea?

Answer 1

$666^{666}$ es sin duda un múltiplo de $8$, y el teorema de Euler nos dice que $$666^{666}\equiv41^{66}\pmod{125}$$ Ahora, que podemos hacer, por ejemplo: $$41^{66}\equiv56^{33}\equiv56\cdot11^{16}\equiv56\cdot4^8\equiv56\cdot6^2\equiv16\pmod{125}$$

Así, desde la $16$ es un múltiplo de a $8$,

$$666^{666}\equiv 16\pmod{1000}$$

Answer 2

Como $3\cdot666=2000-2\equiv-2\pmod{1000}$

$(3\cdot666)^{666}\equiv(-2)^{666}\pmod{1000}$

Como $(3,1000)=1,666^{666}\equiv(3^{-1})^{666}2^{666}\pmod{1000}$

Vamos a encontrar $\displaystyle3^{-666}\cdot2^{666-3}\pmod{\dfrac{1000}8}$

Como $\displaystyle\phi(125)=100,-666\equiv34,663\equiv63\pmod{100}$

$\displaystyle3^{-666}\cdot2^{663}\equiv3^{34}2^{63}\pmod{125}$

Ahora $\displaystyle3^5\equiv-7\pmod{125},$ $\displaystyle3^{34}=3^4(3^5)^6\equiv3^4(-7)^6\equiv(80+1)(50-1)^3\equiv3\cdot50-80-1\pmod{125}\equiv69$

$2^7\equiv3\pmod{125}\implies2^{63}=(2^7)^9\equiv3^9\pmod{125}$

$3^9=3^{-1}(3^5)^2\equiv3^{-1}(-7)^2\equiv42\cdot49\equiv(50-8)(50-1)\equiv8-9\cdot50\equiv-67$

$\implies3^{34}2^{63}\equiv69(-67)\equiv(70-1)(-70+3)\equiv2\pmod{125}$

$\implies3^{-666}2^{666}\equiv2^3\cdot2\pmod{2^3\cdot125}$

Answer 3

He aquí una relativamente enfoque ingenuo. Inicio listado de los poderes de $666$ modulo $1000$:

$$\begin{eqnarray} 666^2 &\equiv& 556 \pmod{1000}, \\ 666^3 &\equiv& 296 \pmod{1000}, \\ 666^4 &\equiv& 136 \pmod{1000}, \\ 666^5 &\equiv& 576 \pmod{1000}, \\ 666^6 &\equiv& 616 \pmod{1000}, \\ 666^7 &\equiv& 256 \pmod{1000}, \\ 666^8 &\equiv& 496 \pmod{1000}, \\ 666^9 &\equiv& 336 \pmod{1000}, \\ 666^{10} &\equiv& 776 \pmod{1000}, \\ 666^{11} &\equiv& 816 \pmod{1000}, \\ 666^{12} &\equiv& 456 \pmod{1000}. \end{eqnarray}$$

Un patrón está empezando a surgir: $$\begin{eqnarray} 666^8 &\equiv& 666^3 + 200 \pmod{1000}, \\ 666^9 &\equiv& 666^4 + 200 \pmod{1000}, \\ 666^{10} &\equiv& 666^5 + 200 \pmod{1000}, \\ 666^{11} &\equiv& 666^6 + 200 \pmod{1000}, \\ 666^{12} &\equiv& 666^7 + 200 \pmod{1000}. \end{eqnarray}$$

Se que este patrón continúe? Observar que $666 \cdot 200 \equiv 200 \pmod{1000},$ por lo $666^5 \cdot 200 \equiv 200 \pmod{1000},$ y así si $$666^n \equiv 666^{n-5} + 200 \pmod{1000}$$ entonces $$\begin{eqnarray} 666^{n+5} &\equiv& 666^5 (666^{n-5} + 200) \pmod{1000} \\ &\equiv& 666^n + 200 \pmod{1000}. \end{eqnarray}$$ La identidad de $666^{n+5} \equiv 666^n + 200 \pmod{1000}$ por lo tanto se cumple para cualesquiera $n \geq 3$.

Repite esto cinco veces, y encontramos que, para $n\geq 3,$ $$666^{n+25} \equiv 666^n \pmod{1000}.$$

Desde $666 \equiv 16 \pmod{25},$ de ello se sigue que $$\begin{eqnarray} 666^{666} &\equiv& 666^{16} \pmod{1000} \\ &\equiv& 666^{11} + 200 \pmod{1000} \\ &\equiv& 666^{6} + 400 \pmod{1000} \\ &\equiv& 16 \pmod{1000}. \end{eqnarray}$$

Answer 4

$$666^{666}=(670-4)^{666}=(4-670)^{666}$$

$$(4-670)^{666}\equiv4^{666}-\binom{666}14^{665}\cdot670^1+\binom{666}24^{664}\cdot670^2\pmod{1000}$$

Ahora $\displaystyle\binom{666}2\equiv0\pmod5$ $\displaystyle\implies4^{664}\binom{666}2\equiv0\pmod{10}$

$\displaystyle\implies4^{664}\binom{666}2\cdot670^2\equiv0\pmod{1000}$

Por lo tanto, tenemos $S\equiv\displaystyle4^{666}-\binom{666}14^{665}\cdot670^1\pmod{1000}$

Ahora $\displaystyle\binom{666}1\cdot67=(670-4)(70-3)\equiv-280-210+12\equiv22\pmod{100}$

$\displaystyle\implies\binom{666}14^{665}\cdot670^1\equiv220\pmod{1000}$

$S\equiv4^{666}-4^{665}\cdot220\equiv-4^{665}(220-4)\equiv-27\cdot2^{3+2\cdot665}\pmod{1000}$

Ahora $\displaystyle\phi(125)=100,2\cdot665\equiv30\pmod{100}\implies2^{2\cdot665}\equiv2^{30}\pmod{125}$

y $\displaystyle2^7\equiv3\pmod{125},2^{30}=2^2(2^7)^4\equiv4\cdot3^4\equiv74\pmod{125}$

$\displaystyle\implies -27\cdot2^{2\cdot665}\equiv-27\cdot74\pmod{125}\equiv-(25+2)(75-1)\equiv2\pmod{125}$

$\displaystyle\implies-27\cdot2^{3+2\cdot665}\equiv2\cdot2^3\pmod{125\cdot2^3}$

Answer 5

Aproximación De Fuerza Bruta

Podemos utilizar el Cuadrado y Multiplicar Algoritmo.

Tomando nota de que $666=1010011010_\text{two}$, vamos a escribir los exponentes en base dos: $$ \begin{align} 666^0&\equiv\hphantom{00}1\pmod{1000}\\ 666^1&\equiv666\pmod{1000}&\text{multiply by }666\\ 666^{10}&\equiv556\pmod{1000}&\text{square}\\ 666^{100}&\equiv136\pmod{1000}&\text{square}\\ 666^{101}&\equiv576\pmod{1000}&\text{multiply by }666\\ 666^{1010}&\equiv776\pmod{1000}&\text{square}\\ 666^{10100}&\equiv176\pmod{1000}&\text{square}\\ 666^{101000}&\equiv976\pmod{1000}&\text{square}\\ 666^{101001}&\equiv\hphantom{0}16\pmod{1000}&\text{multiply by }666\\ 666^{1010010}&\equiv256\pmod{1000}&\text{square}\\ 666^{1010011}&\equiv496\pmod{1000}&\text{multiply by }666\\ 666^{10100110}&\equiv\hphantom{0}16\pmod{1000}&\text{square}\\ 666^{101001100}&\equiv256\pmod{1000}&\text{square}\\ 666^{101001101}&\equiv496\pmod{1000}&\text{multiply by }666\\ 666^{1010011010}&\equiv\hphantom{0}16\pmod{1000}&\text{square}\\ \end{align} $$

---

Un Poco Más De Enfoque Inteligente

Podemos reducir el problema por romper el módulo en factores primos: $$ 666^{666}\equiv0\pmod{8} $$ Desde $\phi(125)=100$, $$ 666^{666}\equiv41^{66}\pmod{125} $$ Todavía podemos utilizar el Cuadrado y Multiplicar el Algoritmo en esta situación. Desde $66=1000010_\text{two}$ $$ \begin{align} 41^0&\equiv\hphantom{00}1\pmod{125}\\ 41^1&\equiv\hphantom{0}41\pmod{125}&\text{multiply by }41\\ 41^{10}&\equiv\hphantom{0}56\pmod{125}&\text{square}\\ 41^{100}&\equiv\hphantom{0}11\pmod{125}&\text{square}\\ 41^{1000}&\equiv\hphantom{}121\pmod{125}&\text{square}\\ 41^{10000}&\equiv\hphantom{0}16\pmod{125}&\text{square}\\ 41^{100000}&\equiv\hphantom{00}6\pmod{125}&\text{square}\\ 41^{100001}&\equiv\hphantom{}121\pmod{125}&\text{multiply by }41\\ 41^{1000010}&\equiv\hphantom{0}16\pmod{125}&\text{square} \end{align} $$ Por lo tanto, $$ 666^{666}\equiv0\pmod{8}\qquad\text{y}\qquad666^{666}\equiv16\pmod{125} $$ Desde $16\equiv0\pmod{8}$, la solución para el Resto Chino Problema es inmediatamente evidente. Es decir, $$ 666^{666}\equiv16\pmod{1000} $$