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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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