2. (Easy/Average) Find the remainder when $14^{100}$ is divided by 45 .
Answer: 31
Solution: Let $\Phi$ denote the Euler's totient function. Since the prime factors of 45 are 3 and 5 only, then
$$
\Phi(45)=45\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=24 \text {. }
$$

Since $\operatorname{gcd}(14,45)=1$, by Euler's Theorem, $14^{24} \equiv 1(\bmod 45)$. So that
$$
14^{100}=\left(14^{24}\right)^{4}\left(14^{4}\right) \equiv 14^{4}(\bmod 45) \equiv 196^{2}(\bmod 45) \equiv 16^{2}(\bmod 45) \equiv 31(\bmod 45)
$$