$777^{401} \pmod {1000}$ is? here's an arithmetic question : find the last $3$ digits of $777^{401}$. I don't know where to start. The chinese remainder theorem gives a double congruence modulo $8$ and $125$ but I don't think this is really helping, there might be a simpler way. Any help is welcome !
 A: Since $777\equiv 1 \pmod{2^3}$ and $777\equiv 27\pmod{5^3}$. Moreover  $\varphi(5^3)=4\cdot 5^2$ and $401 \equiv 1\pmod{100}$ therefore we have
$777^{401}\equiv 1\pmod{8}$ and $777^{401} \equiv 27\pmod{125}$. 
Then by CRT the solution exists and it is unique modulo $1000$, i.e.
$$
777^{401}\equiv 777 \pmod{1000}.
$$
A: $$777=7\times 3\times 37~\textrm{and}~1000=5^3\times 2^3\implies \gcd(777,1000)=1$$
Hence, we use Euler's theorem. We have, $$\phi(1000)=\phi(5^3\times 2^3)=1000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=400$$
Now, according to Euler's theorem, we have,
$$777^{\phi(1000)}\equiv 1\pmod{1000}\implies 777^{400}\equiv 1\pmod{1000}$$
$$\implies 777^{401}=777^{401~\bmod~400}\equiv 777^1\equiv 777\pmod{1000}$$
A: That is a good place to start, but not necessary the way the problem is given.
Hint 1:

What theorems do you know that can help reduce exponents in a congruence? (If you don't know the answer look at Hint 2)

Hint 2:
this theorem (click after looking at hint 1)
Solution:

Consider $\varphi(8)$ and $\varphi(125)$. $\varphi(8)=4 | 400$, and $\varphi(125)=100 | 400$, and since $\varphi$ is multiplicative $\varphi(1000)=400 | 400$. So by Euler's theorem, if 777 is relatively prime to 1000 (which it is), $777^{401}= 777^{400}\cdot 777 \equiv 777 \pmod{1000}$. In fact, by Chinese Remainder Theorem, $777^{100}\equiv 1 \pmod{1000}$ since $100$ is the least common multiple of $4$ and $100$.  

A: Use Euler's theorem: As $\phi(1000)= \phi(125)\times \phi(8)= 400$ we have  $777^{400}\equiv1$ mod $1000$, as $\gcd(777,1000)=1$. So the answer is $777^{401}\equiv777$ mod $1000$.
