Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Mock AIME 4 2006-2007 Problems/Problem 7

Revision as of 13:17, 13 February 2008 by 1=2 (talk | contribs) (Please check for rigor, improve if necessary,)

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 "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_7&oldid=23223"