Q:

$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:

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$.  

