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?
 A: We have $221=13 \cdot 17$, i.e. you should compute


*

*$7^{77} \pmod {13}$ (Result will be some $0 \leq a \leq 12$)

*$7^{77} \pmod {17}$ (Result will be some $0 \leq b \leq 16$)


Afterwards, you use the Chinese Remainder Theorem to find the unique $0 \leq x \leq 220$ with $x \equiv a \pmod {13}$ and $x \equiv b \pmod {17}$.
A: 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}$.
A: 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
$$
