The Chinese Remainder Theorem is one of the oldest theorems in number theory. Your first job is to discover the right statement of this theorem. Most of the statement of the theorem is provided in the next section - you just need to fill in the missing part.

## 7.1.1 The Chinese Remainder Theorem for Two Congruences

Below is an incomplete statement of the Chinese Remainder Theorem for two congruences.

Chinese Remainder Theorem: Ifm_{1}andm_{2}are positive integers such that ????, then for any integersa_{1}anda_{2}, the pair of congruencesxa_{1}(modm_{1}) andxa_{2}(modm_{2})has a unique solution

xmodulom_{1}m_{2}.To complete Research Question 1, you need to figure out what condition is required in place of the ???? above to make the statement true. Notice that the ???? placement occurs after the introduction of

m_{1}andm_{2}but beforea_{1}anda_{2}. This means that the missing condition should involvem_{1}andm_{2}but nota_{1}ora_{2}. So to complete the statement of the theorem, you need to determine what condition onm_{1}andm_{2}allows one to find a unique solution to the congruences for all choices ofa_{1}anda_{2}.

## Research Question 1

Complete the statement of the Chinese Remainder Theorem for two congruences.

## 7.1.2 Some Help

To find the correct statement of the theorem, you'll probably want to do some experimentation. To assist with this job, an applet is provided that will find solutions to pairs of congruences. The applet takes

a_{1},a_{2},m_{1}, andm_{2}as input, and finds all values ofx(modm_{1}m_{2}) that satisfy the pair of congruencesxa_{1}(modm_{1}) andxa_{2}(modm_{2}). For example, to see if the congruencesx2 (mod 4) andx1 (mod 5) have any common solutions, we just execute the following:

As we can see from the output, in this case there is a unique solution given by

x6 (mod 20). Here's what we get for the pair of congruencesx3 (mod 6) andx9 (mod 10):

This time, the solution is not unique. You should compare the output from the applet to what you find algebraically (the method of the Prelab) in solving pairs of congruences. For example, try using applet to find the solutions to the exercises given in the Prelab sheet.

One last suggestion: You may also want to try to generalize the algebraic method that you used in the Prelab when solving specific pairs of congruences. This can be helpful both in finding the correct statement of the theorem as well as the proof. In fact, this is one way in which mathematicians find the right statement for a theorem. They have an idea for a proof and see how generally the method can be applied. Whatever they get is the statement of the theorem.

Section 7.1 | Section 7.2 | Section 7.3 | Section 7.4

Copyright © 2001 by W. H. Freeman and Company