<s>[INST] How can I solve $7^{77}\mod 221$ How is it possible to solve this without calculator etc.: $$7^{77} \mod 221$$
I started with:
\begin{align}
7&\equiv 7 \mod 221 \\
7^2 &\equiv 49 \mod 221 \\
7^4 &\equiv \ ? \mod 221
\end{align}
Sure i can calculate this by my own, but is there a trick to calclulate this with any tools?
 [/INST] Use the Chinese Remainder Theorem.  Note that $221=13\times17$.  Modulo $13$ we have
$$7^2\equiv-3\ ,\quad 7^6\equiv(-3)^3\equiv-1$$
and so
$$7^{77}=(7^6)^{12}7^5\equiv7^5=(7^2)(7^2)7\equiv(-3)(-3)7=63\equiv-2\ .$$
Modulo $17$ we have
$$7^2\equiv-2\ ,\quad 7^8\equiv(-2)^4\equiv-1$$
and so
$$7^{77}=(7^8)^97^5\equiv-7^5\equiv-(-2)(-2)7\equiv6\ .$$
So you have to solve simultaneously
$$x\equiv-2\pmod{13}\ ,\quad x\equiv6\pmod{17}\ .$$
Standard methods (look up Chinese Remainder Theorem) give $x\equiv193\pmod{221}$.
</s>