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
Best Answer
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.