Section 16.5 An Application to Software Design
The Chinese Remainder Theorem is a result from elementary number theory about the solution of systems of simultaneous congruences. The Chinese mathematician Sun-tsï wrote about the theorem in the first century A.D. This theorem has some interesting consequences in the design of software for parallel processors.
Lemma 16.41.
Let \(m\) and \(n\) be positive integers such that \(\gcd( m, n) = 1\text{.}\) Then for \(a, b \in {\mathbb Z}\) the system
has a solution. If \(x_1\) and \(x_2\) are two solutions of the system, then \(x_1 \equiv x_2 \pmod{mn}\text{.}\)
Proof.
The equation \(x \equiv a \pmod{m}\) has a solution since \(a + km\) satisfies the equation for all \(k \in {\mathbb Z}\text{.}\) We must show that there exists an integer \(k_1\) such that
This is equivalent to showing that
has a solution for \(k_1\text{.}\) Since \(m\) and \(n\) are relatively prime, there exist integers \(s\) and \(t\) such that \(ms + nt = 1\text{.}\) Consequently,
or
Now let \(k_1 = (b-a)s\text{.}\)
To show that any two solutions are congruent modulo \(mn\text{,}\) let \(c_1\) and \(c_2\) be two solutions of the system. That is,
for \(i = 1, 2\text{.}\) Then
Therefore, both \(m\) and \(n\) divide \(c_1 - c_2\text{.}\) Consequently, \(c_2 \equiv c_1 \pmod{mn}\text{.}\)
Example 16.42.
Let us solve the system
Using the Euclidean algorithm, we can find integers \(s\) and \(t\) such that \(4s + 5t = 1\text{.}\) Two such integers are \(s = 4\) and \(t = -3\text{.}\) Consequently,
Theorem 16.43. Chinese Remainder Theorem.
Let \(n_1, n_2, \ldots, n_k\) be positive integers such that \(\gcd(n_i, n_j) = 1\) for \(i \neq j\text{.}\) Then for any integers \(a_1, \ldots, a_k\text{,}\) the system
has a solution. Furthermore, any two solutions of the system are congruent modulo \(n_1 n_2 \cdots n_k\text{.}\)
Proof.
We will use mathematical induction on the number of equations in the system. If there are \(k= 2\) equations, then the theorem is true by Lemma 16.41. Now suppose that the result is true for a system of \(k\) equations or less and that we wish to find a solution of
Considering the first \(k\) equations, there exists a solution that is unique modulo \(n_1 \cdots n_k\text{,}\) say \(a\text{.}\) Since \(n_1 \cdots n_k\) and \(n_{k+1}\) are relatively prime, the system
has a solution that is unique modulo \(n_1 \ldots n_{k+1}\) by the lemma.
Example 16.44.
Let us solve the system
From Example 16.42 we know that \(19\) is a solution of the first two congruences and any other solution of the system is congruent to \(19 \pmod{20}\text{.}\) Hence, we can reduce the system to a system of three congruences:
Solving the next two equations, we can reduce the system to
Solving this last system, we find that \(19\) is a solution for the system that is unique up to modulo \(1260\text{.}\)
One interesting application of the Chinese Remainder Theorem in the design of computer software is that the theorem allows us to break up a calculation involving large integers into several less formidable calculations. A computer will handle integer calculations only up to a certain size due to the size of its processor chip, which is usually a 32 or 64-bit processor chip. For example, the largest integer available on a computer with a 64-bit processor chip is
Larger processors such as 128 or 256-bit have been proposed or are under development. There is even talk of a 512-bit processor chip. The largest integer that such a chip could store with be \(2^{511} - 1\text{,}\) which would be a 154 digit number. However, we would need to deal with much larger numbers to break sophisticated encryption schemes.
Special software is required for calculations involving larger integers which cannot be added directly by the machine. By using the Chinese Remainder Theorem we can break down large integer additions and multiplications into calculations that the computer can handle directly. This is especially useful on parallel processing computers which have the ability to run several programs concurrently.
Most computers have a single central processing unit (CPU) containing one processor chip and can only add two numbers at a time. To add a list of ten numbers, the CPU must do nine additions in sequence. However, a parallel processing computer has more than one CPU. A computer with 10 CPUs, for example, can perform 10 different additions at the same time. If we can take a large integer and break it down into parts, sending each part to a different CPU, then by performing several additions or multiplications simultaneously on those parts, we can work with an integer that the computer would not be able to handle as a whole.
Example 16.45.
Suppose that we wish to multiply \(2134\) by \(1531\text{.}\) We will use the integers \(95\text{,}\) \(97\text{,}\) \(98\text{,}\) and \(99\) because they are relatively prime. We can break down each integer into four parts:
and
Multiplying the corresponding equations, we obtain
Each of these four computations can be sent to a different processor if our computer has several CPUs. By the above calculation, we know that \(2134 \cdot 1531\) is a solution of the system
The Chinese Remainder Theorem tells us that solutions are unique up to modulo \(95 \cdot 97 \cdot 98 \cdot 99 = 89{,}403{,}930\text{.}\) Solving this system of congruences for \(x\) tells us that \(2134 \cdot 1531 = 3{,}267{,}154\text{.}\)
The conversion of the computation into the four subcomputations will take some computing time. In addition, solving the system of congruences can also take considerable time. However, if we have many computations to be performed on a particular set of numbers, it makes sense to transform the problem as we have done above and to perform the necessary calculations simultaneously.