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
$\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$
  • $\begingroup$ We used $\ ab\bmod ac = a(b\bmod c) = $ mod Distributive Law $\ \ \ $ $\endgroup$ – Bill Dubuque May 12 at 19:12
  • $\begingroup$ could you, please, explain me why you wrote over $2^{2^{2K}}$ a $2^4$ number? $\endgroup$ – jonnyWoox May 12 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$ – Bill Dubuque May 12 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$ – Bill Dubuque May 12 at 20:05
  • $\begingroup$ I think that I've understood all, it is very interesting observation @Bill - thanks a lot! $\endgroup$ – jonnyWoox May 12 at 20:20
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$
  • $\begingroup$ what can help me with calculate $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 7$ with your advice? $\endgroup$ – jonnyWoox May 12 at 18:56
  • $\begingroup$ $2^m \equiv 1, 2$ or $4 \bmod 7$ depending on $m \bmod 3$. $\endgroup$ – Robert Israel May 12 at 20:32

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.