We seek to solve the set of equations: x1≡r1 (mod m1) [1.1.1] x2≡r2 (mod m2) [1.1.2] ... xn≡rn (mod mn) [1.1.n] Where
the m's are relatively prime. This is a condition for the use of the
formula below (called the Chinese Remainder Theorem) although, as we
know, the Chinese Problem might be solvable anyway.
Let M=product of the m's=m1·m2...mn Let Mi=M/mi, where i=1...n, that is it is the product of all the m's except mi. Also [1.2]
The formula called the Chinese Remainder Theorem is: [1.3]
number when divided by 3, gives a remainder 2; when divided by 4, a
remainder 3 and when divided by 5, a remainder 4. We seek the number
(least positive number).
Provided the divisors are relatively prime, the formula can be used to find a solution.
M=60 x≡359 (mod 60) x≡59 (mod 60) The number is therefore 59.
A number when divided by 7, gives a remainder 5; when divided by 9, a
remainder 2 and when divided by 11, a remainder 10. We seek the number
(least positive number).
Calculating inverse, s:
99s≡1 (mod 7) s≡1 (mod 7)
77s≡1 (mod 9) 5s≡1 (mod 9) s≡2 (mod 9)
63s≡1 (mod 11) 8s≡1 (mod 11) s≡7 (mod 11)
the divisors are relatively prime, the formula can be used to find a
solution. The inverses are found, in this case, by testing. Otherwise, Euclid would have to be used.
M=693 x≡5213 (mod 693) x≡362 (mod 693)
The solution to the equations is 362 (mod 693), which may be verified by trying the remainders.
Proof of the Chinese Remainder Theorem
We seek to solve the set of equations (reproduced from above): x1≡r1 (mod m1) [1.1.1] x2≡r2 (mod m2) [1.1.2] ... xn≡rn (mod mn) [1.1.n] Where
the m's are relatively prime. Let M=product of the m's=m1·m2...mn Let Mi=M/mi, for i=1...n, that is it is the product of all the m's except mi. Also [1.2]
Formulae 1.2 are always solvable, when gcd(Mi, mi)=1, which they always are when the m's are relatively prime, because gcd(M/mi, mi)=1, because M has no factor mi, and mi is pair-wise relatively prime with all the other m's.
The formula called the Chinese Remainder Theorem is: [1.3] We wish to show that x is a solution to the Equations 1.1.1 to 1.1.n, and that it is unique.
back to more basic ideas, we can convert the equations 1.1.1 to 1.1.n
to a common modulus, when we can simply add them, by multiplying each
equation i, by Mi. For instance, multiplying 1.1.1 by M1 gives: M1x1≡r1M1 (mod M1·m1), which gives: M1x1≡r1M1 (mod M), because M/m1·m1=M
The new equation list becomes, therefore: M1x1≡r1M1 (mod M) M2x1≡r2M2 (mod M) ... Mnxn≡rnMn (mod M) [4a]
Now multiply each equation (i) by the respective multiplicative inverse of Mi for i=1...n. [4b]
Now sum all the equations, and equate the right-hand-side to x: [4.1]
Now we note that in all cases, for i=1 to n, x≡xi≡ri (mod mi), that is, we get the original equations, so x is a solution to the set of equations 1.1.1 to 1.1.n above.
For instance, taking modulo m1, all the terms will disappear, because they have m1 as a factor, except M1, which is relatively prime to m1. And M1, multiplied by its inverse is 1, modulo m1, so what remainds is: x≡r1 (mod m1) The corresponding result occurs for all the divisors, mi.
Therefore, x is a solution to the set of Equations 1.1.1 to 1.1.n. ■
The solution is unique modulo M
Suppose that s is a another solution to the equations, which is unique modulo M, so s and x are distinct.
For each of the equations 1.1.1 to 1.1.n s≡x≡xi≡ri (mod mi) → s≡x (mod mi) Using a definition of modulus: s=x+k·mi s and x can differ only by a multiple of the modulus, which is zero modulo mi, so s and x are equaivalent modulo mi. ■