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

Difference between revisions of "Mock AIME 4 2006-2007 Problems/Problem 7"
(→‎Solution)
 
Line 10: Line 10:
 
</cmath>
 
</cmath>
  
−
Now, <math>3^{87}=(3^{20})^4\cdot 3^7\equiv 401^4\cdot 187\pmod{1000}\equiv 601\cdot 187\pmod{1000}\equiv \boxed{387}\pmod{1000}</math>.
+
Now,
 +
 
 +
<cmath>\begin{align*}3^{87}=(3^{20})^4\cdot 3^7&\equiv 401^4\cdot 187\pmod{1000} \\
 +
&\equiv 601\cdot 187\pmod{1000} \\
 +
&\equiv \boxed{387}\pmod{1000}.
 +
\end{align*}</cmath>
 +
 
 
== See also==
 
== See also==
  

Latest revision as of 00:15, 5 January 2010

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} \\ &\equiv \boxed{387}\pmod{1000}. \end{align*}

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_4_2006-2007_Problems/Problem_7&oldid=33153"