7.4   Explicit Formulas

Suppose we have a typical Chinese Remainder Theorem problem, where we wish to solve the pair of congruence equations

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

for x, as in Research Question 1. It would be nice to have a formula for x given in terms of a1, a2, m1, and m2. Such a formula might be useful both for computation and for theoretical purposes. (For example, in the proof of Research Question 1.)

One approach to finding a formula is to use what is known as the method of undetermined coefficients. The idea is to guess the general form of the formula leaving some coefficients unspecified, assume that the formula is correct, and see if you can deduce the correct values of the unknown coefficients. If you can solve for the coefficients, you would have a conjecture for the right formula. With the right formula in hand, it may not be too hard to prove that it is the correct formula.

In this case, we will guess that the solution has the form

x = c1m1 + c2m2,

where c1 and c2 are yet to be determined. If this formula for x is correct, what would we learn about c1 and c2 by plugging into the two congruence equations above? Substituting into the first equation, we would have

c1m1 + c2m2 === a1 (mod m1),

which simplifies to just c2m2 === a1 (mod m1). Can you solve this for c2? Once you have done so, then use the second congruence equation in a similar manner to determine c1 in terms of a1, a2, m1, and m2. You might want to compute some examples to test your formula using the usual applet, which is included below the statement of Research Question 4.

Research Question 4

With the assumptions of Research Question 1, find formulas for c1 and c2 so that

x = c1m1 + c2m2,

is a solution to the pair of congruences in Research Question 1.

Your browser does not support java.

We now want to generalize the result of Research Question 4 to the case of several congruences. An important step in employing the method of undetermined coefficients is to guess the right general form of the answer. For Research Question 4, we suggested trying x = c1m1 + c2m2. For the general case, you will have to try to get the right formula.

Here is the setup. You are given n congruences of the form x === ai (mod mi) satisfying the hypotheses you conjectured in Research Question 3. You want a formula for the solution x in terms of the ai and the mi. In guessing the general form of the answer, think about what made the guess above work well for two congruences. One useful feature was that once the general form for x was substituted into one of the initial congruences, all but one term dropped out. That should have made it easier to solve for c1 and c2.

Research Question 5

With the assumptions of Research Question 3, find a formula for x so that x will be a solution to the system of congruences x === ai (mod mi).

Your browser does not support java.

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