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
has a solution. If
Proof.
The equation
This is equivalent to showing that
has a solution for
or
Now let
To show that any two solutions are congruent modulo
for
Therefore, both
Example 16.42.
Let us solve the system
Using the Euclidean algorithm, we can find integers
Theorem 16.43. Chinese Remainder Theorem.
Let
has a solution. Furthermore, any two solutions of the system are congruent modulo
Proof.
We will use mathematical induction on the number of equations in the system. If there are
Considering the first
has a solution that is unique modulo
Example 16.44.
Let us solve the system
From Example 16.42 we know that
Solving the next two equations, we can reduce the system to
Solving this last system, we find that
Example 16.45.
Suppose that we wish to multiply
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
The Chinese Remainder Theorem tells us that solutions are unique up to modulo
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.