Calculating remainder of $666^{666}$ when divided by $1000$.

Question

I want to calculate the remainder of $666^{666}$ when divided by $1000$. But for the usual methods I use the divisor is very big. Furthermore $1000$ is not a prime, $666$ is a zero divisor in $\mathbb{Z}_{1000}$.

I have some thought about it, here it is...

1. There does not exist $n\in\mathbb{N}$ such that $666^n\equiv 1\,\pmod{\!1000}$
2. $666$ may be nilpotent with degree $n \leq 666$. In this case $666^{666}\equiv 0\,\pmod{\!1000}$.
3. $666$ may be nilpotent with degree $n \geq 666$. If I don't know the exact degree I don't know what to do here.
4. $666$ might be non-nilpotent. For example $4\in\mathbb{Z}_6$ is idempotent. But $666$ is not idempotent, as $666^2\equiv 556\,\pmod{\!1000}$, so even if $666$ is not nilpotent I don't see the answer so easily. If $666$ is not nilpotent, and as it is not idempotent, I don't know what to do here.

Any idea?

Answer 1

$666^{666}$ is certainly a multiple of $8$, and Euler's theorem tells us that $$666^{666}\equiv41^{66}\pmod{125}$$ Now, we can do, for example: $$41^{66}\equiv56^{33}\equiv56\cdot11^{16}\equiv56\cdot4^8\equiv56\cdot6^2\equiv16\pmod{125}$$

Thus, since $16$ is a multiple of $8$,

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

Answer 2

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

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

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

Let us find $\displaystyle3^{-666}\cdot2^{666-3}\pmod{\dfrac{1000}8}$

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

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

Now $\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

Here's a relatively naïve approach. Start listing powers of $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}$$

A pattern is starting to emerge: $$\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}$$

Will this pattern continue? Observe that $666 \cdot 200 \equiv 200 \pmod{1000},$ so $666^5 \cdot 200 \equiv 200 \pmod{1000},$ and so if $$666^n \equiv 666^{n-5} + 200 \pmod{1000}$$ then $$\begin{eqnarray} 666^{n+5} &\equiv& 666^5 (666^{n-5} + 200) \pmod{1000} \\ &\equiv& 666^n + 200 \pmod{1000}. \end{eqnarray}$$ The identity $666^{n+5} \equiv 666^n + 200 \pmod{1000}$ therefore holds for any $n \geq 3$.

Repeat this five times and we find that for $n\geq 3,$ $$666^{n+25} \equiv 666^n \pmod{1000}.$$

Since $666 \equiv 16 \pmod{25},$ it follows that $$\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}$$

Now $\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}$

So, we need $S\equiv\displaystyle4^{666}-\binom{666}14^{665}\cdot670^1\pmod{1000}$

Now $\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}$

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

and $\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

Brute Force Approach

We can use the Square and Multiply Algorithm.

Noting that $666=1010011010_\text{two}$, we will write the exponents in base two: $$ \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} $$

---

A Bit More Intelligent Approach

We can reduce the problem by breaking down the modulus into prime factors: $$ 666^{666}\equiv0\pmod{8} $$ Since $\phi(125)=100$, $$ 666^{666}\equiv41^{66}\pmod{125} $$ We can still use the Square and Multiply Algorithm in this situation. Since $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} $$ Thus, $$ 666^{666}\equiv0\pmod{8}\qquad\text{and}\qquad666^{666}\equiv16\pmod{125} $$ Since $16\equiv0\pmod{8}$, the solution to the Chinese Remainder Problem is immediately evident. That is, $$ 666^{666}\equiv16\pmod{1000} $$

Answer 6

$\varphi(125)=100$, so by Euler's theorem and Binomial theorem:

$$666^{666}\equiv 41^{666\pmod{\! 100}}\equiv (1+40)^{66}\pmod{\! 125}$$

$$\equiv 1+\binom{66}{1}40+\underbrace{\binom{66}{2}}_{\text{divisible by }5}40^2\equiv 1+(75-9)40\pmod{\! 125}$$

$$\equiv 1+(1-10)(50-10)\equiv 1+50-10+100\equiv 16\pmod{\! 125}$$

Since $(125,8)=1$:

$$125,8\mid 666^{666}-16\iff 1000\mid 666^{666}-16$$