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.

• You can look at the answers (including mine) here and also [here](v) – Amzoti Apr 26 '13 at 3:47
• In your case (modulus $13$) Little Fermat tells that $10^{12}\equiv1\pmod{13}$. So therefore also $10^{120}\equiv1^{10}=1$. And also $10^{216}=10^{12\cdot18}\equiv1^{18}$... – Jyrki Lahtonen Apr 26 '13 at 3:47

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$.

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} .$$

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.$$

$\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$

$$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$

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