Arithmetic with Large modular exponent and repeated squaring, such as $10^{221}$ (mod $13$). How would you compute $10^{221}$ mod $13$ by repeated squaring? I just started studying discrete mathematics and I think this would help me in the future. I looked at this example Computing large modular numbers but it kind of didn't make sense to me. Also how could you use Fermat's Little Theorem for this question. Note that I made this questions up myself so I hope it works.
 A: First, find $10^2 \pmod{13}=9$.  Find $10^4=(10^2)^2\equiv 9^2\equiv 3 \pmod{9}$.  Find $10^8=(10^4)^2\equiv 3^2\equiv 9 \pmod{13}$.  Find $10^{16}, 10^{32}, 10^{64}, 10^{128}$ by continuing in this fashion.  Lastly, write $221$ in base $2$ as $221=128+64+16+8+4+1$.  Hence, we can find $10^{221}=10^{128}10^{64}10^{16}10^{8}10^410^210^1$, and we take the whole thing mod $13$ to get $4$.
A: Fermat's Little Theorem tells you that $10^{12} \equiv 1 \pmod{13} $. Hence, 
$$10^{221} = 10^{18 \times 12 + 5 } \equiv (10^{12})^{18} \times 10^5 \equiv 10^ 5 \equiv 4 \pmod{13} . $$
A: To make our lives much simpler, we should apply Fermat's little theorem first. We know that
$$10^{12}\equiv 1\bmod 13,$$
so that because
$$10^{221}=10^{(12\cdot 18)+5}=\underbrace{10^{12}\times \cdots \times 10^{12}}_{18\text{ times}}\times 10^5,$$
we have that
$$10^{221}\equiv \underbrace{1\times \cdots \times 1}_{18\text{ times}}\times 10^5=10^5\bmod 13.$$
Now you it's much easier to apply repeated squaring the rest of the way:
$$10\equiv 10\bmod 13,\qquad 10^2=100\equiv 9\bmod 13,\qquad 10^4=100^2\equiv 9^2\equiv 3\bmod 13,$$
so that
$$10^{221}\equiv 10^5= 10^4\times 10\equiv 3\times 10=30\equiv 4\bmod 13.$$
A: $$2^6=64\equiv-1\pmod{13}$$
$$\implies 2^{221}=(2^6)^{36}\cdot2^5\equiv(-1)^{36}\cdot6\pmod {13}\equiv6$$
$$5^2=25\equiv-1\pmod{13}$$
$$\implies 5^{221}=(5^2)^{110}\cdot5\equiv(-1)^{110}\cdot5\pmod {13}\equiv5$$
$$\text{So,}10^{221}=5^{221}\cdot2^{221}\equiv6\cdot5\pmod{13}\equiv4$$

Alternatively,  $10\equiv-3\pmod{13}\implies 10^{221}\equiv(-3)^{221}\equiv-3^{221}$
Now, observe that $3^3\equiv1\pmod{13}$ and $221\equiv2\pmod3$
$\displaystyle\implies 3^{221}\equiv3^2\pmod{13}\equiv9$
$\displaystyle\implies 10^{221}\equiv-9\pmod{13}\equiv4$
A: $\rm mod\ 13\!:\ \color{#c00}{10^3}\!\equiv \color{#0a0}{10^2}(10)\equiv \color{#0a0}{-4}(10)\equiv \color{#c00}{-1}\:\Rightarrow\: 10^{221}\!\equiv 10^{3(73)+2}\!\equiv (\color{#c00}{10^3})^{73}\color{#0a0}{10^2}\equiv(\color{#c00}{-1})(\color{#0a0}{-4})\equiv 4$
A: Look up "exponentiation by squaring". There are better methods, but this is mostly fast enough. For practical algorithms, check the GNU Multiple Precision Library, to use it comfortably from C++ see GiNaC
