Monthly Archives: October 2016

How does the Chinese Remainder Theorem work?


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?

Advertisements

Leave a comment

Filed under Life