# 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

• By Euler's theorem, $3^{100}\equiv1\mod125,$ and also $3^{100}=(3^2)^{50}\equiv1\mod8$ Aug 2, 2019 at 2:07
• It can't be that $3^{50}\equiv1\mod125$, since $3^{50}\equiv3^2\equiv4\mod5$ Aug 2, 2019 at 2:36

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{aligned} \phi(1000) & = \phi(2^3)\phi(5^3) \\ & = (2^2(2-1)) \times (5^2(5-1)) \\ & = 16 \times 25 \\ & = 400 \end{aligned}\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.

• Thank you. This proof seems nice and short. But what about the comment by J.W. Tanner? How is it useful and used? Aug 2, 2019 at 2:12
• @Vasu090 You are welcome. I've added some more details to indicate how you can use the values separately as a short-cut to minimize the amount of work to confirm what the result should be. Aug 2, 2019 at 2:19

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

• This sketch leaves some work for you (e.g. combining via CRT or lcm). If you need further details let me know. Aug 2, 2019 at 3:20
• It would be interesting to know the reason for the downvote, e.g. so the answer can be improved if need be. Aug 2, 2019 at 3:47
• Using the order test is, of course, fine. For this type of a question it may also be worth our while to use the fact that if $\gcd(a,p)=1$, $p$ a prime, and the order of $a$ modulo $p^n$ is $m$, then the order of $a$ modulo $p^{n+1}$ is either $m$ or $pm$. Here $a=3$, $p=5$, and the starting point would be that $3$ is primitive modulo $5$. Organizing the argument this way allows us to skip the easy $3^{50}\not\equiv1$. So does not really save much! Meaning that whichever tool is easier to refer to should be used :-). Aug 2, 2019 at 8:13
• @Jyrki Indeed, I hoped that my remark "it fails $\bmod 5$" might be enough of a hint to help the OP discover such simple relationships. Not clear what other "tools" you refer to. Generally the Order Test can save much work vs. more naive approaches. Aug 2, 2019 at 13:31
• Thanks for your help! Aug 4, 2019 at 4:27

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$$