Chinese Remaindering
If \(p_0, p_1,\ldots, p_{n-1}\) are co-prime, then there's a one-to-one
correspondence between \(n \text{ mod } (m = p_0 \times p_1 \times \cdots \times p_{n-1})\)
and the tuple comprising the residues of \(n\) modulo \((p_0, p_1,\ldots, p_{n-1})\).
One of the cool things about Chinese Remaindering is that multiplication and addition of numbers modulo
\(m\) can be done in the transformed domain where it's much easier, and then invert the result
back to get the corresponding result modulo \(m\).
For e.g., consider the residue system for \(p_0=4, p_1=7\). In this residue system \(13\) is represented by
the tuple \((6,1)\) and \(12\) is represented by the tuple \((5,0)\). If we want to find
\(13 \times 12 \pmod{28}\), we can
instead multiply component-wise the tuples \((6,1) \times (5,0)\) to get \((30 \text{ mod } 4, 0 \text { mod } 7)\).
That gives us \((2,0)\). When we invert this tuple, we get \(16\). Now \(13\times12 \text{ mod } 28 = 16\)!
Type upto 3 integers > 1 that are co-prime to each other