1

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 this:

  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?

J. W. Tanner
  • 60,406
riemann_lebesgue
  • 626
  • 2
    Can $5^{3125}$ be considered more satisfying? Did in my head and not a big number in my opinion. – cr001 Aug 25 '20 at 11:38
  • What is unsatisfying with this (quick) solution ? But in fact, if the exponent is still small, you can apply Fermat's little theorem directly. Since the reduction modulo $22$ gives $1$, the result is immediate in this case. – Peter Aug 25 '20 at 11:39
  • @Peter I didn't find it especially beautiful, that's all – riemann_lebesgue Aug 25 '20 at 13:32

3 Answers3

4

More elegant, I don't know, but here's how I do this computation:

By lil' Fermat, since $23$ is prime, $5^n\equiv 5^{n\bmod \varphi(23)}=5^{n\bmod22}\mod 23$.

Now $5^5\bmod 22$ is easily computed by hand: $$5^2\equiv 3\implies 5^4\equiv 9\implies 5^5\equiv 9\cdot 5\equiv 1\mod 22.$$ Therefore $\;5^{5^5}\equiv 5^1=5\mod 23$.

Bernard
  • 175,478
  • Or just divide $5^5=3125$ by $22$ using long division ;) –  Aug 25 '20 at 11:46
  • 1
    @StinkingBishop: I'll ask Santa Claus to do that! – Bernard Aug 25 '20 at 11:48
  • When I went to primary school, it wasn't that we were not allowed to use pocket calculators - it was that pocket calculators didn't exist yet (at least not widely available, and you needed a big pocket anyways!). So yep, we had to do long division out of necessity. As a byproduct, we always got the remainder of the division. Not sure what those new generations do, I think they mostly treat long division as a "tick in the box". –  Aug 25 '20 at 11:55
  • Very probably. Did you also learn to compute square roots by hand? I learnt that in the first year of middle school (there was no proof to explain why.it worked, though). – Bernard Aug 25 '20 at 12:03
  • I don't remember whether we did it for square roots... I doubt it, maybe it was shown to some talented kids as part of the maths' club, but I don't really remember and I'd learnt it elsewhere. –  Aug 25 '20 at 12:07
3

Since $22|5^5-1$, by FLT $23|5^{5^5}-5^1$.

J.G.
  • 115,835
2

No need to do much calculation.

$5^5\equiv1\bmod22,$ because $5^5\equiv1\bmod2$ and $5^5\equiv1\bmod11$,

because $5\equiv4^2 $ is a quadratic residue $\bmod 11$.

Therefore, $5^{5^5}\equiv5\bmod23$.

J. W. Tanner
  • 60,406