# 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$ – J. W. Tanner Aug 2 at 2:07
• It can't be that $3^{50}\equiv1\mod125$, since $3^{50}\equiv3^2\equiv4\mod5$ – J. W. Tanner Aug 2 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{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.

• Thank you. This proof seems nice and short. But what about the comment by J.W. Tanner? How is it useful and used? – Vasu090 Aug 2 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. – John Omielan Aug 2 at 2:19
• Thank you for helping. Really appreciate it. – Vasu090 Aug 2 at 2:21
• @Vasu090 You're welcome. My original answer showed using both sets of prime factors but, as J.W.Tanner's comment indicated, it's often easier to deal with each set of prime factors separately. I should've indicated that originally. – John Omielan Aug 2 at 2:23

$$\!\!\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. – Bill Dubuque Aug 2 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. – Bill Dubuque Aug 2 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 :-). – Jyrki Lahtonen Aug 2 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. – Bill Dubuque Aug 2 at 13:31
• Thanks for your help! – Andrew Aug 4 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$$