Problem 27 : The Chinese Remainder Theorem
I have been meaning to write this out for a long time now. This is a powerful theorem that to me allows one to effectively deduce the subspace of solutions to a series of congruence relations. As far as history goes, the earliest known statement of the theorem is present in the 3rd-century book Sun-tzu Suan-ching by Sun-tzu. Here is an embedded calculator for playing around with 2 congruences.
Theorem Statement
Suppose that we have a sequence of natural numbers that are relatively prime i.e. their greatest common divisor, gcd .
Then the following system of equations,
has a unique solution modulo .
The Modulo Inverse
Before beginning the proof, I would like to define the modulo inverse. The modulo inverse say, of w.rt. may be uniquely defined under certain conditions that will be clear soon.
Using the definition of modulo, should be a multiple of .
for some integer . A careful look at the expression reveals that if are not relatively prime or equivalently, gcd, we can find a divisor such that,
Now we have an issue, because LHS is an integer but the RHS is a fraction. So, there is no solution for integers and .
So, the condition for modulo inteverse of w.r.t. to exist, the condition that naturally arises from the definition is gcd.
Proof
Let be the product of the relatively prime sequence . To make this problem tractable, we need to uniquely consider the influence of each congruence relation in the system of congruences provided in the Theorem’s statement. To this end, we can define such that is a product of all the ’s for .
This allows us to claim that . Where we simply used the fact that gcd along with the definition of the modulo inverse.
Also, by design, for .
So, the sum will satisfy all the congruences. This proves the existence of the solution.
For uniqueness, we assume that distinct such that and for .
Then, the difference of the two . Since, the sequence is relatively prime, the only way in which can be divisible by all is if they are also divisible by their product. So, divides . Equivalently,
Therefore, and are the same solution modulo .