You may also like

problem icon

Pythagorean Golden Means

Show that the arithmetic mean, geometric mean and harmonic mean of a and b can be the lengths of the sides of a right-angles triangle if and only if a = bx^3, where x is the Golden Ratio.

problem icon

There's a Limit

Explore the continued fraction: 2+3/(2+3/(2+3/2+...)) What do you notice when successive terms are taken? What happens to the terms if the fraction goes on indefinitely?

problem icon

Mod 7

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

The Public Key

Stage: 5 Challenge Level: Challenge Level:3 Challenge Level:3 Challenge Level:3

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$.