Find the last two digit of $3^{3^{100}}$.
I know how to calculate if I have $3^{100}$. That I will use euler's theorem. which gives me $3^{40}\equiv 1 \pmod{100}$. And so on… but if I have $3^{3^{100}}$ what should I do?
I Tried:
Infact, i need $3^{3^{100}}\equiv x\pmod{ 100}$
For this, I need $3^{100}\equiv y\pmod{\phi{(100)}}$
So i got $y=1$ by using eulers thorem for the abouve cogruence.
That is $(3,40)=1\implies 3^{16}\equiv 1\pmod{40}$
So, i got $(3^{16})^63^4\equiv 1\pmod{40}$
Using this in first congruence i got $3^1\equiv 3\pmod{100}$.
So, the answer is $03$. Is it correct?
I did't use chinese remainder theorem and all. Is there any mistake in my arguments?
Best Answer
If we can find $3^{3^{100}}$ in mods 4 and 25 we're done by the Chinese Remainder Theorem.
Mod 4: Note that $3\equiv -1\pmod 4$, hence $3^{3^{100}}\equiv (-1)^{3^{100}}\equiv (-1)^{2k+1}\equiv -1\equiv 3\pmod 4$.
Mod 25: Since $\varphi(25)=20$ we have $3^{3^{100}}\equiv 3^{3^{100}\pmod {20}}\pmod {25}$. Similarly, $3^{100}\equiv 3^{100\pmod 8}\pmod {20}$, and $100\equiv 4\pmod 8$. Hence, working backwards we get:
$3^{100}\equiv 3^{100\pmod 8}\equiv 3^4\equiv 1\pmod {20}$,
$3^{3^{100}}\equiv 3^{3^{100}\pmod {20}}\equiv 3^1\equiv 3\pmod {25}$.
Thus, threading the congruences together we have:
$3^{3^{100}}=4a+3=25b+3$, or $4a=25b$. So since $\gcd(4,25)=1$ we need $a=25k$. Therefore $3^{3^{100}}=4(25k)+3=100k+3$, so the answer is $\boxed{03}$.