Last Two Digits

As from Euler's Function $\phi(100)=40$

So $3^{\phi(100)} \equiv 1 \pmod {100} \\ \implies 3^{40} \equiv 1 \pmod {100}$

Now we need to find how many $40's$ are there in $3^{100}$ i.e. $3^{100} \equiv ? \pmod {40}$

Now $3^{100} \equiv 1 \pmod{8}$ and $3^{100} \equiv 1 \pmod{5}$ (It can be easily found by using binomial exapansion.)

Then $3^{100} \equiv 1 \pmod {40}$ .Here $3^{100} = 40 k +1$ .Putting this we get:

$3^{3^{100}}=3^{40 k+1} = 3^{40k}.3 \equiv 1^k.3 \pmod {100}$ .

$3^{3^{100}} \equiv 3 \pmod {100}$

Relevant wiki: Euler's Theorem

We need to find $3^{3^{100}} \text{ mod 100}$ .

$\begin{aligned} 3^{3^{100}} & \equiv 3^{3^{100} \text{ mod }\color{#3D99F6}\phi (100)} \text{ (mod 100)} & \small \color{#3D99F6} \text{Since } \gcd (3, 100) = 1, \text{ Euler's theorem applies.} \\ & \equiv 3^{3^{100} \text{ mod }\color{#3D99F6} 40} \text{ (mod 100)} & \small \color{#3D99F6} \text{Euler's totient function } \phi(100) = 40 \\ & \equiv 3^{3^{100 \text{ mod }\color{#3D99F6}\phi (40)}\text{ mod 40}} \text{ (mod 100)} & \small \color{#3D99F6} \text{Since } \gcd (3, 40) = 1, \text{ Euler's theorem applies.} \\ & \equiv 3^{3^{100 \text{ mod }\color{#3D99F6}16} \text{ mod 40}} \text{ (mod 100)} & \small \color{#3D99F6} \text{Euler's totient function } \phi(40) = 16 \\ & \equiv 3^{3^4 \text{ mod 40}} \text{ (mod 100)} \\ & \equiv 3^{81 \text{ mod 40}} \text{ (mod 100)} \\ & \equiv 3^1 \equiv \boxed{3} \text{ (mod 100)} \end{aligned}$

Set p = 101, 3^100 congruent to 1 mod 101, 3^1 mod 101 gives us 3.

Observe that if $a$ is relatively prime to $2^2 = 4$ and $25$ (noting that $100 = 25 \cdot 4$ ) $\begin{array}{rl} a^{20} &\equiv 1 \bmod 25\\ a^{2} &\equiv 1 \bmod 4 \end{array}$ In this case, since $a^{20} \equiv 1 \bmod 4$ also, by Chinese Remainder Theorem , $a^{20} \equiv 1 \bmod 100$ which leads us to evaluate $3^{100} \bmod 20$ .

---

Evaluating $3^{100} \bmod 20$

Observe that $20 = 2^2 \cdot 5$ . If $b$ is relatively prime to $2^2 = 4$ and $5$ , $\begin{array}{rl} b^2 &\equiv 1 \bmod 4\\ b^4 &\equiv 1 \bmod 5 \end{array}$ Chinese Remainder Theorem shows that $b^4 \equiv 1 \bmod 20$ . Therefore, $\begin{array}{rl} 3^{100} &\equiv \left(3^{25}\right)^4 \bmod 20\\ &\equiv 1 \bmod 20 \end{array}$ which is the exponent of $3$ .

---

Answer

Thus, we have $\boxed{3}$ as the answer.

The last two digits are 03 which is the same as 3. I will provide a complete solution later on.