# Calculate $2^{2^{2^{\cdot^{\cdot^{2}}}}} \mod 2016$

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

• Do you have Euler's theorem available? May 12, 2019 at 18:07
• Yes, I had that on last lecture May 12, 2019 at 18:07
• math.stackexchange.com/questions/607829/… May 12, 2019 at 18:24

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.

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

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

• We used $\ ab\bmod ac = a(b\bmod c) =$ mod Distributive Law $\ \ \$ May 12, 2019 at 19:12
• could you, please, explain me why you wrote over $2^{2^{2K}}$ a $2^4$ number? May 12, 2019 at 19:35
• @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}\ \$ May 12, 2019 at 19:39
• @jonnyWoox Alternatively $\large \bmod \color{#0a0}6\!:\,\ 4^{\large 2}\equiv 4\,\Rightarrow\, \color{#c00}{4^{\large K}\!\equiv 4}\$ by induction. $\ \$ May 12, 2019 at 20:05
• I think that I've understood all, it is very interesting observation @Bill - thanks a lot! May 12, 2019 at 20:20