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?
 A: 
We still need to find $3^{19}\pmod{100}$.

Because the Carmichael function of $100$ is $20$, and $3$ is relatively prime to $100$,
$3^{20}\equiv1\bmod100$, so, if $x\equiv3^{19}\bmod100$, then $3x\equiv1\bmod100$.
So $x$ is the inverse of $3\bmod100$.
To be pedantic, that could be found using the extended Euclidean algorithm:
$100=3\times33+1$, so $100+3\times(-33)=1$.  I.e., $x\equiv-33\equiv67\bmod100$.
A: You can do this using the Chinese remainder theorem and by calculating some powers.
$3^{99} = (3^3)^{33} \equiv 2^{33} \pmod{25} = (2^7)^4 \times 2^5 \equiv 3^4 \times 2^5 = 3^3 \times 3 \times 2^5 \equiv 3 \times 2^6 \equiv 17$.
$3^{99} \equiv (-1)^{99} \equiv 3 \pmod{4}$.
So we need the unique number satisfying those constraints in $[0, 100)$, which is $67$.

Your way comes out much the same: $3^{19}$ mod $4$ is $3$ again, and $3^{19}$ mod $25$ is $(3^3)^6 \times 3$ which is $2^6 \times 3$ which is again $17$.
A: 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)$.
A: Just to give a different approach, observe that
$$3^{99}=3^{1+2\cdot49}=3\cdot9^{49}=-3(1-10)^{49}\equiv-3(1-49\cdot10)\mod100$$
(where in the binomial expansion $(1-10)^n=1-10n+{n\choose2}100+\cdots$ we drop everything after the first two terms), and
$$-3(1-490)=3\cdot489\equiv3\cdot89\equiv-3\cdot11=-33\equiv67\mod100$$
