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$
  • 3
    $\begingroup$ By Euler's theorem, $3^{100}\equiv1\mod125,$ and also $3^{100}=(3^2)^{50}\equiv1\mod8$ $\endgroup$ – J. W. Tanner Aug 2 at 2:07
  • 2
    $\begingroup$ It can't be that $3^{50}\equiv1\mod125$, since $3^{50}\equiv3^2\equiv4\mod5$ $\endgroup$ – J. W. Tanner Aug 2 at 2:36
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$
  • $\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 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$ – John Omielan Aug 2 at 2:19
  • $\begingroup$ Thank you for helping. Really appreciate it. $\endgroup$ – Vasu090 Aug 2 at 2:21
  • $\begingroup$ @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. $\endgroup$ – John Omielan Aug 2 at 2:23
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$
  • 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$ – Bill Dubuque Aug 2 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$ – Bill Dubuque Aug 2 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$ – Jyrki Lahtonen Aug 2 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$ – Bill Dubuque Aug 2 at 13:31
  • $\begingroup$ Thanks for your help! $\endgroup$ – Andrew Aug 4 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.