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

Question

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

Answer 1

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.

Answer 2

$\!\!\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}$

Answer 3

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$