![if !IE]> <![endif]>
THE CHINESE REMAINDER THEOREM
One of the most useful results of number theory is the Chinese remainder theorem (CRT). 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 10 integers in Z10, that is the integers 0 through 9, can be reconstructed from their two residues modulo 2 and 5 (the relatively prime factors of 10). Say the known residues of a decimal digit x are r2 = 0 and r5 = 3; that is, x mod 2 = 0 and x mod 5 = 3. Therefore, x is an even integer in Z10 whose remainder, on division by 5, is 3. The unique solution is x = 8.
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
By the definition of Mi, it is relatively prime to mi and therefore
has a unique multi-
plicative inverse mod mi.
So Equation (8.8) is well defined and produces a unique value ci. We can now compute
One of the useful features of the Chinese remainder theorem is that it pro-vides 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.
Copyright ¬© 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.