You may also like

problem icon

Pythagorean Golden Means


problem icon

There's a Limit


problem icon

Mod 7


The Public Key


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