What is the smallest positive integer $n > 1$ such that $3^n$ ends with $003$? 
What is the smallest positive integer $n > 1$  such that $3^n$ ends
with $003$?

Hello! I hope you are doing great. I was doing some number theory and solving the above question but I could not. Any help would be appreciated.

Here's what I've done so far:
Since $3^n$ ends with $003$, hence, $3^{n-1}$ should end with $001$. Since the units digit of the power is $1$, $n-1$ is a multiple of $4$.
Also note that $125 | 3^{n} - 003$. Not sure how this would help.

That's it. I have not made any more progress.
Thank You
 A: The statement $3^{n-1}$ ends in $001$ means that $n-1$ is the Multiplicative order of $3$ modulo $1000$. Lagrange's Theorem says this will always divide Euler's totient function. Here we get that
$$\begin{equation}\begin{aligned}
\phi(1000) & = \phi(2^3)\phi(5^3) \\
& = (2^2(2-1)) \times (5^2(5-1)) \\
& = 16 \times 25 \\
& = 400
\end{aligned}\end{equation}\tag{1}\label{eq1}$$
Thus, you just need to check the various factors of $400$ to determine the first one where $3$ to that power is congruent to $1$ modulo $1000$.
However, a generally simpler & faster method, as J. W. Tanner's question comment indicates, is to check each set of prime factors separately. Thus, you get from above that $\phi(125) = 25 \times 4 = 100$ and $\phi(8) = 4$. However, the order for $3$ modulo $8$ is actually $2$ here since $3^2 \equiv 1 \pmod 8$. Thus, you can determine that $n - 1 = \text{lcm}(4,100) = 100$ works. However, to determine the smallest $n-1$, you should check the even factors of $100$ to see if any of them, call it $f$, give that $3^f \equiv 1 \pmod{125}$. I did a quick manual check to determine there are no such smaller values.
A: $\!\!\bmod 1000\!:\, n\!>\!1\,$ is min with $\,3^n\!\equiv 3\!$ $\iff\! n\!-\!1\!>\!0\,$ is min with $3^{n-1}\!\equiv 1\!$ $\iff\! 3\,$ has order $\,n\!-\!1$
$\!\!\bmod 125\!:\,$ by  Euler $3^{100}\equiv 1\,$ so the order of $\,3\,$ divides $100.\,$ Notice $3^{50}\not\equiv 1\,$ (it fails $\!\bmod 5)$ and $\,3^{20}\not\equiv1\,$ (e.g. by repeated squaring), thus $\,3\,$ has order $100$ by the Order Test.
$\!\!\bmod 8\!:\  3^2\equiv 1\,\Rightarrow\, 3^{100}\equiv 1.\,$  Combining:  $\bmod 1000\!:\ 3\,$ has order $\,\bbox[5px,border:1px solid #c00]{n\!-\!1 = 100}$
A: As we need $3^m\equiv001\pmod{1000}\equiv1\pmod{10},$
$4\mid m$
$$3^{4n}=(10-1)^{2n}=(1-10)^{2n}\equiv1-\binom{2n}110+\binom{2n}210^2\pmod{1000}$$
We need $$-20n+100n(2n-1)\equiv0\pmod{1000}$$
$25$ must divide $n(5n-3)$
As $5\nmid(5n-3),25$  must divide $n$
