What is $2007^{2008}\pmod{1000}$?

Question

I want to find out what is$$2007^{2008}\pmod{1000}$$.

I used this website to find that the answer is $801$, but I'm not sure how they got there.

My attempt:

$2007^{2008}\pmod{1000}\equiv7^{2008}\pmod{1000}\equiv2401^{502}\pmod{1000}\equiv401^{502}\pmod{1000}\equiv160801^{251}\pmod{1000}\equiv801^{251}\pmod{1000}$

I pretty much gave up after this because it was getting too tedious and I didn't feel like this was the right approach. I got the $801$ but it has a power of $251$ which I don't know how to get rid of. Is there a quicker way to do this? If so, how? Thanks in advance!

Answer 1

Hint:

$$7^{2008}=(50-1)^{1004}\equiv(1-50)^{1004}\pmod{1000}$$

$$\equiv1-\binom{1004}150+\binom{1004}250^2\pmod{10^3}$$

Now $\displaystyle\binom{1004}2\equiv0\pmod2$

$\implies\displaystyle\binom{1004}250^2\equiv0\pmod{2\cdot50^2}\equiv0\pmod{1000}$

Alternatively, $7^4=(1+2400)$

$$7^{4n}=(1+2400)^n\equiv1+2400n\pmod{1000}$$

So, ord$_{1000}7\equiv5\cdot4,2008\equiv8\pmod{20}$

$$\implies7^{2008}\equiv7^8\pmod{1000}\equiv(1+2400)^2\equiv1+2\cdot2400+2400^2\equiv1+4800$$

Answer 2

By Euler's Theorem, we know that: $$7^{\phi(1000)}=7^{400}\equiv1\pmod{1000}$$ Therefore, $$2007^{2008}\equiv7^{2008}\equiv7^8\equiv801\pmod{1000}$$