You may also like

Double Time

Crack this code which depends on taking pairs of letters and using two simultaneous relations and modulus arithmetic to encode the message.

Modular Fractions

We only need 7 numbers for modulus (or clock) arithmetic mod 7 including working with fractions. Explore how to divide numbers and write fractions in modulus arithemtic.

Purr-fection

What is the smallest perfect square that ends with the four digits 9009?

Remainder Hunt

Age 16 to 18
Challenge Level

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.