# Thread: Find the remainder in the range 0 to 999 when 7^(8^9) is divided by 1000

1. ## Find the remainder in the range 0 to 999 when 7^(8^9) is divided by 1000

Hey guys,

Im confused with this :s

Find the remainder in the range 0 to 999 when 7^(8^9) is divided by 1000

We're dealing with a huge power, and it confused me as to how I am supposed to work it out.

I could start with doing

7 = 7 mod 1000
7^2 = 49 mod 1000
7^3 = 343 mod 1000
7^4 = 401 mod 1000

and maybe work it out with multiples of them? But then again the number (8^9) is huge so it might not be practical.

I was thinking of using Fermats Little Theorem, but I am unsure as to where I should begin.

Any help would be appreciated!

2. Since 7 is coprime with 1000, by the Euler's theorem, $7^{\varphi(1000)}\equiv1\pmod{1000}$, where $\varphi(n)$ is Euler's totient function. The last link shows that $\varphi(1000)=\varphi(2^3\cdot5^3)=1\cdot2^2\cdot4 \cdot5^2=400$.

So, the first step is to find the remainder of $8^9$ and 400. I got 128. Next, we need to find the remainder of $7^{128}$ and 1000. I did the following: $7^{128}=49^{64}=2401^{32}\equiv401^{32}\equiv801^{ 16}\equiv\dots\equiv801\pmod{1000}$.

3. Thanks a lot!

I understand it perfectly now thank you again!!