Chinese Remainder Theorem (CRT) is used to solve a set of congruent equations with one variable but different moduli, which are relatively prime as shown below:

$x = a_1 (mod m_1) \\ x = a_2 (mod m_2) \\ x = a_k (mod m_k)$

For Ex.

Suppose we have 2 prime numbers as 5 and 7. Suppose that 16 is our number. Then, we have

16 mod 5 =1

16 mod 7 =2

There is only one number smaller than 5 × 7 =35.

These two residues can be used to uniquely determine the number.

Therefore CRT suggests that for an arbitrary which is less than p and b i.e. less than 9. L where p and q are prime, there must be a unique number x , such that

x < pq and

x = a mod p and x= b mod q

Applications of CRT :

a) To solve quadratic congruence.

b) To represent a very large integer in terms of list of small integers

The following is an example of a set of equations with different moduli

x = 2 (mod 3)

x = 3 (mod 5)

x = 2 (mod 7)

The solution to this set of equations is follows the following steps:

1) Find $M= m_1 × m_2 × m_3 × …………….× m_k$

This is the Common Modulus.

m = 3 × 5 × 7 = 105

2) Find $M_1 , M_2 , M_k$

$M_1 = M / m_1 , M_2 = M / m_2 ………M_k=M/ m_k \\ M_1 =105 /3 =35 \\ M_2 = 105 / 5 =21 \\ M_3 = 105 /7 =15$

3) Find the multiplicative inverse of $M_1, M_2 , M_k$ using corresponding Moduli $( m_1, m_2….m_k)$

$M_1^{-1} =2 \\ M_2^{-1} = 1 \\ M_3^{-1} = 1$

4) The solution to simultaneous equation is :

$x = (a_1 × M_1 × M_1^{-1} + a_2 × M_2 × M_2^{-1} + a_3 × M_3 × M_3^{-1} ) mod m \\ x = (2 × 35 × 2 + 3 × 21 × 1 +2 × 15 × 1 ) mod 105 \\ x= (140 + 63 + 30 ) mod 105 \\ x = ( 233 ) mod 105 \\ [233/105-\gt div=2 , rem (mod) =23]$

Ans. x= 23 mod 105