The last four!

Euler's Theorem states that:

$a^{\phi(n)} \equiv 1$ (mod $n$ ) if a and n are coprime.

$\phi(n)$ is equal to the number of positive integers less than or equal to n that are coprime to n : Euler's totient function.

$\phi(2500) = 1000$ so $3^{1000} \equiv 1$ (mod 2500) because 3 and 2500 are coprime.

Also, $3^{1000} \equiv (3^2)^{500}$ (mod 8)

$\equiv 1^{500}$ (mod 8)

$\equiv 1$ (mod 8). Now using Chinese Remainder Theorem, $3^{1000} \equiv 1$ (mod 20000) and therefore $3^{1000} \equiv 1$ (mod 10000) so the last four digits are 0001. Adding 1000 gives the answer: $\boxed{1001}$ .

3^1000= 1 mod 10000

*= means congruence

And add 100, so we get 1000+1= 1001