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"
(Please check for rigor, improve if necessary,)
Line 1: Line 1:
 
==Problem==
 
==Problem==
 
Find the remainder when <math>3^{3^{3^3}}</math> is divided by 1000.
 
Find the remainder when <math>3^{3^{3^3}}</math> is divided by 1000.
 +
 
==Solution==
 
==Solution==
 +
<math>\phi (1000)=400</math>, so <math>3^{400}=1\bmod 1000</math>.
  
−
Euler's Totient Theorem comes in handy here:
+
Therefore, we want <math>3^{27} \bmod 400</math>.
−
 
 
−
<math>3^{400}\equiv 1 \pmod {1000}</math>
 
  
−
So we are looking for <math>3^{27} \pmod {400}</math>
+
Since <math>400=2^4*5^2</math>, we want <math>3^{27}\bmod 16</math> and <math>3^{27} \bmod 25</math>.
  
−
<math>3^{27}=(3^9)^3=(27^3)^3</math>
+
<math>3^{4} \equiv 1\bmod 16</math>, so <math>3^{27}\equiv 11\bmod 16</math>.
  
−
We brute force it:
+
Since <math>3^{\phi(25)}=3^{20}\equiv 1\bmod 20</math>, <math>3^{27}\equiv 3^7\equiv 18\bmod 25</math>.
  
−
<math>27^3=729*27=19683</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>19683 \equiv 83 \pmod {400}</math>
+
<math>3^{3^{3^3}}\equiv 3^{43} \bmod 1000</math>.
  
−
<math>83^2=6889</math>
+
Since <math>1000=8*125</math>, we want to find <math>3^{43}\bmod 8</math> and <math>3^{43}\bmod 125</math>.
  
−
<math>83^3 \equiv 187 \pmod {400}</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>.
  
−
<math>3^{27} \equiv 187 \pmod {400}</math>
+
We have gotten somewhere.
  
−
<math>3^{3^{3^3}} \equiv 3^{187} \pmod {1000}</math>
+
<math>3^{43}\equiv 27\bmod 125</math>
  
−
{{solution}}
+
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>.
  
−
----
+
== See also==
  
 
*[[Mock AIME 4 2006-2007 Problems/Problem 8| Next Problem]]
 
*[[Mock AIME 4 2006-2007 Problems/Problem 8| Next Problem]]
 
*[[Mock AIME 4 2006-2007 Problems/Problem 6| Previous Problem]]
 
*[[Mock AIME 4 2006-2007 Problems/Problem 6| Previous Problem]]
 
*[[Mock AIME 4 2006-2007 Problems]]
 
*[[Mock AIME 4 2006-2007 Problems]]

Revision as of 13:17, 13 February 2008

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"