7.1   Solving Two Congruences

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 === a2 (mod m2)

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 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 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:

Your browser does not support java.

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):

Your browser does not support java.

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

Chapter 7 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company