# 2^(2^(32)) mod 11

For 1420172017 mod 60 I used a logarithm rule to solve it: 1420172017 mod 60 => lg(14) a = 20172017 In essence, I calculated 20172017 mod 60 = 37 (using Euler's Theorem). Then I used that result as a power of 14: 1437 mod 60 = 44.

I figured that the same principle would also apply to 2232.

So, first I tried to get the result of 232 mod 11. Since the point of this is not to use a calculator, I simplified the term using exponentation laws: 232 = 22 mod 11 * 230 11 = 4 * 1 = 4.

I checked the result and 232 mod 11 really is 4.

The problem appears during the next step: 24 mod 11 = 5. But 2232 mod 11 = 9. Therefore, my result is wrong.

Note that $$2^{10}\equiv 1\pmod{11}$$ (Fermat), hence if $$2^{32}\equiv n\pmod{10}$$, then $$2^{2^{32}}\equiv 2^n\pmod{11}$$.

So what is $$2^{32}\bmod{10}$$? Start by computing $$2^{32}\bmod 5$$. As $$2^4\equiv 1\pmod 5$$, clearly $$2^{32}=(2^4)^8\equiv1\pmod 5$$ as well. Of course $$2^{32}$$ is even, so (ultimately by the Chinese Remainder Theorem) $$2^{32}\equiv6\pmod{10}$$.

Thus we need only compute $$2^6\equiv 64\equiv 9\pmod{11}$$.

$$\!\bmod 11\!:\,\ \underbrace{2^{\large 2^{\Large 32}}\!\!\equiv 2^{\large\color{#c00} 6}}_{\Large 2^{\Large\color{#0a0}{10}}\ \equiv\ 1}\,\$$ by $$\ \overbrace{2^{\large 32}\!\bmod\color{#0a0}{10} = 2\underbrace{(2^{\large 31}\!\bmod 5)}_{\large 2^{\Large 4}\ \equiv\ 1}}^{\large ab\,\bmod\, ac\ \ =\ \ a(b\bmod c)\ \ \ }= 2(2^{\large 3}\!\bmod 5) = \color{#c00}6$$

• Underbraced are by little Fermat, and overbrace is the mod Distributive Law. – Bill Dubuque Apr 30 at 15:14
• And $2^6\cong9\pmod{11}$. – Chris Custer Apr 30 at 15:15
• @Chris The point is to highlight the nontrivial aspects of the problem (so I purposely remove trivial parts that may obfuscate that). – Bill Dubuque Apr 30 at 15:17

The multiplicative order of $$2$$ mod $$11$$ is $$10$$, not $$11$$. So you want to compute $$2^{32} \bmod 10$$.

$$2^5\equiv-1\pmod{11}$$

Now $$2^{31}=2\cdot4^{15}=2(5-1)^{15}\equiv\equiv2(-1)\equiv3\pmod5,$$

$$2^{31}=5a+3$$(say for some integer $$a>0$$)

$$2^{2^{32}}=(2^{2^{31}})^2=(2^{5a+3})^2=(2^5)^{2a}\cdot2^6\equiv(-1)^{2a}\cdot2^4\equiv2^6\pmod{11}\equiv?$$