What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$

Question

What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$? I have made several observations about the problem but I cant see how they lead me to an answer.

Observation one: $\phi(1003) = 16 \cdot 58 =8 \cdot 116$ (Euler totient function).

Observation two: $$10^{15} \mod 1003 = 1000^5 \mod 1003 = (-3)^5 \mod 1003 = -243 \mod 1003.$$ So $$177 + 10^{15} \mod 1003 = 177 - 243 \mod 1003= - 66 \mod 1003 = -2\cdot 3 \cdot 11 \mod 1003.$$

Observation three: $(\mathbb Z/1003 \mathbb Z)\cong (\mathbb Z/17\mathbb Z)\times (\mathbb Z/59\mathbb Z)$ by the chinese remainder theorem.

I am really struggling to use any of these to form some sort of coherent argument. I thought maybe I could use observation one and use Fermat's little theorem to conclude $((177 + 10^{15})^{166})^8 \mod 1003= 1 \mod 1003$, but then I should first check that $(177 + 10^{15})^{166} \in (\mathbb Z/1003 \mathbb Z)^*$. Even then, the problem would be reduced to looking for elements in $a\in(\mathbb Z/1003 \mathbb Z)^*$ such that $a^8 = 1$, for instance $a = 1002$ would work, but then I wonder if this is the only element in $(\mathbb Z/1003 \mathbb Z)^*$ such that its eighth power is unit... probably not. If anyone can make sense of my observations and use them to find an answer, or if anyone has a different method to see the answer I would be very happy to hear it! Thanks in advance!

Answer 1

I'd try to do it more basically:

$$10^3=-3\pmod{1003}\implies 10^{15}=(-3)^5=-243=760\pmod{1003}$$

So finally

$$177+10^{15}=177-243=-66=937\pmod{1003}$$

Answer 2

Write $x=177+10^{15}=177+1000^5$. Modulo $17$ we have $$x=7+(-3)^5=-236=2\quad\Rightarrow\quad x^4=-1\quad\Rightarrow\quad x^{166}=x^6=-4\ .$$ Modulo $59$ we get $$x=-3^5\quad\Rightarrow\quad x^{166}=3^{830}=3^{18}=-2\ .$$ Now use the Chinese Remainder Theorem.