Example 3 Find the remainder when $1996^{2000}$ is divided by 29.
Solution: Since 29 is a prime number and 29|1996, by Fermat's Little Theorem we know
$$
1996^{28} \equiv 1(\bmod 29)
$$

Therefore, $1996^{2000}=1996^{28 \times 71+12} \cong 1996^{12}(\bmod 29)$.
Also, $1996=69 \times 29-5$, so
$$
1996^{12} \equiv(-5)^{12} \equiv(-4)^{6} \equiv 6^{2} \equiv 7(\bmod 29) \text {. }
$$

Thus, the remainder when $1996^{2000}$ is divided by 29 is 7.