What is the remainder after dividing $(177 + 10^{15})^{166}$ by $1003 = 17 \cdot 59$ 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!

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.
