modular arithmetic – More elegant solution to $5^{5^5}$ mod 23


I needed to calculate $5^{5^5}$. This took about 5 minutes or so using the standard trick of building the answer out of smaller answers. My method was to:

  1. calculate $5^{25}=5^{23} 5^2$, which gives 10, using Fermat’s Little Theorem
  2. Calculate $10^{25}$, using the same trick, finding that it equals 11
  3. Calculate $11^5$, by calculating $11^2$ mod 23, using this to get $11^4$, and finally $11^5$ mod 23

This gave 5, which is correct.

However, this method, while fairly quick, was quite unsatisfying. Is there a more elegant solution?