Find the last two digit of $3^{3^{100}}$.

Question

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?

Answer 1

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}$.

Answer 2

you are right with Euler's theorem. $100=2^{2}5^{2}$ and $\phi{(100)}=40=(2^{2}-1)=(5^{2}-5)$, so by Euler's theorem you have : $3^{40k+1}\equiv3\pmod{100}$ then, you have $3^{100}\equiv1\pmod{40}$ this finally gives you : $3^{3^{100}}\equiv3\pmod{100}$ and so, the last two digits of your number are 3 and 0.

Answer 3

Any base to a power has a pattern. So if I consider powers of 3, $3,9,27,81,243$ you notice that the end digits follow the pattern $3,9,7,1$. You can generalize that any power mod 4 (the number of elements in the pattern) will "end" in the corresponding element in this pattern.

for two digits of the answer, you must take $3^{3^{100}} (mod 100)$, which follows a similar strategy, but the pattern (the last 2 digits of the power) will be a little bit longer.

Answer 4

$3^{100}=1+40 k$ for some $k\in Z$, therefore the result is $3^{3^{100}}=...03$.

(It is easy to check: $3^{100}=1 \mod 5$ and $3^{100}=1 \mod 8$, from where we get $3^{100}=1 \mod 40$).