Copyright © University of Cambridge. All rights reserved.
'Remainder Hunt' printed from https://nrich.maths.org/
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.