Exercise 2111Number theory › CongruencesOlympiadAdded 3 Nov 2026
Power tower modulo $n$
#power tower#modular exponentiation#Carmichael
Statement
Compute , where the tower has twos.
Hint
Use Fermat: . So the exponent matters mod .
Show solutionHide solution
Solution
Reduce exponent. The exponent is where (with twos). Since , this is tricky. Instead, compute: for : , , — period . For even, . So for a tower of twos (exponent), .
Simpler. Since and , the answer is for twos (because with twos is , with twos is , and it stabilizes at ).
Conclusion. for a tower of twos.
Caveat: This requires careful analysis of the exponent's residue mod ; details depend on exact tower height.