Last three digits of 23^320 What is the best way to compute the last three digits of $23^{320}$? I know one way is by starting of $23^2$ and finding the last three digits, then squaring those (calculating $23^4 \pmod {1000}$) and getting the last three digits and so on until you reach $23^{320}$. Is there any easier method?
 A: $201$
(Using "23**320" in Python3.)
Or, a marginally different twist that does not involve totients (directly, at least):
Since $320 = 5 \cdot 2^6$, we have
$23^5 = 343 \mod 1000$
$343^2 = 649 \mod 1000$
$649^2 = 201 \mod 1000$
Now notice that $(200n+1)^2 = 200(2n)+1 \mod 1000$, hence 
$(200n+1)^{2^4} = 200(16)+1 = 201\mod 1000$.
A: Some ideas:
Since $10^3=5^3\times 2^3$, we can try work independently. And use the Chinese remainder theorem
The totient function of $125$ is easily seen to be $100$, so acording to Euler's theorem you have that $23^{100} \equiv 1 \pmod{125}$, and therefore $23^{300}\equiv1 \pmod{125}$. Additional computation shows that $23^{320}\equiv 76 \pmod{125}$. Set $a_1=76$.
The other case is maybe easier, since $\phi(8)=4$, then $23^4 \equiv 1 \pmod{8}$. Since $4$ divides $320$ then you have that $23^{320}\equiv 1 \pmod{8}$. Set $a_2=1$.
The last step would be to use the Chine Remainder Theorem to recover the whole answer.
We need to solve two congruences to apply this theorem to obtain numbers $b_1$ and $b_2$. 
$$ 8x \equiv 1 \pmod{125}$$
$$ 125x \equiv 1 \pmod{8}$$
The solutions are $47$ in the first case and $5$ in the second case. From here we obtain the following expression (it's just the recipe of the Chinese remainder theorem)
$$x\equiv 8*a_1*b_1 +125*a_2*b_2 = 8*76*47+125*5= 29201 \equiv 201 \pmod{1000}$$
This doesn't seem simple enough though. But is another approach. This answer is correct. I verified.
