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"
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
<math>\phi (1000)=400</math>, so <math>3^{400}=1\bmod 1000</math>.
+
Using the [[Carmichael function]], we have <math>\lambda(1000)=100</math>, so <math>3^{100}=1\pmod{1000}</math>. Therefore, letting <math>N=3^{3^3}</math>, we seek to find an <math>n</math> such that <math>N\equiv n\pmod{100}</math> so that <math>3^N\equiv 3^n\pmod{1000}</math>.
  
−
Therefore, we want <math>3^{27} \bmod 400</math>.
+
Using the Carmichael function again, we have <math>\lambda(100)=20</math>, so <math>N=3^{27}\equiv 3^7\pmod{100}\equiv 87\pmod{100}</math>. Therefore <math>n=87</math>, and so we have the following:
−
 
+
<cmath>
−
Since <math>400=2^4*5^2</math>, we want <math>3^{27}\bmod 16</math> and <math>3^{27} \bmod 25</math>.
+
3^{3^{3^3}}\equiv 3^{87}\pmod{1000}.
−
 
+
</cmath>
−
<math>3^{4} \equiv 1\bmod 16</math>, so <math>3^{27}\equiv 11\bmod 16</math>.
 
−
 
 
−
Since <math>3^{\phi(25)}=3^{20}\equiv 1\bmod 20</math>, <math>3^{27}\equiv 3^7\equiv 18\bmod 25</math>.
 
−
 
 
−
The only number <math>\bmod 400</math> that is <math>11\bmod 16</math> and <math>18\bmod 25</math> is <math>43\bmod 400</math>. Therefore,
 
−
 
 
−
<math>3^{3^{3^3}}\equiv 3^{43} \bmod 1000</math>.
 
−
 
 
−
Since <math>1000=8*125</math>, we want to find <math>3^{43}\bmod 8</math> and <math>3^{43}\bmod 125</math>.
 
−
 
 
−
Since <math>3^4\equiv 1\bmod 8</math>, <math>3^{43}\equiv 27\equiv 3\bmod 8</math>.
 
−
 
 
−
And since <math>3^5\equiv -7\bmod 125</math>, <math>3^{10}\equiv 49\bmod 125</math>, <math>3^{20}\equiv 26\bmod 125</math>, <math>3^{40}\equiv 1\bmod 125</math>.
 
−
 
 
−
We have gotten somewhere.
 
−
 
 
−
<math>3^{43}\equiv 27\bmod 125</math>
 
−
 
 
−
The only number <math>\bmod 1000</math> that satisfies <math>3\bmod 8</math> and <math>27\bmod 125</math> is <math>\boxed{027}\bmod 1000</math>.
 
  
 +
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>.
 
== See also==
 
== See also==
  

Revision as of 23:15, 4 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, $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}$.

See also

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