Chinese remainder theorem– Once a Chinese riddle asks the following question- Is there a positive integer x such that when x is divided by 3 it yields a remainder 2, when x is divided by 5 it yields a remainder 4, and when x is divided by 7 it yields a remainder 6?
In other words, we seek a common solution of the following three congruence equations:
x ≡ 2 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7)
Theorem (Chinese remainder theorem)
Consider the system
where the mi are pairwise relatively prime. Then the system has a unique solution modulo
Proposition: Consider the system
Of congruence equations
(Then each pair and are co-prime.) Let 
Then the following is a solution of the system (1)
Now we will solve the riddle asked by Chinese:
First method: (a) x ≡ 2 (mod 3) and (b) x ≡ 4 (mod 5)
Chinese remainder theorem tells us there is a unique solution modulo M = 3 ・ 5 = 15. Adding multiples of the modulus m = 5 to the given solution x = 4 of the second equation (b), we obtain the following three solutions of (b) which are less than 15:
4, 9, 14
Testing each of these solutions in equation (a), we find that 14 is the only solution of both equations. Now we apply the same process to the two equations
(c) x ≡ 14 (mod 15) and (d) x ≡ 6 (mod 7)
Chinese remainder theorem tells us there is a unique solution modulo M = 15 ・ 7 = 105 .
Adding multiples of the modulus m = 15 to the given solution x = 14 of the first equation (c), we obtain the following seven solutions of (b) which are less than 105:
14, 29, 44, 59, 74, 89, 104
Testing each of these solutions of (c) in the second equation (d) we find that 104 is the only solution of both equations. Thus the smallest positive integer satisfying all three equations is
x = 104
This is the solution of the riddle.
Second method:
M = 3 ・ 5 ・ 7 = 105, M1 = 105/3 = 35, M2 = 105/5 = 21, M3 = 105/7 = 15
Using the above notation, we obtain
We now seek solutions to the equations
35x ≡ 1 (mod 3), 21x ≡ 1 (mod 5), 15x ≡ 1 (mod 7)
Reducing 35 modulo 3, reducing 21 modulo 5, and reducing 15 modulo 7, yields the system
2x ≡ 1 (mod 3), x ≡ 1 (mod 5), x ≡ 1 (mod 7)
The solutions of these three equations are, respectively,
s1 = 2, s2 = 1, s3 = 1
We now substitute into the formula (1) to obtain the following solution of our original system:
x0 = 35 ・ 2 ・ 2 + 21 ・ 1 ・ 4 + 15 ・ 1 ・ 6 = 314
Dividing this solution by the modulus M = 105, we obtain the remainder
x = 104 which is the unique solution of the riddle between 0 and 105.