§ 27.15. Chinese Remainder Theorem

Permalink:: http://dlmf.nist.gov/27.15

The Chinese remainder theorem states that a system of congruences $x\equiv a_{1}\;\;(\textrm{mod}m_{1}),\dots,x\equiv a_{k}\;\;(\textrm{mod}m_{k})$ , always has a solution if the moduli are relatively prime in pairs; the solution is unique (mod $m$ ), where $m$ is the product of the moduli.

This theorem is employed to increase efficiency in calculating with large numbers by making use of smaller numbers in most of the calculation. For example, suppose a lengthy calculation involves many 10-digit integers. Most of the calculation can be done with five-digit integers as follows. Choose four relatively prime moduli $m_{1},m_{2},m_{3}$ , and $m_{4}$ of five digits each, for example $2^{{16}}-3$ , $2^{{16}}-1$ , $2^{{16}}+1$ , and $2^{{16}}+3$ . Their product $m$ has 20 digits, twice the number of digits in the data. By the Chinese remainder theorem each integer in the data can be uniquely represented by its residues (mod $m_{1}$ ), (mod $m_{2}$ ), (mod $m_{3}$ ), and (mod $m_{4}$ ), respectively. Because each residue has no more than five digits, the arithmetic can be performed efficiently on these residues with respect to each of the moduli, yielding answers $a_{1}\;\;(\textrm{mod}m_{1})$ , $a_{2}\;\;(\textrm{mod}m_{2})$ , $a_{3}\;\;(\textrm{mod}m_{3})$ , and $a_{4}\;\;(\textrm{mod}m_{4})$ , where each $a_{j}$ has no more than five digits. These numbers, in turn, are combined by the Chinese remainder theorem to obtain the final result $\;\;(\textrm{mod}m)$ , which is correct to 20 digits.

Even though the lengthy calculation is repeated four times, once for each modulus, most of it only uses five-digit integers and is accomplished quickly without overwhelming the machine's memory. Details of a machine program describing the method together with typical numerical results can be found in Newman (1967). See also Apostol and Niven (1994, pp. 18–19).