AoPSWiki

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

Personal tools

Log in

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

Using the Carmichael function, we have $\lambda(1000)=100$ , so $3^{100}=1\pmod{1000}$ . Therefore, letting $N=3^{3^3}$ , we seek to find an $n$ such that $N\equiv n\pmod{100}$ so that $3^N\equiv 3^n\pmod{1000}$ .

Using the Carmichael function again, we have $\lambda(100)=20$ , so $N=3^{27}\equiv 3^7\pmod{100}\equiv 87\pmod{100}$ . Therefore $n=87$ , and so we have the following: $3^{3^{3^3}}\equiv 3^{87}\pmod{1000}.$

Now,

$\begin{align*}3^{87}=(3^{20})^4\cdot 3^7&\equiv 401^4\cdot 187\pmod{1000} \\&\equiv 601\cdot 187\pmod{1000} \\&\e...$

See also

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

Category: Intermediate Number Theory Problems

Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.

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