Remainder Problem – Duke Math Meet 2009 Team Round Problem 9 solution

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 \implies 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 \implies 5^{4Q} \equiv 1 mod 12 \) )

Thus \(5^{5^5} = 12Q’ + 5 \implies 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.

Leave a Reply

Your email address will not be published. Required fields are marked *