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

xa_{1}(modm_{1}) andxa_{2}(modm_{2}).for

x, as in Research Question 1. It would be nice to have a formula forxgiven in terms ofa_{1},a_{2},m_{1}, andm_{2}. 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=c_{1}m_{1}+c_{2}m_{2},where

c_{1}andc_{2}are yet to be determined. If this formula forxis correct, what would we learn aboutc_{1}andc_{2}by plugging into the two congruence equations above? Substituting into the first equation, we would havec_{1}m_{1}+c_{2}m_{2}a_{1}(modm_{1}),which simplifies to just

c_{2}m_{2}a_{1}(modm_{1}). Can you solve this forc_{2}? Once you have done so, then use the second congruence equation in a similar manner to determinec_{1}in terms ofa_{1},a_{2},m_{1}, andm_{2}. 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

c_{1}andc_{2}so thatx=c_{1}m_{1}+c_{2}m_{2},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=c_{1}m_{1}+c_{2}m_{2}. For the general case, you will have to try to get the right formula.Here is the setup. You are given

ncongruences of the formxa(mod_{i}m) satisfying the hypotheses you conjectured in Research Question 3. You want a formula for the solution_{i}xin terms of theaand the_{i}m. 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_{i}xwas substituted into one of the initial congruences, all but one term dropped out. That should have made it easier to solve forc_{1}andc_{2}.

## Research Question 5

With the assumptions of Research Question 3, find a formula for

xso thatxwill be a solution to the system of congruencesxa(mod_{i}m)._{i}

Section 7.1 | Section 7.2 | Section 7.3 | Section 7.4

Copyright © 2001 by W. H. Freeman and Company