Euler's theorem for congruences Using Euler's theorem, how to compute:

a) $3^{1000} \pmod{2500}$
b) $7^{1001} \pmod{2500}$
c) $101^{21600} \pmod{81000}$


First note that $(3,2500)=1$ and then compute $\phi(2500)=5^3 \cdot 2 \cdot 4=1000$ .
Now Euler's theorem tells us that :
$$3^{\phi(2500)} \equiv 1 \pmod{2500}$$ or :
$$3^{1000} \equiv 1 \pmod{2500}$$
In the same way $7^{1000} \equiv 1 \pmod{2500}$ so :
$$7^{1001} \equiv 7 \pmod{2500}$$
Finally : $$\phi(81000)=3^3 \cdot 5^2 \cdot 2^2 \cdot 4 \cdot 2=21600$$ and also $(101,81000)=1$ so :
$$101^{21600} \equiv 1 \pmod{81000}$$ 
