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

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

• – lab bhattacharjee Jul 31 '16 at 7:52
• @labbhattacharjee i need to know why and how of method and not the mechanical procedure – Gathdi Jul 31 '16 at 7:53
• 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. – Jyrki Lahtonen Jul 31 '16 at 7:57
• @JyrkiLahtonen, +1 – Andreas Caranti Jul 31 '16 at 11:17
• @JyrkiLahtonen What do you mean by period? – Gathdi Jul 31 '16 at 14:58

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.

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

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

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

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

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

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

• 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). – Bill Dubuque Jul 31 '16 at 14:54