Euler's theorem for congruences

Question

Using Euler's theorem, how to compute:

a) $3^{1000} \pmod{2500}$

b) $7^{1001} \pmod{2500}$

c) $101^{21600} \pmod{81000}$

Answer 1

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