8.4. The Chinese Remainder TheoremOne of the most useful results of number theory is the Chinese remainder theorem (CRT).[7] In essence, the CRT says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli.
The CRT can be stated in several ways. We present here a formulation that is most useful from the point of view of this text. An alternative formulation is explored in Problem 8.17. Let
where the mi are pairwise relatively prime; that is, gcd(mi, mj) = 1 for 1 j i A in ZM by a k-tuple whose elements are in Zmi using the following correspondence: Equation 8-7
where A ai ai = A mod mi for 1 The mapping of Equation (8.7) is a one-to-one correspondence (called a bijection) between ZM and the Cartesian product Zm1 x Zm2 x ... x Zmk. That is, for every integer A such that 0 M there is a unique k-tuple (a1, a2,..., ak) with 0 mi that represents it, and for every such k-tuple (a1, a2,..., ak) there is a unique integer A in ZM. Operations performed on the elements of ZM can be equivalently performed on the corresponding k-tuples by performing the operation independently in each coordinate position in the appropriate system. Let us demonstrate the first assertion. The transformation from A to (a1, a1,..., ak) is obviously unique; that is, each ai is uniquely calculated as ai = A mod mi. Computing A from (a1, a1,..., ak) can be done as follows. Let Mi = M/mi for 1 Mi = m1 x m2 x ... x mi-1 x mi+1 x ... x mk so that Mi 0(mod j Equation 8-8
By the definition of Mi it is relatively prime to mi and therefore has a unique multiplicative inverse mod mi So Equation (8.8) is well defined and produces a unique value ci. We can now compute: Equation 8-9
To show that the value of A produced by Equation (8.9) is correct, we must show that ai = A mod mi for 1 cj 0(mod j ci 1(mod ai = A mod mi. The second assertion of the CRT, concerning arithmetic operations, follows from the rules for modular arithmetic. That is, the second assertion can be stated as follows: If
then
One of the useful features of the Chinese remainder theorem is that it provides a way to manipulate (potentially very large) numbers mod M in terms of tuples of smaller numbers. This can be useful when M is 150 digits or more. However, note that it is necessary to know beforehand the factorization of M.
|