Suppose we have a typical Chinese Remainder Theorem problem, where we wish to solve the pair of congruence equations
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
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
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 4With the assumptions of Research Question 1, find formulas for c1 and c2 so that is a solution to the pair of congruences in Research Question 1. |
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 |