How does the Chinese Remainder Theorem work? by Sujith Vijay

Answer by Sujith Vijay:

Let us start with a totally different problem. Suppose you want to find the polynomial of least degree satisfying [math]p(1)=8, p(2) = 13 [/math] and [math] p(3) = 34[/math].

We write [math]p(x)=p_1(x) + p_2(x) + p_3(x)[/math] where

[math]p_1(1)=8 \quad p_1(2) = 0 \; \; \quad p_1(3) = 0[/math]

[math]p_2(1)=0 \quad p_2(2) = 13 \quad p_2(3) = 0[/math]

[math]p_3(1)=0 \quad p_3(2) = 0 \; \; \quad p_3(3) = 34[/math]These subproblems are easier. Clearly,

[math]p_1(x)=c_1(x-2)(x-3)[/math]

[math]p_2(x)=c_2(x-1)(x-3)[/math]

[math]p_3(x)=c_3(x-1)(x-2)[/math]Using the data given, we get [math]c_1=4, c_2=-13, c_3=17[/math] and [math]p(x)=8x^2-19x+19[/math]. The technique we used is called Lagrange interpolation.

Chinese Remainder Theorem works in a very similar way. Consider the problem you have posted.

[math] x \equiv 3 \; \rm { mod } \; 5[/math]

[math] x \equiv 5 \; \rm { mod } \; 7[/math]

[math] x \equiv 1 \; \rm { mod } \; 9[/math]We write [math] x = y_1 + y_2 + y_3 [/math] where

[math] y_1 \equiv 3 \; {\rm { mod }} \; 5 \quad y_1 \equiv 0 \; {\rm { mod }} \; 7 \quad y_1 \equiv 0 \; {\rm { mod }} \; 9[/math]

[math] y_2 \equiv 0 \; {\rm { mod }} \; 5 \quad y_2 \equiv 5 \; {\rm { mod }} \; 7 \quad y_2 \equiv 0 \; {\rm { mod }} \; 9[/math]

[math] y_3 \equiv 0 \; {\rm { mod }} \; 5 \quad y_3 \equiv 0 \; {\rm { mod }} \; 7 \quad y_3 \equiv 1 \; {\rm { mod }} \; 9[/math]

Once again, the subproblems are easier. We have,

[math] y_1 = 63z_1 \equiv 3 \; \rm { mod } \; 5 [/math]

[math] y_2 = 45z_2 \equiv 5 \; \rm { mod } \; 7 [/math]

[math] y_3 = 35z_3 \equiv 1 \; \rm { mod } \; 9 [/math]This solves to [math] z_1 = 1, z_2 = 4, z_3 = 8 [/math]

[math] x \equiv 63 + 180 + 280 \equiv 208 \; \rm { mod } \; 315 [/math]

Thus the smallest positive integer satisfying the given set of congruences is [math] 208 [/math].

How does the Chinese Remainder Theorem work?