Now that you have completed the first two Research Questions, you know the exact nature of the solutions to the pair of congruences
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,
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:
OK, now we have reduced our problem to just two congruences:
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:
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 3Give 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
Notice that the output agrees with what we found above. Try it with different numbers.