3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You can look at the answers (including mine) here and also [here](v) $\endgroup$ – Amzoti Apr 26 '13 at 3:47
  • 4
    $\begingroup$ 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}$... $\endgroup$ – Jyrki Lahtonen Apr 26 '13 at 3:47
5
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.