<s>[INST] Given $a^b \pmod {c}$, $a^b \pmod {d}$, $a^b \pmod {e}$, how can $a^b mod (c*d*e)$ be deduced? 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)$$
 [/INST] 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}$$
</s>