This question covered large exponents on the $b$ side. What about the $m$ side?
Given:
$$a^b \pmod m$$
where $m$ is a large compound number.
For example:
Given
$$5^{2003} \pmod {7} \equiv 3$$ $$5^{2003} \pmod {11} \equiv 4$$ $$5^{2003} \pmod {13} \equiv 8$$
how can one quickly deduce:
$$5^{2003} mod (7*11*13)$$
Let the number be $x$.
Then we get from the Chinese Remainder Theorem: $$5^{2003}\pmod{7\cdot 11\cdot 13}\equiv x\iff\begin{cases}x\pmod 7\equiv 3\\x\pmod{11}\equiv 4\\ x\pmod{13}\equiv 8\end{cases}$$
The following is one method to apply the Chinese Remainder Theorem.
From the 3rd equation: $$x=13k+8\tag 4$$
Combine with the 1st equation: $$13k+8\equiv -k+1\equiv 3\pmod 7\implies k=7l-2$$ Substitute in (4): $$x=13(7l-2)+8=13\cdot7l-18\tag 5$$ Combine with 2nd equation: $$13\cdot7l-18\equiv 3l+4\equiv 4\pmod{11} \implies l=11m$$ Substitute in (5): $$x=13\cdot7\cdot 11m -18 \equiv -18\pmod{7\cdot 11\cdot 13}$$