AoPSWiki

Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.

Personal tools

Search

Toolbox

Mock AIME 4 2006-2007 Problems/Problem 7

From AoPSWiki

Problem

Find the remainder when $3^{3^{3^3}}$ is divided by 1000.

Solution

$\phi (1000)=400$ , so $3^{400}=1\bmod 1000$ .

Therefore, we want $3^{27} \bmod 400$ .

Since $400=2^4*5^2$ , we want $3^{27}\bmod 16$ and $3^{27} \bmod 25$ .

$3^{4} \equiv 1\bmod 16$ , so $3^{27}\equiv 11\bmod 16$ .

Since $3^{\phi(25)}=3^{20}\equiv 1\bmod 20$ , $3^{27}\equiv 3^7\equiv 18\bmod 25$ .

The only number $\bmod 400$ that is $11\bmod 16$ and $18\bmod 25$ is $43\bmod 400$ . Therefore,

$3^{3^{3^3}}\equiv 3^{43} \bmod 1000$ .

Since $1000=8*125$ , we want to find $3^{43}\bmod 8$ and $3^{43}\bmod 125$ .

Since $3^4\equiv 1\bmod 8$ , $3^{43}\equiv 27\equiv 3\bmod 8$ .

And since $3^5\equiv -7\bmod 125$ , $3^{10}\equiv 49\bmod 125$ , $3^{20}\equiv 26\bmod 125$ , $3^{40}\equiv 1\bmod 125$ .

We have gotten somewhere.

$3^{43}\equiv 27\bmod 125$

The only number $\bmod 1000$ that satisfies $3\bmod 8$ and $27\bmod 125$ is $\boxed{027}\bmod 1000$ .

See also

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Mock_AIME_4_2006-2007_Problems/Problem_7"

Category: Intermediate Number Theory Problems

Try our innovative online adaptive learning system, Alcumus.
Over 1100 problems and 60+ video lessons. FREE!

© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us