The * Chinese Remainder Theorem* says that
certain systems of simultaneous congruences *with different
moduli* have solutions. The idea embodied in the theorem was
known to the Chinese mathematician Sunzi in the century A.D. --- hence the name.

I'll begin by collecting some useful lemmas.

* Lemma 1.* Let m and , ..., be positive integers.
If m is relatively prime to each of , ..., , then it is
relatively prime to their product .

* Proof.* If , then there is a prime p
which divides both m and . Now , so p must divide for some i. But p divides both m and , so . This
contradiction implies that
.

For example, 6 is relatively prime to 25, to 7, and to 11. Now , and .

I showed earlier that the greatest common divisor of a and b is *greatest* in the
sense that it is divisible by any common divisor of a and b. The next
result is the analogous statement for least common multiples.

* Lemma 2.* Let m and , ..., be positive integers.
If m is a multiple of each of , ..., , then m is a multiple
of .

* Proof.* By the Division Algorithm, there are
unique numbers q and r such that

Now divides both m and , so divides r. Since this is true for all i, r is a
common multiple of the smaller than the
*least* common multiple . This is only possible if . Then , i.e. m is a multiple of
.

For instance, 88 is a multiple of 4 and 22. The least common multiple of 4 and 22 is 44, and 88 is also a multiple of 44.

* Lemma 3.* Let , ..., be positive integers.
If , ..., are pairwise relatively prime (that is, for ), then

* Proof.* Induct on n. The statement is trivially
true for , so I'll start with . The statement for follows from the equation :

Now assume , and assume the result is true for n. I will prove that it holds for .

* Claim:* .

(Some people take this as an iterative *definition* of .) is a multiple of each
of , ..., , so by Lemma 2 it's a multiple of . It's also a multiple of , so

On the other hand, for ,

Therefore,

Obviously,

Thus, is a common multiple of all the 's. Since is the least common multiple, Lemma 2 implies that

Since I have two *positive* numbers which divide one another,
they're equal:

This proves the claim.

Returning to the proof of the induction step, I have

The second equality follows by the induction hypothesis (the statement for n). The third equality follows from Lemma 1 and the result for .

As an example, 6, 25, and 7 are relatively prime (in pairs). The least common multiple is .

* Theorem.* (* The Chinese
Remainder Theorem*) Suppose , ..., are pairwise
relatively prime (that is, for ). Then the following system of congruences
has a unique solution mod :

* Notation.*

For example,

This is a convenient (and standard) notation for omitting a single variable term in a product of things.

* Proof.* Define

That is, is the product of the m's with omitted. By Lemma 1, . Hence, there are numbers , such that

In terms of congruences,

Now let

If , then , so mod all the terms but the k-th term are 0 mod :

This proves that x is a solution to the system of congruences (and incidentally, gives a formula for x).

Now suppose that x and y are two solutions to the system of congruences.

Then

Thus, is a multiple of all the m's, so

But the m's are pairwise relatively prime, so by Lemma 3,

That is, the solution to the congruences is unique mod .

* Example.* Solve

, so there is a unique solution mod 36. Following the construction of x in the proof,

Solution:

* Example.* Solve

The moduli are pairwise relatively prime, so there is a unique solution mod 60. This time, I'll solve the system using an iterative method.

But , so

Hence,

Finally, , so

Hence, .

Now put everything back:

* Example.* Calvin Butterball keeps pet meerkats
in his backyard. If he divides them into 5 equal groups, 4 are left
over. If he divides them into 8 equal groups, 6 are left over. If he
divides them into 9 equal groups, 8 are left over. What is the
smallest number of meerkats that Calvin could have?

Let x be the number of meerkats. Then

From , I get . Plugging this into the second congruence, I get

Hence, . Plugging this into gives

Plugging this into the third congruence, I get

Hence, . Plugging this into gives

The smallest positive value of x is obtained by setting , which gives .

You can sometimes solve a system even if the moduli aren't relatively prime; the criteria are similar to those for solving system of linear Diophantine equations.\blank

* Theorem.* Consider the system

(a) If , there are no solutions.

(b) If , there is a unique solution mod .

Note that if , case (b) automatically holds, and --- i.e. I get the Chinese Remainder Theorem for .

* Proof.* (a) I'll prove the contrapositive.
Suppose x is a solution to the system of congruences, so

The first congruence gives , so . Similarly, . But and , so

Therefore,

This proves the contrapositive of the assertion, so (a) is true.

(b) First, suppose that if x and y are solutions to the system.

Thus, . Similarly, . Since is a multiple of and , it is a multiple of . Thus,

Thus, any two solutions are congruent mod .

Now suppose , so for some . Note that

It follows that is invertible mod , so there is an integer p such that

I claim that the following is a solution to the system for all :

You can obtain this "guess" by working backwards from the system assuming there is a solution, and solving the congruences by basic algebra. I will omit the details.

First, since ,

This shows that the proposed solution satisfies the first congruence.

Next. I need to reduce mod and show that I get . I'll need the following facts. First, since , we have .

Second, since , we have

Hence,

This shows that solves the congruences for all --- and so is a solution mod . Our initial observation shows that this is the only solution mod .

Let's look at an example to show how this works. Suppose we have the system of congruences

We have , , , and . Since , the condition for a solution is satisfied.

First, .

Next,

The multiplicative inverse of 6 mod 7 is . (You can find this by trial and error, or using the Extended Euclidean Algorithm.) A solution mod is

You can check that 141 solves the original congruences.

* Example.* Solve

Since , there is a unique solution mod . I'll use the iterative method to find the solution.

Since ,

Now I use my rule for "dividing" congruences: 6 divides both 12 and 6, and , so I can divide through by 6:

Multiply by 2, and convert the congruence to an equation:

Plug back in:

Copyright 2022 by Bruce Ikenaga