Duke Math Meet 2009 Problem 9 solution | Team Round

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.

Some Useful Links:

• Duke Math Meet 2008 Problem 8
• Our Math Olympiad Program
• AM-GM Inequality - Video