Categories

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 $5^5 = 3125 \equiv 5 mod 13$ . Thus answer is 5.