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?
 A: 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.$$
A: 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}$$
A: $\newcommand{\angles}[1]{\left\langle\,{#1}\,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\iff}{\Leftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\Li}[2]{\,\mathrm{Li}_{#1}\left(\,{#2}\,\right)}
 \newcommand{\ol}[1]{\overline{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

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



*

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

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


*Then,
$\ds{2^{2016}\ \ul{last\ two\ digits}\ \mbox{is}\
\color{#f00}{\large 36}}$.

A: 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.
A: 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 $
A: 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}$
A: You can write
$$ 2^{2016} = 2^{32}  {(2^{32})}^2  {(2^{32})}^4  {(2^{32})}^8  {(2^{32})}^{16} {(2^{32})}^{32} $$
and
$$ 2^{32} = {({({(2^{4})}^{2})}^{2})}^{2}  $$
Calculating squares in $\text{ mod 100}$:
$\quad 16 \mapsto 56 \mapsto 36 \mapsto 96$
and so $2^{32} \equiv 96 \text{ mod 100}$ and since $96^{2} \equiv 16 \text{ mod 100}$ there is a cyclic pattern on these squares; using mental calculations and our cycle,
$\quad 2^{2016} \equiv (-4) (16) (56) (36)(-4)(16) \equiv$
$\quad\quad\quad\quad (16)(16)(56)(36)(16) \equiv$
$\quad\quad\quad\quad (56)(56)(36)(16) \equiv$
$\quad\quad\quad\quad (36)(36)(16) \equiv$
$\quad\quad\quad\quad (-4)(16) \equiv$
$\quad\quad\quad\quad 36 \text{ mod 100} $
