You may also like


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.

The Public Key

Age 16 to 18 Challenge Level:

Here is a similar example: Suppose you want to find $x$ where ($0\leq x\leq 100$) and $17^{13}\equiv x \pmod {101}$. As $17^{13}$ is too large for most calculators to show exactly we start with $17^6=24137569$ and, first dividing this by 101, we find that $17^6=(238985)(101)+84$ so we now know that $17^6\equiv 84 \pmod{101}.$

The next step is to use this to tackle $17^{13}$. $$17^{13}=(17^6)^2 \times 17 $$ $$ \equiv 84^2 \times 17 \equiv 119952 \pmod {101} $$ $$119952 =1187\times 101 + 65 $$ $$\equiv 65 \pmod{101}$$ Hence $x=65$.