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

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?

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

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.

• thank you this is what i want.@Aurelian Oct 2, 2014 at 12:05

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.

• i have already quoted that i know this.. but how is the question.@Stretch Maniac Oct 2, 2014 at 11:44

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