  The Chinese Remainder Theorem for the integers says that every system of
congruence equations is solvable as long as the system satisfies an obvious
necessary condition. This statement can be generalized in a natural way to
arbitrary algebraic structures using the language of Universal Algebra. In this
context, an algebra is a structure of a first-order language with no relation
symbols, and a congruence on an algebra is an equivalence relation on its base
set compatible with its fundamental operations. A tuple of congruences of an
algebra is called a Chinese Remainder tuple if every system involving them is
solvable. In this article we study the complexity of deciding whether a tuple
of congruences of a finite algebra is a Chinese Remainder tuple. This problem,
which we denote CRT, is easily seen to lie in coNP. We prove that it is
actually coNP-complete and also show that it is tractable when restricted to
several well-known classes of algebras, such as vector spaces and distributive
lattices. The polynomial algorithms we exhibit are made possible by purely
algebraic characterizations of Chinese Remainder tuples for algebras in these
classes, which constitute interesting results in their own right. Among these,
an elegant characterization of Chinese Remainder tuples of finite distributive
lattices stands out. Finally, we address the restriction of CRT to an arbitrary
equational class $\mathcal{V}$ generated by a two-element algebra. Here we
establish an (almost) dichotomy by showing that, unless $\mathcal{V}$ is the
class of semilattices, the problem is either coNP-complete or tractable.
