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=(\genfrac{}{}{0ex}{}{100}{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.