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?

Solution 1:

Using Carmichael function will be beneficial here as $\displaystyle\lambda(1000)=100$

$$\implies 3^{100n}\equiv1^n\pmod{1000}\equiv1$$ for any integer $n$

As $(3,1000)=1,$ this implies $$3^{100n-1}\equiv3^{-1}$$

As $\displaystyle 999\equiv-1\pmod{1000}\implies3^{-1}\equiv-333\equiv1000-333$

Solution 2:

To know $3^n\bmod 1000$ it is enough to know $3^n\bmod 8$ and $3^n\bmod 125$. From $3^2\equiv 1\pmod 8$ we conclude $3^{1000}\equiv 1\pmod 8$. From $\phi(125)=100$, we conclude $3^{1000}=(3^{100})^{10}\equiv 1\pmod{125}$. Therefore $3^{1000}\equiv 1\pmod {1000}$. This implies $3^{999}\equiv 667\pmod{1000}$