Find the last three digits of $383^{101}$

Question

We have to find out $383^{101} \equiv ? \pmod {1000}$. I know that $383^2 ≡ 689 \pmod {1000}$ $383^5≡143 \pmod {1000}$

I know that $ϕ(1000)=400 >101 $ from Euler. It definitely can't help me. I don't know how to continue. I can't use the Chinese Remainder Theorem.

Answer 1

Observe that $383\equiv 3\pmod{10}$. Since $3^1\equiv 3\pmod{10}$, $3^2\equiv 9\pmod{10}$, $3^3\equiv 7\pmod{10}$, and $3^4\equiv 1\pmod{10}$, we know that the order of $383\equiv 3\pmod{10}$ is $4$. Therefore, the order of $383$ must be divisible by $4$.

Now, if we extend this to $383\equiv 83\pmod{100}$, we have that $83^4=47458321\equiv 21\pmod{100}$. Then, $(83^4)^n\equiv (2\cdot 10+1)^n\equiv 2n\cdot 10+1\pmod{100}$ by the binomial theorem. Therefore, we expect the order of $83\pmod{100}$ to be $20$.

Continuing in this manner, we can use the method of successive squares to determine $383^{20}\pmod{1000}$. In particular, since $20=4+16$, we have \begin{align*} 383^1&\equiv 383\pmod{1000}\\ 383^2&=146689\equiv 689\pmod{1000}\\ 383^4&\equiv 689^2=474721\equiv 721\pmod{1000}\\ 383^8&\equiv 721^2=519841\equiv 841\pmod{1000}\\ 383^{16}&\equiv 841^2=707281\equiv 281\pmod{1000} \end{align*} Therefore, $383^{20}=383^4\cdot 383^{16}\equiv 721\cdot 281=202601\equiv 601\pmod{1000}.$ Therefore, $(383^{20})^m\equiv (6\cdot 100+1)^m\pmod{1000}$. Using the binomial theorem, we find that $383^{20m}\equiv 6m\cdot 100+1\pmod{1000}$, in order for this to be $1$, we need $m$ to be a multiple of $5$. Hence, $383^{100}\equiv 1\pmod{1000}$. Hence $383^{101}\equiv 383\pmod{1000}$.

Answer 2

I don't know what the expected approach to this problem is, but using $101 = 50 + 51$, $50 = 25 + 25$, $51 = 50 + 1$, $25 = 24 + 1$, $24 = 12 + 12$, $12 = 6 + 6$, $6 = 3 + 3$, $3 = 2 + 1$, you should be able to solve it by hand in a few minutes.

Answer 3

Answer: $\boxed{383}$. Let's solve it:

$\phi(125)=100$ and $\phi(8)=4$. Least common multiple of $100$ and $4$ is $100$.

$$383^{100} \equiv 1 \pmod{125}$$ and $$383^{4} \equiv 1 \pmod{8}$$ Therefore $383^{100} \equiv 1 \pmod{1000}$. Hence we yields $$383^{101} \equiv 383 \pmod{1000} $$

Answer 4

The units digit of $383^1$ is $3$.
The units digit of $383^2$ is $9$ ($3 \times 3 = 9$).
The units digit of $383^3$ is $7$ ($3 \times 9 = 27$).
The units digit of $383^4$ is $1$ ($3 \times 7 = 21$).

Calculating,

$\; 383^4 \equiv 721 \pmod{1000}$

Calculating,

$\; 383^{101} \equiv 383 \cdot 721^{25} \equiv 383 \cdot (1 + 720)^{25} \equiv 383 \cdot (1 + 2^4 \cdot 3^2 \cdot 5^1)^{25} \equiv$
$\quad\quad\quad\quad \; 383 \; \bigr(1 + \binom{25}{1}\,2^4 \cdot 3^2 \cdot 5^1 + \binom{25}{2}\,2^8 \cdot 3^4 \cdot 5^2 + 0\bigr) \equiv$
$\quad\quad\quad\quad \; 383 \; \bigr(1 + 0 + 0 + 0 \bigr) \equiv 383 \pmod{1000}$