[Math] Last digits using Euler’s theorem

Question

Euler's theorem says:

$$a^{\varphi(m)} \equiv 1 \pmod{m}$$

Find $$22^{41} \pmod{10}$$

Obviously, you have to gun for $\varphi(10)$.

Let $a = 22$

$$22^{\varphi{10}} \equiv 1 \pmod{10}$$

But what should I do?

Answer 1

The way to solve this is to use Chinese Remainder Theorem in combination with Euler's theorem.

Clearly, $22^{41} \equiv 0 \pmod 2$. $22^{41} \equiv 2^{41} \pmod 5 = (2^4)^{10} \times 2 \pmod 5 = 2 \pmod 5$ using Euler's theorem. Combining the two results using CRT, we obtain $22^{41} \equiv 2 \pmod {10}$.