Chinese Remainder Theorem

According to the Chinese Remainder Theorem in Mathematics, if one is aware of the remainders of the Euclidean division of an integer n by several integers, they can then be used to determine the unique remainder of n's division by the product of these other integers, provided that the n and the divisors are pairwise coprime (no two divisors share a common factor other than 1).

History of the Sun Zi

The theory was developed by the mathematician Sun Zi in the third century AD, while Qin Jiushao first presented the entire theorem in 1247. Sun Zi was an ancient Chinese author who wrote a traditional Chinese work on military tactics. He was one of the first realists in the study of international affairs.

Sun Zi (c. 544 B.C.E. - c. 496 B.C.E.)

Statement of Remainder Theorem

According to the theorem, the system of simultaneous congruences is defined as pairwise coprime positive integers $n_{1},n_{2},\cdots ,n_{k}$ and arbitrary integers $a_{1},a_{2},\cdots ,a_{k}$,

$x \equiv a_{1}(mod\; n_{1})\\ x \equiv a_{2}(mod\; n_{2})\\\vdots \\ x \equiv a_{k}(mod\; n_{k})$

has a solution, which is a unique modulo, $N = n_{1} n_{2} \cdots n_{k}$.

Chinese Remainder Theorem Proof

The Chinese remainder theorem can be used to solve a system of congruences in the following manner:

• Compute $N = n_{1}\times n_{2} \times \cdots\times n_{k}$

• For every $i = 1,2,3, \cdots, k$ compute

$Y_{i} = \dfrac{N}{n_{i}} = n_{1}, n_{2}, \cdots, n_{i-1} n_{i+1} \cdots n_{k}$

• For every $i = 1,2, \cdots, k$ compute

$Z_{i} = y_{i}^{-1} mod\; n_{i}$ utilising Euclid's extended algorithm.

• The integer $x = \sum_{i=1}^{k}a_{1}y_{i}z_{i}$ is a solution to the system of congruences and $x\bmod N$ is the unique solution modulo N.

Now, let’s check why x is a solution for every $i = 1,2 \ldots ,k$,

So,

$x \equiv (a_{1}y_{1}z_{1} + a_{2}y_{2}z_{2}+\cdots a_{k}y_{k}z_{k}) (mod\; n_{i})$ $x\equiv (a_{i}y_{i}z_{i}) (mod\; n_{i})$

$ x \equiv (a_{i}) (mod\; n_{i})$

where the second line comes after because $y_{j} = 0 (mod\; n_{i})$ for each $j\neq i$ and the third line because of $y_{i}z_{i} \equiv 1(mod\; {n_i})$.

Now assume that there are two solutions u and v to the given systems of congruences.

Then,

$n_{1}|(u-v), n_{2}|(u-v),\cdots ,n_{k}|(u-v)$

Since $n_{1},n_{2}, \ldots ,n_{k}$ It's relative primes. So,

$u \equiv v \; mod(n_{1},n_{2}, \cdots, n_{k})$.

Hence Proved.

Application of the Chinese Remainder Theorem

• As it enables replacing a computation for which one knows a bound on the size of the result by numerous comparable computations on tiny integers, the Chinese remainder theorem is commonly employed for computing with large integers.

• A Godel numbering for sequences has been created using the Chinese Remainder Theorem and is utilised in the demonstration of Godel's Incompleteness Theorems.

• As a special example of the Chinese remainder theorem, the range ambiguity resolution methods utilised with medium pulse repetition frequency radar can be viewed as such.

Chinese Remainder Theorem Examples

1. Solve the system below using the Chinese remainder theorem:

$x\equiv 3(mod\; 5)\\ x\equiv 5(mod\; 7)$.

Ans: Given data,

$x\equiv 3(mod\; 5)\\ x\equiv 5(mod\; 7)$

By the Chinese Remainder Theorem,

We have

$N = 5\times 7 = 35 \\ N_{1}= \dfrac{35}{5} = 7 \\ N_{2}= \dfrac{35}{7} = 5$

Now using relation,

$N_{i}x_{i}\equiv 1(mod\;n_{i})$

$7x_{1} \equiv 1(mod\;5), \\ \Rightarrow 2x_{1} \equiv 1(mod\;5)\\ 6x_{1} \equiv 3(mod\;5)\\ x_{1} = 3$

Similarly,

$5x_{2} \equiv 1(mod\;7), \\ 15x_{2} \equiv 3(mod\;7), \\ x_{2} = 3$

Finally,

$N = N_{1}x_{1}a_{1}+N_{2}x_{2}a_{2}$

$7\times 3\times 3+5\times 5\times 3 = 138\\ \Rightarrow 138(mod\;35)\\ \Rightarrow 33(mod\;35)$

2. Determine the solution for the following system:

$x\equiv 1(mod\;2)\\ x\equiv 2(mod\;3)\\ x\equiv 3(mod\;5)$.

Ans: By the Chinese remainder theorem, we have

$N = 2\times 3\times 5 = 30 \\ N_{1} = \dfrac{30}{2} = 15 \\ N_{2} = \dfrac{30}{3} = 10 \\ N_{3} = \dfrac{30}{5} = 6$

Now using relation,

$N_{i}x_{i}\equiv 1(mod\;n_{i})$

So, when we solve $15x_{1} \equiv 1(mod\;2)$

$x_{1} \equiv 1(mod\;2)$

$x_{1} =1$

Now,

$10x_{2} \equiv 1(mod\;3)$

$x_{2} \equiv 1(mod\;3)$

$x_{2} =1$

Finally,

$6x_{3} \equiv 1(mod\;5)$

$x_{3} \equiv 1(mod\;5)$

$x_{3} =1$

Finally,

$N = N_{1}x_{1}a_{1}+N_{2}x_{2}a_{2}+N_{3}x_{3}a_{3}$

$1 \times 15 \times 2 + 1 \times 10 \times 2 + 1 \times 6 \times 3 = 53\\ \Rightarrow 53(mod\;30) \equiv 23(mod\;30)$.

3. Solve the system below using the Chinese remainder theorem:

$x\equiv 3(mod\;9)\\ x\equiv 7(mod\;13)$.

Ans: Given data,

$x\equiv 3(mod\;9)\\ x\equiv 7(mod\;13)$

By the Chinese Remainder Theorem, we have

$N = 9\times 13 = 117 \\ N_{1} = \dfrac{117}{9} = 13 \\ N_{2} = \dfrac{117}{13} = 9$

Now,

$13y_{1}= 1(mod\; 9), \\ \Rightarrow 4y_{1}= 1(mod\; 9)\\ 28y_{1}= 7(mod\; 9)\\ y_{1}= 7$

Similarly,

$9y_{2}= 1(mod\; 13), \\ \Rightarrow 27y_{2}= 3(mod\; 13) \\ \Rightarrow y_{2}= 3$

Finally,

$13\times 7\times 3+9\times 3\times 7 = 462 \\ \Rightarrow 462(mod\;117) \\ \Rightarrow 111(mod\;117)$

Important Points to Remember

• There exists an integer such that for each if and only if are coprime pairs of integers.

• Simultaneous linear congruences with coprime moduli have a singular solution provided by the Chinese remainder theorem.

• The Chinese Remainder Theorem states that the natural map is an isomorphism in terms of rings.