Try this Remainder problem from Duke Math Meet 2009 Problem 9. This problem is from the Team Round of the meet.
Problem: Duke Math Meet 2009 Problem 9
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 $latex 5^5 = 3125 \equiv 5 mod 13 $ . Thus answer is 5.
