7.3   Solving Lots of Congruences

Now that you have completed the first two Research Questions, you know the exact nature of the solutions to the pair of congruences

x === a1 (mod m1)     and     x === a2 (mod m2).

Recall that the cases where there is a unique solution modulo m1m2 is covered by the Chinese Remainder Theorem for two congruences. Suppose instead you had three or more congruences. Is there a version of the Chinese Remainder Theorem in this case? There is indeed, and (surprise, surprise) it's your job to find it.

To help get you headed in the right direction, let's look at an example involving three specific congruences, such as

x === 1 (mod 5)
x === 2 (mod 6)
x === 3 (mod 7).

One way of proceeding is to begin by solving the first pair of congruences,

x === 1 (mod 5)     and     x === 2 (mod 6).

By applying the algebraic method of the Prelab, we can show that this pair of congruences is equivalent to the single congruence x === 26 (mod 30). Let's check this with our applet:

Your browser does not support java.

OK, now we have reduced our problem to just two congruences:

x === 26 (mod 30)     and     x === 3 (mod 7).

We can employ our method for pairs again to reach the single congruence x === 206 (mod 210). Again, let's check this with the applet:

Your browser does not support java.

So, we did it! We solved three congruences by twice applying what we know about solving a pair of congruences. Here's your chance to generalize this process.

Research Question 3

Give a statement of the Chinese Remainder Theorem (as in Research Question 1) for n congruences.

7.3.1  Using Java to Solve Lots of Congruences

We now introduce a new and improved Java applet that can be used to solve more than two congruences simultaneously. For example, to solve the system of congruences

x === 1 (mod 5)
x === 2 (mod 6)
x === 3 (mod 7),

we enter

Your browser does not support java.

Notice that the output agrees with what we found above. Try it with different numbers.

Section 7.1 | Section 7.2 | Section 7.3 | Section 7.4

Chapter 7 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company