6
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Jyrki Lahtonen Jun 30 '16 at 11:07
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque Dec 15 '16 at 3:34
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Toma Radu-Petrescu Jun 30 '16 at 9:52
  • $\begingroup$ @TomaRadu-Petrescu, I wanted to find $$2^n\equiv-1\text{or }1\pmod m$$ which is possible only if $(2,m)=1$ $\endgroup$ – lab bhattacharjee Jun 30 '16 at 10:00
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

  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}}$.
$\endgroup$
  • $\begingroup$ Heh. +1 for steampunk and rabbits. $\endgroup$ – Joffan Jun 30 '16 at 19:56
  • $\begingroup$ @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 . $\endgroup$ – Felix Marin Jun 30 '16 at 23:06
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1. Anyway: A professional mathematician sets the difference. $\endgroup$ – Felix Marin Jun 30 '16 at 18:40
  • $\begingroup$ ... and some hasty user readily set a downvote :D $\endgroup$ – Jack D'Aurizio Jan 30 '17 at 22:58
  • $\begingroup$ @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}$. $\endgroup$ – MathCosmo Jun 5 '18 at 12:00
  • 1
    $\begingroup$ @MathCosmo: there is very little to adapt, since 2 is a generator mod 125, too. $\endgroup$ – Jack D'Aurizio Jun 5 '18 at 13:37
1
$\begingroup$

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 $

$\endgroup$
1
$\begingroup$

We use $ \ ca\bmod cn\,=\ c\ (a\bmod n),\, $ the mod Distributive Law, $ $ to compute

$\ \ \begin{align} 2^{\large 16+20I}\!\bmod 100\, &=\ 2^{\large 2}\,(\color{#c00}{2^{\large 14+20I}}\bmod{25})\\ &=\, 2^{\large 2}\! \cdot \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}$

$\endgroup$

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.