<s>[INST] What is $3^{99} \pmod{100}$? I saw this post on how to solve $3^{123}\pmod{100}$ using Euler's Totient Theorem.
How about for $3^{99}\pmod{100}$? It seems more complicated because applying Euler's Totient Theorem gets us $3^{40}\equiv 1\pmod{100}$. This means $3^{80}\equiv 1 \pmod{100}$, which isn't enough, because we still need to find $3^{19}\pmod{100}$.
Now, when the terms are listed, a pattern does emerge.
$$\begin{array}{|c|c|c|c|}
\hline
3 & 9 & 27 & 81 \\ \hline
43 & 29 & 87 & 61 \\ \hline
83 & 49 & 47 & 41\\ \hline
23 & 69 & 07 & 21 \\ \hline
03 & 89 & 67 & 01 \\ \hline
\end{array}$$
And $3^{19}$ ends in $67$.
But how can I find this in other methods, besides bashing? Is there some sort of theorem that I can use?
 [/INST] We have $ 3^4 \equiv 81 \ (\text{mod} \ 100), \\ 3^5=243 \equiv 43 \ (\text{mod} \ 100),\\ 3^{10}=43^2 =1849 \equiv 49  \ (\text{mod} \ 100).$
Then $ \ 3^{20} =49^2=2401 \equiv 1 \ (\text{mod} \ 100) \Rightarrow 3^{80} \equiv 1 \ (\text{mod} \ 100).$
Also $3^9=3^4 \cdot 3^5 = 81 \cdot 43=3483 \equiv 83 \ (\text{mod} \ 100).$
Thus,$$ 3^{99}=3^9 \cdot.3^{10} \cdot 3^{80}=83 \cdot 49 \cdot 1=4067 \equiv 67 \ (\text{mod} \ 100) .$$
Hence $3^{99} \equiv {\color{blue}{67}} \ (\text{mod} \ 100)$.
</s>