3
$\begingroup$

How to find $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 2016$ where $2$ occurs $2016$ times?
My current observations:

$$2^{11} = 2048 \equiv 2048=2016 \equiv 2^5 $$ and $$ 2^{16} \equiv 2^{11}\cdot 2^5 \equiv 2^{10} $$ and now we have $2012$ of "2" left...

$\endgroup$
3

2 Answers 2

4
$\begingroup$

Hint: $2016 = 2^5 \cdot 3^2 \cdot 7$. Consider it separately mod $2^5$, mod $3^2$ and mod $7$, and combine using the Chinese Remainder Theorem.

$\endgroup$
2
  • $\begingroup$ what can help me with calculate $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 7$ with your advice? $\endgroup$
    – jonnyWoox
    May 12, 2019 at 18:56
  • $\begingroup$ $2^m \equiv 1, 2$ or $4 \bmod 7$ depending on $m \bmod 3$. $\endgroup$ May 12, 2019 at 20:32
3
$\begingroup$

$ \overbrace{2^{\large 2^{\Large 2K}}\!\!\!\bmod 2^{\large 5}\!\cdot 63}^{\large\ \ \ 2^{\Large 2K}\ge5\ \ {\rm by}\ \ K>1 }\, =\, 2^{\large 5}\!\left[\dfrac{{2^{\large \color{#c00}{2^{\Large 2K}}}}}{2^{\large 5}} \bmod\, 63\right] =\, 2^{\large 5}\overbrace{ \left[\,\dfrac{{2^{\large \color{#c00}{4}}}}{2^{\large 5}} \bmod 63\right]}^{\!\!\!\! \dfrac{2^{\large 5}}{2^{\large 6}_{\phantom{1}}}\ \ {\large \equiv}\ \ \dfrac{2^{\large 5}}{1}} =\, \bbox[5px,border:1px solid #c00]{2^{\large 5}[\,2^{\large 5}\,]}\ \ $ by

$\!\!\bmod 63\!:\ 2^{\large\color{#0a0} 6}\!\equiv 1\,$ so $\!\underbrace{\color{#c00}{2^{\large 2K}}\!\bmod\color{#0a0} 6_{\phantom{1}}}_{\large 2\ \mid\ 2^{\Large 2K}\ {\rm by} \ K>1}\!\!\! = 2\!\!\!\underbrace{\left[\dfrac{2^{\large 2K}}{2}\!\bmod 3\right]}_{ \dfrac{(-1)^{2K}}{-1}\ {\large \equiv}\ \dfrac{1}{-1} {\large}\ {\large \equiv}\ \ \large 2}\!\!\!\!\! =\color{#c00} 4$

$\endgroup$
11
  • $\begingroup$ We used $\ ab\bmod ac = a(b\bmod c) = $ mod Distributive Law $\ \ \ $ $\endgroup$ May 12, 2019 at 19:12
  • $\begingroup$ could you, please, explain me why you wrote over $2^{2^{2K}}$ a $2^4$ number? $\endgroup$
    – jonnyWoox
    May 12, 2019 at 19:35
  • 1
    $\begingroup$ @jonnyWoox The overbraced numerator is $\equiv 2^{\large\color{#c00} 4}\pmod{\!63}$ by the calculation in the line below it, i.e. by reducing its $\,\rm\color{#c00}{expt} \bmod 6,\,$ valid by $\,2^{\large 6}\equiv 64\equiv 1\pmod {\!63}\ \ $ $\endgroup$ May 12, 2019 at 19:39
  • 1
    $\begingroup$ @jonnyWoox Alternatively $\large \bmod \color{#0a0}6\!:\,\ 4^{\large 2}\equiv 4\,\Rightarrow\, \color{#c00}{4^{\large K}\!\equiv 4}\ $ by induction. $\ \ $ $\endgroup$ May 12, 2019 at 20:05
  • $\begingroup$ I think that I've understood all, it is very interesting observation @Bill - thanks a lot! $\endgroup$
    – jonnyWoox
    May 12, 2019 at 20:20

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.