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...")
 
(→‎Solution)
 
(4 intermediate revisions by 3 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
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>.  
+
Finding the last two digits is equivalent to finding <math>3^{3^{3^{3}}}\pmod{100}</math>. We can start by expanding the uppermost exponent: <math>3^{3^{27}}</math>. Then, since <math>\phi(100)=40</math>, the exponent is equal to <math> 3^{27}\pmod{40} </math>. We see that <math> 3^4=81\equiv1\pmod{40} </math>, so it simplifies to <math>3^3={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 now just need to find the last two digits of <math>3^{27}</math>. Using the [[Chinese Remainder Theorem]], we find that the last two digits are <math>3\pmod{4}</math> and <math>12\pmod{25}</math>. We guess and check to get <math>\boxed{87}</math>.
 +
~BorealBear
 +
 
 +
Link back to [[Euler's Totient Theorem]].

Latest revision as of 21:14, 15 August 2023

Problem

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

Solution

Finding the last two digits is equivalent to finding $3^{3^{3^{3}}}\pmod{100}$. We can start by expanding the uppermost exponent: $3^{3^{27}}$. Then, since $\phi(100)=40$, the exponent is equal to $3^{27}\pmod{40}$. We see that $3^4=81\equiv1\pmod{40}$, so it simplifies to $3^3={27}\pmod{40}$.

We now just need to find the last two digits of $3^{27}$. Using the Chinese Remainder Theorem, we find that the last two digits are $3\pmod{4}$ and $12\pmod{25}$. We guess and check to get $\boxed{87}$. ~BorealBear

Link back to Euler's Totient Theorem.

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