# Monthly Archives: October 2016

## How does the Chinese Remainder Theorem work?

How does the Chinese Remainder Theorem work? by Sujith Vijay

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

We write $p(x)=p_1(x) + p_2(x) + p_3(x)$ where

$p_1(1)=8 \quad p_1(2) = 0 \; \; \quad p_1(3) = 0$
$p_2(1)=0 \quad p_2(2) = 13 \quad p_2(3) = 0$
$p_3(1)=0 \quad p_3(2) = 0 \; \; \quad p_3(3) = 34$

These subproblems are easier. Clearly,

$p_1(x)=c_1(x-2)(x-3)$
$p_2(x)=c_2(x-1)(x-3)$
$p_3(x)=c_3(x-1)(x-2)$

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

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

$x \equiv 3 \; \rm { mod } \; 5$
$x \equiv 5 \; \rm { mod } \; 7$
$x \equiv 1 \; \rm { mod } \; 9$

We write $x = y_1 + y_2 + y_3$ where

$y_1 \equiv 3 \; {\rm { mod }} \; 5 \quad y_1 \equiv 0 \; {\rm { mod }} \; 7 \quad y_1 \equiv 0 \; {\rm { mod }} \; 9$

$y_2 \equiv 0 \; {\rm { mod }} \; 5 \quad y_2 \equiv 5 \; {\rm { mod }} \; 7 \quad y_2 \equiv 0 \; {\rm { mod }} \; 9$

$y_3 \equiv 0 \; {\rm { mod }} \; 5 \quad y_3 \equiv 0 \; {\rm { mod }} \; 7 \quad y_3 \equiv 1 \; {\rm { mod }} \; 9$

Once again, the subproblems are easier. We have,

$y_1 = 63z_1 \equiv 3 \; \rm { mod } \; 5$
$y_2 = 45z_2 \equiv 5 \; \rm { mod } \; 7$
$y_3 = 35z_3 \equiv 1 \; \rm { mod } \; 9$

This solves to $z_1 = 1, z_2 = 4, z_3 = 8$

$x \equiv 63 + 180 + 280 \equiv 208 \; \rm { mod } \; 315$

Thus the smallest positive integer satisfying the given set of congruences is $208$.

How does the Chinese Remainder Theorem work?