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)$

1. CRT states that the above set of equations have a unique solution of moduli which are relatively prime.

2. 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 x 7 = 35.

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

3. Therefore CRT suggests that for an arbitrary number which is less than p and q, 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

4. Applications of CRT:

5. To solve quadratic congruence.

6. To represent a very large integer in terms of list of small integers.

   x = 2 mod 3

   x = 3 mod 5

   x = 2 mod 7

   The solution to this set of equation follows the following steps:

• Find $M = m_1 x m_2 x m_3 x ……. x m_k$

This is the common modulus.

M = 3 x 5 x 7 = 105

• 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$

• Find the multiplicative inverse of M1, M2 , Mk using corresponding

moduli (m1, m2….mk)

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

• The solution to simultaneous equation is

$x = (a_1 x M_1 x M_1^{-1} + a_2 x M_2 x M_2^{-1} + a_3 x M_3 x M_3^{-1}) \mod M \\ x = (2 x 35 x 2 + 3 x 21 x 1 + 2 x 15 x 1) \mod 105 \\ x = (140 + 63 + 30) mod 105 \\ x = 233 mod 105$

$[233/105 \rightarrow dividend = 2, remainder (\mod) = 23]$

Therefore, x = 23 mod 105