examples - Applications of the Chinese remainder theorem

Here is a neat example that predates David Speyer's example of fast parallel arithmetic, but uses the same trick.

Richard J. Lipton, Yechezkel Zalcstein: Word Problems Solvable in Logspace. J. ACM 24(3): 522-526 (1977)

In this paper, the Chinese remainder theorem is used to prove that the word problem on several types of groups are solvable in logspace. (The Chinese remainder theorem is not explicitly invoked, but one can use it to justify the algorithms.) For instance, the paper states:

Corollary 6. The word problem for finitely generated free groups is solvable in logspace.

The word problem for a finite group is to determine if a given product of group elements equals the identity. The results are proved by embedding a group into a group of matrices over the integers, then computing the matrix product modulo all small primes.