3
$\begingroup$

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

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

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you. This proof seems nice and short. But what about the comment by J.W. Tanner? How is it useful and used? $\endgroup$
    – Vasu090
    Aug 2, 2019 at 2:12
  • $\begingroup$ @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. $\endgroup$ Aug 2, 2019 at 2:19
4
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ This sketch leaves some work for you (e.g. combining via CRT or lcm). If you need further details let me know. $\endgroup$ Aug 2, 2019 at 3:20
  • 2
    $\begingroup$ It would be interesting to know the reason for the downvote, e.g. so the answer can be improved if need be. $\endgroup$ Aug 2, 2019 at 3:47
  • 2
    $\begingroup$ 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 :-). $\endgroup$ Aug 2, 2019 at 8:13
  • $\begingroup$ @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. $\endgroup$ Aug 2, 2019 at 13:31
  • $\begingroup$ Thanks for your help! $\endgroup$ Aug 4, 2019 at 4:27
2
$\begingroup$

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$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .