<s>[INST] Last 3 digits of $3^{999}$ I know that it's $3^{999} \mod 1000$ and since $\varphi(1000) = 400$ and $3^{400}\equiv1 \mod1000$ it will be equivalent to $3^{199} \mod 1000$ but what should I do from then? Or am I wrong about this from the start?
 [/INST] Simple computation, and the fact that $\phi(8)=4$, gives
$$
\begin{align}
3^{999}
&\equiv3^3\\
&\equiv3\pmod8\tag1
\end{align}
$$
The square and multiply algorithm, and the fact that $\phi(125)=100$, gives
$$
\begin{align}
3^{999}
&\equiv3^{99}\\
&\equiv42\pmod{125}\tag2
\end{align}
$$
The Extended Euclidean Algorithm, as implemented in this answer, gives
$$
\begin{array}{r}
&&15&1&1&1&2\\\hline
1&0&1&-1&2&-3&8\\
0&1&-15&16&-31&47&-125\\
125&8&5&3&2&1&0
\end{array}\tag3
$$
which says that
$$
47\cdot8-3\cdot125=1\tag4
$$
Equation $(4)$ implies both
$$
\begin{align}
-375&\equiv1\pmod8\\
-375&\equiv0\pmod{125}
\end{align}\tag5
$$
and
$$
\begin{align}
376&\equiv0\pmod8\\
376&\equiv1\pmod{125}
\end{align}\tag6
$$
Thus, to satisfy $(1)$ and $(2)$, we compute
$$
\begin{align}
3^{999}
&\equiv42\cdot376-3\cdot375\\
&\equiv667&\pmod{1000}\tag7
\end{align}
$$
</s>