Chinese Remainder Theorem

The Chinese remainder theorem is used to get a unique solution for an arbitrary finite number of congruences with coprime moduli, which states that:

If M = m₁, m₂, …, m_r is a set of pairwise relatively prime non-zero integers such that gcd(m_i, m_j) = 1 for i ≠ j, and a₁, a₂, …, a_r  Є ℤ, then the system of congruences x ≡ a₁ (mod m₁), x  ≡ a₂ (mod m₂), …, x ≡ a_r (mod m_r) has a unique solution in modulo M for all 1≤ i ≤ r. 

It is applied in all areas of mathematics, especially in computer science, including internet cryptography, where it is used to encode numbers based on it.

Now, let us first verify if the theorem is true for a pair of congruences.

For Pair of Congruences

It states that if m and n are two coprime numbers, the pair of congruences x ≡ a (mod m) and x ≡ b (mod n) has a unique solution for x modulo mn, ∀ a, b Є ℤ.

Here, we show that there is always a solution for x modulo mn, and then we verify that the solution is unique in modulo mn.

Proof

Verifying the Existence of Solution 

The first congruence is written as

x ≡ a (mod m) ⇒ x = a + mp, for some p Є ℤ …..(i)

Using (i), we get the second congruence as x ≡ b (mod n)

⇒ a + mp ≡ b (mod n)

On subtracting a from both sides, we get

⇒ mp ≡ b – a (mod n) …..(ii)

Since m and n are coprime numbers, gcd(m, n) = 1

Also, we know m (mod n) is invertible. Let m’ be the inverse of m (mod n), which means mm’ ≡ 1 (mod n)

On multiplying (ii) by m’, we get

mm’p ≡ m’(b – a) (mod n) ⇒ p = m’(b – a) + nq, for some q Є ℤ

⇒ x = a + mp = a + mm’(b – a) + mnq

Thus, if x satisfies the given pair of congruences, it must hold the above form.

Now, let us verify this expression for every q Є ℤ, which satisfies the given pair of congruences a + mm’(b – a) + mnq ≡ a + 0 + 0 ≡ a (mod m) and a + mm’(b – a) + mnq ≡ a + 1(b – a) + 0 ≡ b (mod n)

Verifying the Uniqueness of Solution

Assuming the solution is not unique, if x = c and x = c’ both satisfy x ≡ a (mod m) and x ≡ b (mod n), then we have c ≡ c’ (mod m) and c ≡ c’ (mod n). 

Thus, m | (c − c’) and n | (c − c’). 

Since gcd(m, n) = 1, the product mn divides (c − c’), which means c ≡ c’ (mod mn). 

This shows that all solutions to the given pair of congruences are the same in modulo mn, and thus, the solution is unique.

Now, let us verify the Chinese remainder theorem for a system of congruences.

Proof

To prove the theorem, first, we verify that there is always a solution for x modulo m_i, and then, if the solution is unique in modulo m_i for all 1≤ i ≤ r.

Existence of Solution 

Here, we prove the existence of the solution using the mathematical induction.

We have already proved the base step for r = 2

Now, let us assume all simultaneous congruences with r pairwise relatively prime moduli in the inductive part for which the statement is true.

Considering a system of simultaneous congruences with r + 1 pairwise relatively prime moduli, we get:

x ≡ a₁ (mod m₁), …, x ≡ a_r (mod m_r), x ≡ a_r+1 (mod m_r+1), where (m_i, m_j) = 1 for all i ≠ j, and all the a_i’s are arbitrary. 

By the inductive hypothesis, there is a solution b to the first r congruences, say b ≡ a₁ (mod m₁), b ≡ a₂ (mod m₂), …, b ≡ a_r (mod m_r). 

Now, from the system of two congruences, we get 

x ≡ b (mod m₁m₂ … m_r) and x ≡ a_{r + 1} (mod m_{r + 1}) 

⇒ x ≡ b (mod M) and x ≡ a_{r + 1} (mod m_{r + 1}) …..(iii)

Since (m_r, m_{r + 1}) = 1 for i = 1, 2, …, r, we have gcd(m₁m₂ … m_r, m_{r + 1}) = 1, and the two moduli in (iii) are relatively prime. 

As we know, in the case of two congruences, there is always a solution to (iii), say c. 

Since c ≡ b (mod m₁m₂ … m_r), we have c ≡ b (mod M) for i = 1, 2, . . . , r. 

For any value of b, we have b ≡ a_i (mod M) for i = 1, 2, …, r. 

Thus, c ≡ a_i (mod M) for i = 1, 2, …, r. Also, c ≡ a_{r + 1} (mod m_{r + 1}). 

For any value of c, we observe that c satisfies r + 1 given congruences. This concludes the inductive step, which indicates a solution exists for x modulo m_i (1≤ i ≤ r). 

Uniqueness of Solution 

Assuming the solution is not unique, if x = c and x = c’ both satisfy x ≡ a₁ (mod m₁), x  ≡ a₂ (mod m₂), …, x ≡ a_r (mod m_r), then we have c ≡ c’ (mod m_i) for i = 1, 2, …, r

Thus, m_i | (c − c’) for i = 1, 2, …, r

Since all the m_i’s are pairwise relatively prime, their product m₁m₂ …m_r divides (c − c’), which means c ≡ c’ (mod m₁m₂ …m_r) ⇒ c ≡ c’ (mod M).

This shows all solutions to the given system of congruences are the same when determined by modulo m₁m₂ …m_r (that is, modulo M).

Thus, the Chinese remainder theorem is verified.

The solution to a system of congruences using the Chinese remainder theorem is found by the formula:

x ≡ ${\sum ^{r}_{i=1}a_{i}M_{i}x_{i}\left( modM\right)}$

Here,

• ${M_{i}=\dfrac{M}{m_{i}}}$
• x_i is the modular inverse of M_i, modulo m_i

Solved Examples