Chinese remainder theorem to find $1030^{989}\bmod\; 3003$?

Question

so this is a slightly different take on a question I asked, but instead of the product of two numbers- this time it is a very large number raised to a very large power.

I am meant to use the Chinese Remainder Theorem to solve this, I have attempted to reduce the $1030^{989}$ down using the power rules and mod as I go, and have eventually hit $842\bmod 3003$ and now I am unsure of where to go from here, (or even if reducing the power was the right step to take).

Step by step instruction works better than simply giving hints or general guidance, but any help you can give is of course appreciated.

Thank you

Answer 1

Hint: $3003 = 3 \cdot 7 \cdot 11 \cdot 13$ and so you reduce $1030 \bmod 3 , 7,11,13$ and $989 \bmod 2,6,10,12$.

Answer 2

We need to find the order of $1030\mod 3003$. For that, you can use the Chinese remainder theorem: as $3003=3\,7\,11\,13$, we have a ring isomorphism \begin{align} \mathbf Z/3003\mathbf Z&\simeq\mathbf Z/3\mathbf Z\times\mathbf Z/7\mathbf Z\times\mathbf Z/11\mathbf Z\times\mathbf Z/13\mathbf Z \\ n&\mapsto(n\bmod 3,n\bmod 7,n\bmod 11,n\bmod 13 \end{align} Now it happens that $\qquad1030\equiv\begin{cases}1\bmod3\;\text{and }\bmod 7,\\7\bmod 11,\\3\bmod 13.\end{cases} $

On the other hand $7$, hence $1030$ has order $10\bmod 11$ and $3$, hence $1030$ has order $3\bmod 13$. So $1030$ has order $\bmod 3003$ the l.c.m. of the orders of each of its reductions, i.e. $1003$ has order $30$ and $$1030^{989}\equiv1030^{989\bmod 30}=1030^{-1}\mod 3003.$$ There remains to find the inverse of $1030\bmod 3003$, which is easily done with the extended Euclidean algorithm.