About the Project
27 Functions of Number TheoryApplications

§27.15 Chinese Remainder Theorem

The Chinese remainder theorem states that a system of congruences xa1(modm1),,xak(modmk), 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 m1,m2,m3, and m4 of five digits each, for example 2163, 2161, 216+1, and 216+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 m1), (mod m2), (mod m3), and (mod m4), 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 a1(modm1), a2(modm2), a3(modm3), and a4(modm4), where each aj has no more than five digits. These numbers, in turn, are combined by the Chinese remainder theorem to obtain the final result (modm), 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).