What is the remainder when 5^{5^{5^5}} is divided by 13 ?

By Fermat’s Little Theorem

5^{12} = 1 \mod 13

Now if we can find out 5^{5^5} \mod 12 we can find the answer.

By Euler’s theorem 5^{\phi (12) } = 5^4 = 1 mod 12

Finally if we can find 5^5 mod 4 we are done.

Since 5 \equiv 1 mod 4 \Rightarrow 5^5 \equiv 1 mod 4 \implies 5^5 = 4Q + 1

Thus 5^{5^5} = 5^{4Q +1} = 5^{4Q} \times 5 \equiv 1 \times 5 mod 12 (as we have previously computed 5^4 \equiv 1 mod 12 \Rightarrow 5^{4Q} \equiv 1 mod 12 )

Thus 5^{5^5} = 12Q' + 5 \Rightarrow 5^{5^{5^5}} = 5^{12Q' + 5 } = 5^{12Q'} \times 5^5 \equiv 5^5 mod 13 . (since we have previously computed 5^{12} \equiv 1 \mod 13 \implies 5^{12Q'} \equiv 1 mod 13 )

Thus 5^{5^{5^5}} \equiv 5^5 mod 13 . But 5^5 = 3125 \equiv 5 mod 13 . Thus answer is 5.