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: If m1 and m2 are positive integers such that ????, then for any integers a1 and a2, the pair of congruences
x a1 (mod m1) and x
has a unique solution x modulo m1m2.
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 m1 and m2 but before a1 and a2. This means that the missing condition should involve m1 and m2 but not a1 or a2. So to complete the statement of the theorem, you need to determine what condition on m1 and m2 allows one to find a unique solution to the congruences for all choices of a1 and a2.
Research Question 1Complete 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
a1, a2,
m1, and m2 as input, and
finds all values of x (mod
m1m2) that satisfy the
pair of congruences x
a1 (mod m1) and x
a2 (mod
m2). For example, to see if the
congruences
x 2 (mod 4) and
x
1 (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
x 6 (mod 20).
Here's what we get for the pair of congruences
x 3 (mod 6) and
x 9 (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.