Sum of the last four digits of $3^{2015}$ If $N = 3^{2015}$, what is the sum of the last four digits of $N$?
$(A)21$ $(B)22$ $(C)23$ $(D)24$
It is not possible using a calculator, so how can I do it? Hints are appreciated.
 A: A variation, I think a bit simpler, of ADG's answer.  We have
$$\eqalign{
  3^{2015}
  &=3\times(10-1)^{1007}\cr
  &=\color{red}{3}\left(10^{1007}-\cdots-\binom{1007}410^4+{}\right.\cr
  &\qquad\qquad\left.{}+\color{red}{\binom{1007}310^3-\binom{1007}210^2+1007\times10-1}\right)\cr}$$
and all except the red parts are irrelevant.

For the remaining calculations, we only need the last digit of $\binom{1007}3$, so
$$\binom{1007}3=\frac{1007\times1006\times1005}{3\times2\times1}
  =1007\times503\times335=\underbrace{\cdots\ \cdots\ \cdots}_{\rm irrelevant\ digits}\cdots5\ .$$
Likewise
$$\binom{1007}{2}=1007\times503=\cdots21\ .$$
So, without using a calculator at any stage, the last four digits of the number are given by (hover to see the answer)


 $$3\times(5000-2100+70-1)=8907$$

and the total is

 $$24\ .$$

A: We have $3^{\phi(1000)}=3^{400}\equiv 1\pmod{1000}$, hence $3^{2015}\equiv 3^{15}\pmod{1000}$. The latter can be computed by repeated squaring modulo $1000$.
A: The answer is D 24 the first four digits are 8907
I used BT to solve the question
$$3^{2015}=-3(1-10)^{1007}=-3(1-10*1007+100*1007*1006/2-1000*1007*10066*1005/6+........)$$
$$3^{2015}=-3(1-10)^{1007}=-3(1-70+2100-5000)$$
$$3^{2015}=-3(1-10)^{1007}=-3(-2969)=8907$$ 
A: Read about Carmichael function. $$\lambda(10\ 000)=\lambda(2^45^4)=\text{lcm}(\lambda(2^4),\lambda(5^4))=\text{lcm}\left(\frac{1}{2}\phi(2^4),\phi(5^4)\right)=\text{lcm}(4,500)=500$$
$$3^{2015}\equiv 3^{2015\pmod {\lambda(10\ 000)}}\equiv 3^{2015\pmod{500}}\equiv 3^{15}\equiv 8907\pmod {10\, 000}$$
