[Math] Applications of the Chinese remainder theorem

ac.commutative-algebraapplicationsbig-listexamplesnt.number-theory

As the title suggests I am interested in CRT applications. Wikipedia article on CRT lists some of the well known applications (e.g. used in the RSA algorithm, used to construct an elegant Gödel numbering for sequences…)

Do you know some other (maybe not so well known) applications? Or interesting problems (recreational? or from mathematical competitions like IMO?) which can be solved using CRT. Or any good references or examples in that direction.

I hope that with this I will have better understanding of CRT and how to use it in general.

Best Answer

Parallel computation: Suppose you have a huge computation to do that involves adding, multiplying and subtracting integers. Possibly also dividing but, if so, only division by numbers in a finite set S which you already know.

Choose primes $p_1$, $p_2$, ..., $p_r$ which do not divide any element of $S$, and such that $p_1 p_2 \cdots p_r$ is surely larger than your answer. Split your computation over $r$ processors, the $i$th of which computes the answer modulo $p_i$. Use CRT to put your answer back together in the end.

This was the method used in the recent computation of the Kazhdan-Lustig-Vogan polynomials of E8.