If 15 was coprime to $\varphi(5000) = 2000$ we could use Euler's theorem, but it's not.
I solved this question by observing that for even $r \geq 4$ we have $15^r \equiv 625 \bmod 5000$, which I proved by induction, and observing that $100!$ is even. But this question appears early in the number theory course that I'm taking, so I feel like there must be a direct solution via that relies only only on basic number theory ideas: Fermat's Little Theorem, Euler's theorem, Chinese Remainder Theorem, etc.
I suspect we can use Chinese Remainder Theorem but I don't have a good intuition for how to use it yet.
Best Answer
I think the method you used is the best way to go.
Still, if you want to do it via the Chinese Remainder theorem....
Note that $5000=2^3\times 5^4$ so solve the problem mod $2^3$ and mod $5^4$ separately. Clearly the answer is $0\pmod {5^4}$ so that just leaves $2^3$. But $15\equiv -1\pmod {2^3}$ so the answer is $1\pmod {2^3}$. Now apply the CRT to $$n\equiv 0 \pmod {625}\quad \&\quad n\equiv 1\pmod {8}$$
Since $625\equiv 1 \pmod {8}$ the answer is $625$.