How to find last two digits of $2^{2016}$

What should the 'efficient' way of finding the last two digits of $2^{2016}$ be? The way I found them was by multiplying the powers of $2$ because $2016=1024+512+256+128+64+32$. I heard that one way would be with the Chinese Remainder Lemma but I don't really know how I should start?

• As an alternative duplicate target also consider this or this. The latter one has list of further essential duplicates as a comment. Observe the extra steps you need to do because the base $2$ shares a factor with $100$. – Jyrki Lahtonen Jun 30 '16 at 11:07
• One answer to your question in lab's answer is that we can use the identity $$\ 4a\bmod 4n\, = 4(a\bmod n)\$$ to pull out common factors using the distributive law. This decreases the modulus so simplifies computations. This might be clearer in my answer. – Bill Dubuque Dec 15 '16 at 3:34

Essentially we need $2^{2016}\pmod{100}$

As $(2^{2016},100)=4$

let us find $2^{2016-2}\pmod{100/4}$

Now as $2^{10}\equiv-1\pmod{25}$

$2^{2014}=2^{201\cdot10+4}=(2^{10})^{201}\cdot2^4\equiv(-1)^{201}\cdot2^4\equiv9\pmod{25}$

$$\implies2^2\cdot2^{2014}\equiv2^2\cdot9\pmod{2^2\cdot25}$$

• Why did you find $2^{2014}$ and not $2^{2016}$? If I tried writing $2^{2016}$ as $2^{201\cdot10+6}$ the final answer would be $2^2\cdot2^{2016}\equiv2^2\cdot11\pmod{2^2\cdot25}$ which is wrong. Can you please explain me why it doesn't work like this, too? – Toma Radu-Petrescu Jun 30 '16 at 9:52
• @TomaRadu-Petrescu, I wanted to find $$2^n\equiv-1\text{or }1\pmod m$$ which is possible only if $(2,m)=1$ – lab bhattacharjee Jun 30 '16 at 10:00

By brute force:

Powers of $2$ end in

$$01,02,\color{blue}{04,08,16,32,64,28,56,12,24,48,96,92,84,68,36,72,44,88,76,52},04,08,16\cdots$$ and so on with a period of $20$.

Hence $$2^{2016}\to2^{16}\to36.$$


This is an $\ds{\ul{old\ school}}$ proof:

1. Since $\ds{2^{2016} = \pars{2^{4}}^{2016/4} = 16^{504}}$, it's obvious the $\ds{\ul{2^{2016}\ last\ digit}}$ is $\ds{\color{#f00}{\large 6}}$.

Namely, the last digit of any $n^{\mathrm{th}}$-powers $\ds{\pars{n = 1,2,3,\ldots}}$ of $\ds{\ 16}$ is $\ds{\color{#f00}{6}}$.
2. Then, $\ds{{2^{2016} - 6 \over 10}= {16^{504} - 6 \over 10}}$ is an $\ds{\ul{integer}}$ and its last digit is the digit before the $\ds{2^{2016}}$ last digit: \begin{align} \fbox{$\ds{\ {16^{504} - 6 \over 10}\ }$} & = {\pars{16^{504} - 16} + 10 \over 10} = {16\pars{16^{503} - 1} \over 10} + 1 = {16\times 15 \over 10}\,{16^{503} - 1 \over 16 - 1} + 1 \\[3mm] & = \fbox{$\ds{\ 24\sum_{n = 0}^{502}16^{n} + 1\ }$}\tag{1} \end{align} The above sum last digit is the last digit of $\ds{\pars{1 + 6\times 502} = 301\ul{3}.\ }$ The last digit of $\ds{2\ul{4} \times 301\ul{3}}$ is $\ds{\ul{2}}$ such that the last digit of $\ds{\pars{1}}$ is $\ds{\pars{\ul{2} + \ul{1} = \color{#f00}{\large 3}}}$
3. Then, $\ds{2^{2016}\ \ul{last\ two\ digits}\ \mbox{is}\ \color{#f00}{\large 36}}$.
• Heh. +1 for steampunk and rabbits. – Joffan Jun 30 '16 at 19:56
• @Joffan Thanks for your remark. Sometimes it's nice to use 'brute force', 'old school', 'old tricks from the old trunk', etc... I like the other answers ( the 'mod' style is a quite useful tool ) but I feel we need some aditional feeling . – Felix Marin Jun 30 '16 at 23:06

You may combine an obvious fact: $$2^{2016}\equiv 0\pmod{4}$$ with the less obvious fact that $2$ is a generator for $\mathbb{Z}/(25\mathbb{Z})^*$ to get: $$2^{2016} \equiv 2^{2016\pmod{\varphi(25)}} \equiv 2^{16} \equiv (-1)\cdot 64 \equiv 11\pmod{25}$$ from which: $$2^{2016}\equiv\color{red}{36}\pmod{100}$$ readily follows from the Chinese remainder theorem.

• +1. Anyway: A professional mathematician sets the difference. – Felix Marin Jun 30 '16 at 18:40
• ... and some hasty user readily set a downvote :D – Jack D'Aurizio Jan 30 '17 at 22:58
• @JackD'Aurizio sir your proof is mind blowing!! I love group theory and I can't help but ask the last three digit of $2^{2017}$. – MathCosmo Jun 5 '18 at 12:00
• @MathCosmo: there is very little to adapt, since 2 is a generator mod 125, too. – Jack D'Aurizio Jun 5 '18 at 13:37

We need to find $2^{2016} \bmod 100$

We can calculate this fairly directly without the need for the Chinese Remainder Theorem to recombine the results from the different prime powers, although that is often a useful technique.

Although $2^2 \mid 100$, the values for exponents above $2$ will cycle as usual in accordance with Euler's Theorem, and the cycle length will divide $\lambda(100)=\text{lcm}(20,2)=20$, the reduced totient function (Carmichael function).

So since $2016 \equiv 16 \bmod 20$ (and $16>2$), $2^{2016} \equiv 2^{16} \equiv (2^8)^2 \equiv 56^2 \equiv 6^2 \equiv 36 \bmod 100$

We use $$\ ca\bmod cn\,=\ c\ (a\bmod n),\,$$ the mod Distributive Law,  to pull out $$\,c=2^{\large 2}$$ \ \ \begin{align} 2^{\large 16+20I^{\phantom{|}}}\!\!\!\bmod 100\, &=\ 2^{\large 2}\,(\color{#c00}{2^{\large 14+20I}}\bmod{25})\\ &=\, 2^{\large 2}\,(\color{#c00}{3^{\large 2}}), \ {\rm by}\ \bmod{25}\!:\,\ {\color{#c00}{2^{\large 14+20I}}}\!\equiv 2^{\large 14}\, \!\!\!\underbrace{(\color{#0a0}{2^{\large 20}})^{\large I}\! \equiv \color{#0a0}{\bf 1}^{\large I}}_{\rm\large\color{#0a0}{Euler}\ \phi(25)=20}\!\!\!\,2^{\large 14}\!\equiv (2^{\large 7})^{\large 2}\!\equiv\color{#c00}{ 3^{\large 2}} \end{align}