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 "Euler's Totient Theorem Problem 2 Solution"

(Created page with "==Problem== (BorealBear) Find the last two digits of <math> 3^{3^{3^{3}}} </math>. ==Solution== This problem is just asking for <math> 3^{3^{3^{3}}}\pmod{100} </math>. We ca...")
 
m
Line 5: Line 5:
 
This problem is just asking for <math> 3^{3^{3^{3}}}\pmod{100} </math>. We can start by expanding the uppermost exponent, which gives us <math> 3^{3^{27}} </math>. Then, since <math> \phi(100)=40 </math>, the exponent will be equal to <math> 3^{27}\pmod{40} </math>. We can see that <math> 3^4\equiv 81\equiv 1\pmod{40} </math>, so the expression simplifies to <math> 3^3\equiv 27\pmod{40} </math>.  
 
This problem is just asking for <math> 3^{3^{3^{3}}}\pmod{100} </math>. We can start by expanding the uppermost exponent, which gives us <math> 3^{3^{27}} </math>. Then, since <math> \phi(100)=40 </math>, the exponent will be equal to <math> 3^{27}\pmod{40} </math>. We can see that <math> 3^4\equiv 81\equiv 1\pmod{40} </math>, so the expression simplifies to <math> 3^3\equiv 27\pmod{40} </math>.  
  
−
We're now left with finding the last two digits of <math> 3^{27} </math>. To do this, we use [[Chinese Remainder Theorem]]. We find that it is <math> 3 </math> mod <math> 4 </math> and <math> 12 </math> mod <math> 25. </math> From here, we use guess+check to get <math> \boxed{87} </math>.
+
We're now left with finding the last two digits of <math> 3^{27} </math>. To do this, we use [[Chinese Remainder Theorem]]. We find that it is <math> 3 </math> mod <math> 4 </math> and <math> 12 </math> mod <math> 25. </math> From here, we use guess+check to get <math> \boxed{87} </math>. -BorealBear

Revision as of 20:17, 23 April 2021

Problem

(BorealBear) Find the last two digits of $3^{3^{3^{3}}}$.

Solution

This problem is just asking for $3^{3^{3^{3}}}\pmod{100}$. We can start by expanding the uppermost exponent, which gives us $3^{3^{27}}$. Then, since $\phi(100)=40$, the exponent will be equal to $3^{27}\pmod{40}$. We can see that $3^4\equiv 81\equiv 1\pmod{40}$, so the expression simplifies to $3^3\equiv 27\pmod{40}$.

We're now left with finding the last two digits of $3^{27}$. To do this, we use Chinese Remainder Theorem. We find that it is $3$ mod $4$ and $12$ mod $25.$ From here, we use guess+check to get $\boxed{87}$. -BorealBear

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euler%27s_Totient_Theorem_Problem_2_Solution&oldid=152528"