Difference between revisions of "Euler's Totient Theorem Problem 2 Solution"
Megaboy6679 (talk | contribs) |
(→Solution) |
||
(One intermediate revision by the same user not shown) | |||
Line 3: | Line 3: | ||
==Solution== | ==Solution== | ||
− | 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>. | + | 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 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>. | + | 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 | ~BorealBear | ||
Link back to [[Euler's Totient Theorem]]. | Link back to [[Euler's Totient Theorem]]. |
Latest revision as of 21:14, 15 August 2023
Problem
(BorealBear) Find the last two digits of .
Solution
Finding the last two digits is equivalent to finding . We can start by expanding the uppermost exponent: . Then, since , the exponent is equal to . We see that , so it simplifies to .
We now just need to find the last two digits of . Using the Chinese Remainder Theorem, we find that the last two digits are and . We guess and check to get . ~BorealBear
Link back to Euler's Totient Theorem.