### Purr-fection

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

### Old Nuts

In turn 4 people throw away three nuts from a pile and hide a quarter of the remainder finally leaving a multiple of 4 nuts. How many nuts were at the start?

### Mod 7

Find the remainder when 3^{2001} is divided by 7.

# Remainder Hunt

##### Stage: 5 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.