Remainder hunt

What are the possible remainders when the $100^{th}$ power of an integer is divided by $125$? This is a solution from Yatir Halevi, Maccabim-Reut High School, Israel.

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

$$a_k = {100 \choose k} 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 \rm {something}+ q^{100}$. But we know that $0 \leq q \leq 4$ so the remainder when the $100^{th}$ power is divided by $125$ is the same as the remainder for $q^{100}$, with $q = 0, 1, 2, 3, \rm{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

\[2^{100}\equiv 2^2\times 2^{7\times 14} \] \[ \equiv 4\times 3^{14}\] \[ \equiv 4\times 3^4 \times 3^{5\times 2}\] \[ \equiv 4\times 3^4 \times 243^2 \] \[ \equiv 4\times 81\times (-7)^2 \] \[= 4\times 81\times 49 \] \[= 15876 \equiv 1 \]

Similarly

\[3^{100}\equiv 3^{5\times 20} \] \[\equiv 243^{20}\] \[\equiv (-7)^{20}\] \[\equiv (-32)^6\times (-7)^2\] \[\equiv 2^{30} \times 49 \] \[\equiv 2^{7 \times 4}\times 4 \times 49 \] \[\equiv 3^4 \times 4 \times 49 \] \[= 15876 \equiv 1\]

If $q=4$ then $q^{100} = \big(2^{100}\big)^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.