Goseeko blog

What is Chinese remainder theorem?

by krishna

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 be the solutions respectively, of the congruence equations

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.

You may also like