This post is the second post in a series of posts on the Chinese remainder theorem (CRT). The previous post sets up the scene by discussing the fundamental theorem of arithmetic. In this post, we derive the various versions of CRT from a lemma (Lemma A below) that is equivalent to the fundamental theorem of arithmetic.
Links to the other posts in the series: first post, third post, fourth post.
____________________________________________________________________________
The starting point
Lemma A and Theorem B are discussed in the previous post. Lemma A is shown to be equivalent to the fundamental theorem of arithmetic. Lemma A makes CRT possible.
Lemma A
Let , and be integers. Suppose that , i.e. the greatest common divisor of and is 1. If , then .
Theorem B
The following conditions are equivalent:
 The statement of Lemma A.
 (Euclid’s lemma) If is a prime number and , then either or .
 Every positive integer can be written as a product of prime numbers and that this product (called a factorization) is unique.
In this post, we start from Lemma A and derive several versions of CRT. First, let’s look at a consequence of Lemma A.
Lemma C
Let be positive integers that are pairwise relatively prime. Let . Then for any integer ,

if and only if for each .
Proof
The direction is clear.
We show the direction . Suppose that for each , . Then for some integer . Note that . By Lemma 1, . We can write for some integer . Continue the same argument, it follows that for some integer . This means that .
____________________________________________________________________________
The Chinese remainder theorem
The following are several statements of the Chinese remainder theorem. The first version is a restatement of Lemma C using congruence notation.
Theorem D (Chinese Remainder Theorem)
Let be positive integers that are pairwise relatively prime. Let . Then for any integers and ,

if and only if for each .
The proof of Lemma C would take care of Theorem D. Note that means that .
Theorem E (Chinese Remainder Theorem)
Let be positive integers that are pairwise relatively prime. Let . Then for any integers and ,

the integer is a solution of the linear congruence equation if and only if the integer is satisfies simultaneously the following linear congruence equations:
Proof
By Theorem D, if and only if for each .
Theorem F (Chinese Remainder Theorem)
Suppose are positive integers that are pairwise relatively prime. Let . Suppose we have the following system of linear congruence equations
such that each of the linear congruence equations has a unique solution, i.e. for each , and are relatively prime. Then the system of linear congruence equations has a unique solution modulo .
Proof
First, a solution is produced. Then it is shown that the solution is unique. To produce the solution, the first step is solve each equation individually. Because and are relatively prime, the equation has a unique solution . Thus for each .
Next, let be the product of all the moduli where . Note that and are still relatively prime. There exists a unique such that . In other words, is the multiplicative inverse of modulo .
The proposed solution is . The following shows that is the solution to each equation.
All the terms containing with drop out since contains as a factor. The product drops out since it is congruent to 1 modulo . Then is congruent to modulo .
To show the uniqueness, suppose is also a solution to the system of linear congruence equations. Then for each . Multiplying the inverse of on both sides, we have and for each . By Theorem E, .
Theorem G (Chinese Remainder Theorem)
Suppose are positive integers that are pairwise relatively prime. Let . For any sequence of integers , the following system of linear congruence equations
has a unique solution modulo .
Proof
This follows directly from Theorem F.
____________________________________________________________________________
To complete the loop
To complete the loop, we show that Theorem G implies Theorem D. Suppose that for each . Consider the following system of congruence equations:
The number is clearly a solution to this system of equations. By Theorem G, this solution is unique. So any other solution to this system must be congruent to modulo . By assumption, is a solution to the system. So .
The loop is now complete. Theorem G is the usual statement of CRT. Based on the loop, any one of the theorems can be called the Chinese remainder theorem. Note that the loop by itself does not establish the Chinese remainder theorem. For that to happen, some condition outside the loop must imply one condition in the loop. The above discussion shows that the fundamental theorem of arithmetic (in the form of Lemma A) implies Theorem D.
____________________________________________________________________________
Comments
CRT is a versatile tool and is found to be useful in many areas of mathematics. One approach in applying CRT is that of a divide and conquer idea. The original problem is divided into smaller problems, which can be solved independently of one another. At the end, the results of the smaller problems are combined to form the solution of the original problem. For example, in solving a linear congruence equation for a large modulus , CRT in the form of Theorem E suggests that the problem can be broken up into a set of linear congruence equations with smaller moduli. For this reason, CRT is important in computing (both theory and applications), especially in computing intensive areas such as coding theory and cryptography.
In the next posts, we discuss two algorithms for solving CRT simultaneous systems of equations and look at a few applications.
____________________________________________________________________________
Pingback: Another look at the fundamental theorem of arithmetic  Exploring Number Theory
Pingback: How to Chinese remainder, part 1  Exploring Number Theory
Pingback: How to Chinese remainder, part 2  Exploring Number Theory
Pingback: Speeding up modular exponentiation using CRT  Exploring Number Theory