How to calculate remainder using Fermat's Little Theorem I want calculate remainder when $2^{1000}$ is divided by $5^{4}$
Can I calculate it using Fermat's Little Theorem?
 A: A very useful concept here is Euler totient function.
We denote $\varphi(m) : \mathbb{N} \to \mathbb{N}$ an arithmetical function. $\varphi(m)$ means the number of positive integers which are coprime to $n$. This function has some useful and interesting properties like these:

*

*Incomplete multiplicity. For $m, n \in \mathbb{N}$, with $(m, n) = 1$, $\varphi(m) \cdot \varphi(n) = \varphi(mn)$.

*Euler's product formula. If $m$ is an integer, we can calculate
$$\varphi(n) = n \prod_{p \ | \ n} \left(1 - \frac{1}{p}\right).$$

*Euler's product formula for prime powers. If $p$ is a prime number and $k$ a positive integer, we can calculate
$$\varphi(p^k) = p^k \left(1 - \frac{1}{p}\right).$$

*Gauss's formula. If $n$ is a natural number, this formula states that
$$\sum_{d \ | \ n} \varphi(d) = n.$$

*Euler's theorem. If $a$ is an integer and $m$ a natural number, then
$$a^{\varphi(m)} \equiv 1 \ (\text{mod} \ m).$$
From this theorem derives directly Fermat's little theorem, with the only mention that for a prime number $p$, $\varphi(p) = p - 1$, obviously by definition of $\varphi$-function.

All this being known about this interesting number theory application, the problem looks much more easy. We have, by Euler's theorem
$$2^{\varphi(5^4)} \equiv 1 \ (\text{mod} \ 5^4).$$
But, by Euler's product formula for prime powers,
$$\varphi(5^4) = 5^4 \cdot \frac{4}{5} = 125 \cdot 4 = 500.$$
So
$$2^{500} \equiv 1 \ (\text{mod} \ 5^4),$$
meaning that
$$2^{1000} \equiv (2^{500})^2 \equiv 1 \ (\text{mod} \ 5^4)$$
And this finishes our computation using Euler's theorem. It doesn't look like Fermat may have any link in this exercise/problem.
Sources:
[1]. https://www.wikiwand.com/en/Euler%27s_totient_function
[2]. how to calculate $\phi (625)$? Eulers's Totient
