INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More 

October 11, 2014

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.

Some Useful Links:

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com