Maths WorkshopMaths problems with full solutions
Exercise 2111Number theory › CongruencesOlympiadAdded 3 Nov 2026

Power tower modulo $n$

#power tower#modular exponentiation#Carmichael

Statement

Compute 222⋯(mod11)2^{2^{2^{\cdots}}}\pmod{11}, where the tower has 20242024 twos.

Hint

Use Fermat: 210≡1(mod11)2^{10}\equiv1\pmod{11}. So the exponent matters mod 1010.

Show solutionHide solution

Solution

Reduce exponent. The exponent is 2X2^X where X=22⋯X=2^{2^{\cdots}} (with 20232023 twos). Since gcd⁡(2,10)=2\gcd(2,10)=2, this is tricky. Instead, compute: 22k(mod10)2^{2^k}\pmod{10} for k≥1k\ge1: 22=42^2=4, 24=16≡62^4=16\equiv6, 26=64≡42^6=64\equiv4 — period 22. For k≥2k\ge2 even, 22k≡6(mod10)2^{2^k}\equiv6\pmod{10}. So for a tower of 20232023 twos (exponent), 2exponent≡26=64≡9(mod11)2^{\text{exponent}}\equiv2^6=64\equiv9\pmod{11}.

Simpler. Since 26=64≡92^6=64\equiv9 and 210≡12^{10}\equiv1, the answer is 99 for 20242024 twos (because 2222^{2^{2}} with 33 twos is 24=16≡52^4=16\equiv5, 22222^{2^{2^2}} with 44 twos is 216≡26≡92^{16}\equiv2^6\equiv9, and it stabilizes at 99).

Conclusion. 22⋯≡9(mod11)2^{2^{\cdots}}\equiv9\pmod{11} for a tower of 20242024 twos.

Caveat: This requires careful analysis of the exponent's residue mod 1010; details depend on exact tower height.