Every integer can be expressed in the following way: $5p+q$, where $p$ and $q$ are certain integers and $0\le q\le 4$. Expanding $(5p+q{)}^{100}$ with the aid of the binomial theorem we get the general term:

${\displaystyle a_k=\left(\genfrac{}{}{0ex}{}{100}{k}\right)5^{100-k}{p}^{100-k}{q}^k.}$

All the terms except the last one $q^{100}$ are divisible by 125. What we get is a number of this sort: $125\times \mathrm{something}+q^{100}$. But we know that $0\le q\le 4$ so the remainder when the 100th power is divided by 125 is the same as the remainder for $q^{100}$, with $q=0,1,2,3,\mathrm{or}4$.

If $q=0$ then $q^{100}=0$; if $q=1$ then $q^{100}=1$.

Let $q=2$; we want the remainder after $2^{100}$ is divided by 125, so we work modulo 125. Now $2^7=128\equiv 3$ where the symbol ' $\equiv$' indicates that the numbers have the same remainder after division by 125. For $q=3$ it follows that $3^5=243\equiv -7$. Thus

${\displaystyle 2^{100}\equiv 2^2\times 2^{7\times 14}}$

${\displaystyle \equiv 4\times 3^{14}}$

${\displaystyle \equiv 4\times 3^4\times 3^{5\times 2}}$

${\displaystyle \equiv 4\times 3^4\times {243}^2}$

${\displaystyle \equiv 4\times 81\times (-7{)}^2}$

${\displaystyle =4\times 81\times 49}$

${\displaystyle =15876\equiv 1}$

Similarly

${\displaystyle 3^{100}\equiv 3^{5\times 20}}$

${\displaystyle \equiv {243}^{20}}$

${\displaystyle \equiv (-7{)}^{20}}$

${\displaystyle \equiv (-32{)}^6\times (-7{)}^2}$

${\displaystyle \equiv 2^{30}\times 49}$

${\displaystyle \equiv 2^{7\times 4}\times 4\times 49}$

${\displaystyle \equiv 3^4\times 4\times 49}$

${\displaystyle =15876\equiv 1}$

If $q=4$ then $q^{100}=(2^{100}{)}^2\equiv 1.$

So we can either get 0 or 1 as a remainder and we get 0 if the original number is a multiple of 5 and 1 otherwise.