<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] Without the Chinese Remainder Theorem :
$$
\eqalign{
7^5 &\equiv 11 \pmod {221} \cr
7^{75} &\equiv 11^{15} \pmod {221} \cr
7^{77} &\equiv 7^2 \cdot 11^{15} \pmod {221} \cr
}
$$
Also
$$
\eqalign{
11^3 &\equiv 5 \pmod {221} \cr
11^{15} &\equiv 5^{5} \pmod {221} \cr
}
$$
To conclude
$$
7^{77} \equiv 7^2 \cdot 11^{15} \equiv 7^2 \cdot 5^5 \equiv  49 \cdot 31 \equiv 193
$$
</s>