Courses
Courses for Kids
Free study material
Offline Centres
More

Chinese Remainder Theorem

ffImage
Last updated date: 21st Feb 2024
Total views: 146.4k
Views today: 4.46k
hightlight icon
highlight icon
highlight icon
share icon
copy icon

An Introduction to the 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


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.


Conclusion

In this article, the Chinese remainder theorem is thoroughly covered. Each necessary element of the theorem is covered throughout the article. This theorem leads us to the conclusion that the Chinese Remainder Theorem is a classical theorem that explains the conditions under which several equations can have a simultaneous integer solution.

Competitive Exams after 12th Science

FAQs on Chinese Remainder Theorem

1. What does congruence mean?

If the difference between two integers a and b can be divided by the number m, then the two numbers are said to be congruent modulo m. Then it is stated that a is congruent to b modulo m, and this assertion is represented by the symbol a ≡ b (mod m). Congruence is the name given to such a relationship. Many features of congruences, especially those involving a variable x, such as XP ≡ x (mod p), where p is a prime number, are similar to those algebraic equations. They play a significant role in the theory of numbers.

2. What is the uniqueness of the Chinese remainder theorem?

Assume that all of the congruences have x and y as their solutions. When x and y are divided by ni, they provide the same residual, therefore their difference, x-y, is a multiple of both ni. Since x and y are congruent modulo N since the ni are pairwise coprime, their product N divides x-y as well. The first statement of the theorem assumes that x and y are non-negative and less than N; therefore, their difference can only be a multiple of N if x = y.

3. What does the mathematical term modulus mean?

Although the term "modulus" has multiple meanings in different fields, its mathematical use has the longest history and has had the greatest influence on contemporary culture. Carl Friedrich Gauss created modular arithmetic at the beginning of the 19th century, which is the field in which the modulus is most crucial. Modular arithmetic's central tenet is that two integers a and b are said to be congruent modulo a certain number n if and only if n, the modulus, is divisible by the gap between a and b.