Copyright © University of Cambridge. All rights reserved.
'The Public Key' printed from https://nrich.maths.org/
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$.