$777^{401} \pmod {1000}$ is?

Question

here's an arithmetic question : find the last $3$ digits of $777^{401}$. I don't know where to start. The chinese remainder theorem gives a double congruence modulo $8$ and $125$ but I don't think this is really helping, there might be a simpler way. Any help is welcome !

Answer 1

Since $777\equiv 1 \pmod{2^3}$ and $777\equiv 27\pmod{5^3}$. Moreover $\varphi(5^3)=4\cdot 5^2$ and $401 \equiv 1\pmod{100}$ therefore we have $777^{401}\equiv 1\pmod{8}$ and $777^{401} \equiv 27\pmod{125}$.

Then by CRT the solution exists and it is unique modulo $1000$, i.e. $$ 777^{401}\equiv 777 \pmod{1000}. $$

Answer 2

$$777=7\times 3\times 37~\textrm{and}~1000=5^3\times 2^3\implies \gcd(777,1000)=1$$

Hence, we use Euler's theorem. We have, $$\phi(1000)=\phi(5^3\times 2^3)=1000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=400$$

Now, according to Euler's theorem, we have,

$$777^{\phi(1000)}\equiv 1\pmod{1000}\implies 777^{400}\equiv 1\pmod{1000}$$

$$\implies 777^{401}=777^{401~\bmod~400}\equiv 777^1\equiv 777\pmod{1000}$$

Answer 3

Use Euler's theorem: As $\phi(1000)= \phi(125)\times \phi(8)= 400$ we have $777^{400}\equiv1$ mod $1000$, as $\gcd(777,1000)=1$. So the answer is $777^{401}\equiv777$ mod $1000$.

Answer 4

That is a good place to start, but not necessary the way the problem is given.

Hint 1:

What theorems do you know that can help reduce exponents in a congruence? (If you don't know the answer look at Hint 2)

Hint 2: this theorem (click after looking at hint 1)

Solution:

Consider $\varphi(8)$ and $\varphi(125)$. $\varphi(8)=4 | 400$, and $\varphi(125)=100 | 400$, and since $\varphi$ is multiplicative $\varphi(1000)=400 | 400$. So by Euler's theorem, if 777 is relatively prime to 1000 (which it is), $777^{401}= 777^{400}\cdot 777 \equiv 777 \pmod{1000}$. In fact, by Chinese Remainder Theorem, $777^{100}\equiv 1 \pmod{1000}$ since $100$ is the least common multiple of $4$ and $100$.