5
$\begingroup$

To find last two digits of $2^{100}$

I have just learned about modular arithmetic and I wanted to solve this problem. I only know about equivalence classes and about $a=b \pmod n$. I have also learned about multiplication and addition of classes. Can someone explain to me step by step on how to apply modular arithmetic to this problem?

Thanks

$\endgroup$
  • 1
    $\begingroup$ See math.stackexchange.com/questions/607829/… $\endgroup$ – lab bhattacharjee Jul 31 '16 at 7:52
  • $\begingroup$ @labbhattacharjee i need to know why and how of method and not the mechanical procedure $\endgroup$ – Gathdi Jul 31 '16 at 7:53
  • 2
    $\begingroup$ Gathdi, just try it out. Experiment what happens with exponents smaller than $100$. You will find a period. It is not very short, but not excessively long either. After you see what happens, you can then take a look at it, and see what modular arithmetic is necessary to justify the result. $\endgroup$ – Jyrki Lahtonen Jul 31 '16 at 7:57
  • $\begingroup$ @JyrkiLahtonen, +1 $\endgroup$ – Andreas Caranti Jul 31 '16 at 11:17
  • $\begingroup$ @JyrkiLahtonen What do you mean by period? $\endgroup$ – Gathdi Jul 31 '16 at 14:58
11
$\begingroup$

Method 1(using fast power algorithm):

$2^0 \equiv 1 \pmod {100}$

$2^1 \equiv 2 \pmod {100}$

$2^2 \equiv 4 \pmod {100}$

$2^4 \equiv 16 \pmod {100}$

$2^8 \equiv 56 \pmod {100}$

$2^{16} \equiv 36 \pmod {100}$

$2^{32} \equiv 96 \pmod {100}$

$2^{64} \equiv 16 \pmod {100}$

Since $100 = 4 + 32 + 64$

$2^{100} \equiv 2^{4} 2^{32} 2^{64}\equiv 16 \times 96 \times 16 \equiv 76 \pmod {100}$

Method 2(using minimal cycle to improve):

Since $2^{22} \equiv 4 \pmod {100}$, $2^{100} \equiv 2^{22 \times 4 + 12} \equiv 4^4 \times 2^{12} \equiv 2^{20} \equiv 16 \times 96 \equiv 76 \pmod{100} $

Last but not least: Since $2^{20} \equiv 76 \pmod {100}$, $76 \times 76 \equiv 76 \pmod{100}$, $2^{100} = 2^{20 \times 5} \equiv 76^5 \equiv 76 \pmod{100} $ by induction.

$\endgroup$
7
$\begingroup$

$$2^{100} \equiv 4^{50} \equiv 0 \pmod {4}$$ $$2^{100} \equiv 1024^{10} \equiv (-1)^{10} \equiv 1 \pmod {25}$$

So what number less than $100$ is $0 \pmod 4$ and $1 \pmod {25}$ ?

$\endgroup$
5
$\begingroup$

$2^{100}\bmod{100}=$

$2^{10\cdot10}\bmod{100}=$

$(2^{10})^{10}\bmod{100}=$

$1024^{10}\bmod{100}=$

$24^{10}\bmod{100}=$

$24^{3\cdot3+1}\bmod{100}=$

$(24^{3})^{3}\cdot24\bmod{100}=$

$13824^{3}\cdot24\bmod{100}=$

$24^{3}\cdot24\bmod{100}=$

$13824\cdot24\bmod{100}=$

$24\cdot24\bmod{100}=$

$576\bmod{100}=$

$76\pmod{100}$

$\endgroup$
  • $\begingroup$ $2^{3 \cdot 3 + 1}$ should probably be $24^\cdots$ $\endgroup$ – mathreadler Jul 31 '16 at 11:20
  • 1
    $\begingroup$ @mathreadler: Thank you, added the missing digit :) $\endgroup$ – barak manos Jul 31 '16 at 13:11
1
$\begingroup$

Use the Chinese remainder theorem: $$\mathbf Z/100\mathbf Z\simeq \mathbf Z/4\mathbf Z\times\mathbf Z/25\mathbf Z.$$

Now $2^{100}\equiv 0\mod 4$, and $\;2^{100}=(2^{20})^5\equiv 1^5=1\mod 25\;$ by Euler's theorem.

So we have to solve the system of linear congruences: $\;\begin{cases} x\equiv 0\mod4,\\x\equiv 1\mod 25.\end{cases}$

From the Bézout's relation $\;25-6\cdot 4=1$, we deduce the solutions: $$x\equiv 0\cdot 24-1\cdot 6\cdot 4=-24\equiv 76\mod 100.$$

$\endgroup$
0
$\begingroup$

$2^{10}=1024$

$2^{100}=1024^{10}$

$2^{11} \equiv48$

$ 2^{12}\equiv96\equiv-2^2$

$ 2^{100}\equiv2^{12*8+2^4}\equiv-{2^2}^8*2^4$

$ =-2^{20}=-2^2*256=-24\equiv76 \pmod {100}$

another method

By euler's function, $2^{\phi(25)}=2^{20}\equiv1 \pmod{25}$

$2^{100}\equiv1,26,51,76 \pmod{100}$

$2^{100}$ is multiple of 4, so $76$.

$\endgroup$
0
$\begingroup$

${\rm mod}\ 25\!:\ \ \ \ \color{#0a0}{2^{\large 10}} = 1024\equiv \color{#0a0}{\bf -1}\,\Rightarrow$ $\,\color{#c00}{2^{\large 90}}\equiv (\color{#0a0}{2^{\large 10}})^{\large 9}\equiv (\color{#0a0}{\bf -1})^{\large 9}\equiv \color{#c00}{\bf -1}$

${\rm mod}\ 100\!:\,\ 2^{\large 100} = 2^{\large 10} \color{#c00}{2^{\large 90}} = 2^{\large 10}(\color{#c00}{\bf -1}+25n) \equiv \color{#c00}{\bf -}2^{10}\!+0\equiv -1024\equiv -24 $

$\endgroup$
  • $\begingroup$ All mental arithmetic, no use of Euler/Fermat or CRT etc (but of course you should learn those methods because they will be essential for more general problems). $\endgroup$ – Bill Dubuque Jul 31 '16 at 14:54

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.